Branch-and-bound algorithn for solving problem of minimizing fees for external resources

Cover Page

Cite item

Full Text

Abstract

We consider a problem of scheduling jobs performed on a single machine. Precedence relations between jobs are established, as well as subsets of jobs that require additional external resources, for which a fee is charged. For each external resource, the extreme (first and last) job to be executed using that resource is uniquely determined. It is necessary to order the jobs without violating the precedence relations and minimizing total rent payments. We have proved that this problem is NP-hard in the strong sense, even if the processing times of all jobs are the same and the prices of all external resources are equal. Based on the properties of the objective function, lower bounds and the branch-and-bound method are proposed to solve the problem. In this method, enumeration is performed according to feasible permutations of extreme jobs using external resources. The computational experiment showed the efficiency of the proposed lower bounds of the objective function, which make it possible to cut off unpromising branches in the search tree. We also determined the type of input data for which the developed method is more successful than another known variant of exact methods that enumerate all jobs. In particular, for large-dimensional problems with fewer than 20 external resources, this method proves to be more efficient than CP Optimizer solver which is based on constraint programming.

About the authors

Elena Gennad'evna Musatova

V.A. Trapeznikov Institute of Control Sciences of RAS

Email: nekolyap@mail.ru
Moscow

Alexander Alekseevich Lazarev

V.A. Trapeznikov Institute of Control Sciences of RAS

Email: jobmath@mail.com
Moscow

References

  1. 1. КИБЗУН А.И., РАССКАЗОВА В.А. Модель целочисленно-го линейного программирования как математическое обес-печение системы оптимального планирования потоковогопроизводства на этапе оперативного графикования // Ав-томатика и телемеханика. – 2023. – №5. – С. 113—132.
  2. 2. МУСАТОВА Е.Г., ЛАЗАРЕВ А.А. Задача минимизации сум-марной взвешенной длительности курсов для одного прибо-ра с ограничениями предшествования // Автоматика и теле-механика. – 2023. – №9. – С. 153–168.
  3. 3. BRISKORN D., DAVARI M., MATUSCHKE J. Single-machinescheduling with an external resource // European Journal ofOperational Research. – 2021. – Vol. 293, No. 2. – P. 457–468.
  4. 4. BRUCKER P. Scheduling algorithms. – Springer: Heidelberg,2007. – 371 p..
  5. 5. CHEN B., POTTS C.N., WOEGINGER G.J. A reviewof machine scheduling: complexity, algorithms andapproximability // Handbook of Combinatorial Optimization. –Boston, MA: Springer US, 1998. – P. 1493–1641.
  6. 6. CSEBFALVI A.B., CSEBFALVI G. Hammock activities inproject scheduling // Proc. of the Sixteenth Annual Conf. ofPOMS. – Chicago, IL, 2005.
  7. 7. ELIEZER O. A new bi–objective hybrid metaheuristicalgorithm for the resource-constrained hammock cost problem(RCHCP). – Doctoral Dissertation. – Pecs, 2011. – 111 p.
  8. 8. GRAHAM R.L., LAWLER E.L., LENSTRA J.K., KAN A.R.Optimization and approximation in deterministic sequencingand scheduling: a survey // Annals of discrete mathematics. –1998. –Vol. 5 –P. 287–326.
  9. 9. HARHALAKIS G. Special features of precedence networkcharts // European Journal of Operational Research. – 1990. –Vol. 49, No. 1. – P. 50–59.
  10. 10. LAWLER E.L. Optimal sequencing of a single machine subjectto precedence constraints // Management Science. – 1973. –Vol. 19, No. 5. – P. 544–546.
  11. 11. LAWLER E.L. Sequencing jobs to minimize total weightedcompletion time subject to precedence constraints // Annals ofDiscrete Mathematics. – 1978. – Vol. 2 – P. 75-–90.
  12. 12. LAZAREV A., KHUSNULLIN N., MUSATOVA E. et al.Minimization of the weighted total sparsity of cosmonauttraining courses // Communications in Computer andInformation Science. – 2019. – Vol. 974. – P. 202–215.
  13. 13. LENSTRA J.K., RINNOOY KAN A.H.G. Complexityof scheduling under precedence constraints // OperationsResearch. – 1978. – Vol. 26, No. 1. – P. 22–35.
  14. 14. MOHRING R.H. Minimizing costs of resource requirements inproject networks subject to a fixed completion time // OperationsResearch. – 1984. – Vol. 32, No. 1. – P. 89—120.
  15. 15. NADERI B., RUIZ R., ROSHANAEI V. Mixed-integerprogramming vs. constraint programming for shop schedulingproblems: New results and outlook // INFORMS Journal onComputing. – 2023. – Vol. 35, No. 4. – P. 817–843.
  16. 16. RASSKAZOVA V.A. LIP model in solving RCPSP at theflow type production // Communications in Computer andInformation Science. – 2024. – Vol. 1913. – P. 75–88.
  17. 17. RODRIGUES S.B., YAMASHITA D.S. An exact algorithm forminimizing resource availability costs in project scheduling //European Journal of Operational Research. – 2010. – Vol. 206,No. 3. – P. 562–568.
  18. 18. TOMCZAK M., JASKOWSKI P. Scheduling repetitiveconstruction projects: Structured literature review // Journal ofCivil Engineering and Management. – 2022. – Vol. 28, No. 6. –P. 422–442.
  19. 19. VANHOUCKE M. Work continuity constraints in projectscheduling // Journal of Construction Engineering andManagement. – 2006. – Vol. 132, No. 1. – P. 14–25.
  20. 20. VANHOUCKE M. Work continuity optimization for theWesterscheldetunnel Project in the Netherlands // Tijdschriftvoor economie en management. – 2007. – Vol. 52, No. 3. –P. 435–449.
  21. 21. ZHANG A., ZHEN T., CHEN Y., CHEN G. An improvedalgorithm for parallel machine scheduling under additionalresource constraints // Optimization Letters. – 2023. – Vol. 17,No. 3. – P. 753–769.
  22. 22. ZOU X., WU G., ZHANG Q. Work continuity constraintsin repetitive project scheduling considering soft logic //Engineering, Construction and Architectural Management. –2021. – Vol. 28, No. 6. – P. 1713–1738.
  23. 23. https://www.ibm.com/docs/es/icos/22.1.0 (дата обращения:15.04.2025).

Supplementary files

Supplementary Files
Action
1. JATS XML
Download


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).