A survey of emerging models and methods of scheduling
https://doi.org/10.15514/ISPRAS-2014-26(3)-1
Abstract
The paper is addressed the important problem of systematization and conceptualization of scheduling theory. Scheduling is widely applied in such subject areas as production management, traffic flow organization, planning of projects and resource management into computing systems. However, a diversity of mathematical models and methods of scheduling poses usually the problem of design of fast algorithm as well as the problem of efficient software implementation taking into account specificity of subject area. A usage of typical solvers from shared mathematical libraries is exceedingly limited. A usage of object-oriented frameworks for software implementations is more perspective. In the paper we make an attempt to systematize and to generalize models and methods of scheduling theory with the aim of construction of such a framework. The main attention is paid to resource-constrained project scheduling problems. These problems are widely used in practice on the one hand and bring together different mathematical statements arising in related subject areas and disciplines on the other hand.
About the Authors
A. S. Anichkin
ISP RAS
Russian Federation
Russian Federation
V. A. Semenov
ISP RAS
Russian Federation
Russian Federation
References
1. Salewski F., Schirmer A., Drexl A. Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application. European Journal of Operational Research, 1997, vol. 102, no. 1, pp. 88-110.
2. Internet page: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0 %B8%D1%8F_%D1%80%D0%B0%D1%81%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D0%B9 (as amended June 4, 2013 at 14:07).
3. Demeulemeester E. L., B. de Reyck, Herroelen W. S. The discrete time/resource trade-off problem in project networks – A branch-and-bound approach. IIE Transactions, 2000, vol. 32, no. 11, pp. 1059-1069.
4. Lazarev A. A., Gafarov E. R. Teoriya raspisanij: zadachi i algoritmy [Scheduling theory: problems and algorithms]. Lomonosov Moscow State University, Moscow, Russia, 2011, 222 p.
5. Ranjbar M., Kianfar F. Solving the discrete time/resource trade-off problem in project scheduling with genetic algorithms. Applied Mathematics and Computation, 2007, vol. 191, no. 2, pp. 451-456.
6. Kovalenko YU. V. Slozhnost' nekotorykh zadach teorii raspisanij i ehvolyutsionnye algoritmy ikh resheniya [Complexity of some scheduling problems and evolutionary algorithms for their solution]. PhD thesis, Omsk, Russia, 2013, 129 p.
7. Ranjbar M., B. de Reyck, Kianfar F. A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling. European Journal of Operational Research, 2009, vol. 193, no. 1, pp. 35-48.
8. Sprecher A. Resource-constrained project scheduling: Exact methods for the multi-mode case. Series: Lecture Notes in Economics and Mathematical Systems, vol. 409, Springer, Berlin, Germany, 1994, 142 p.
9. Akkan C., Drexl A., Kimms A. Network decomposition-based benchmark results for the discrete time-cost tradeoff problem. European Journal of Operational Research, 2005, vol. 165, no. 2, pp. 339-358.
10. Internet page: https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1 %87%D0%B0_%D0%BE%D0%B1_%D1%83%D0%BF%D0%B0%D0%BA%D0%BE%D0%B2%D0%BA%D0%B5_%D0%B2_%D0%BA%D0%BE%D0%BD%D1%82%D0%B5%D0%B9%D0%BD%D0%B5%D1%80%D1%8B (as amended September 19, 2013 at 21:17).
11. Demeulemeester E. L., B. de Reyck, Foubert B., Herroelen W. S., Vanhoucke M. New computational results on the discrete time/cost trade-off problem in project networks. Journal of the Operational Research Society, 1998, vol. 49, no. 11, pp. 1153-1163.
12. Internet page: https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1 %87%D0%B0_%D0%BE_%D1%80%D0%B0%D0%BD%D1%86%D0%B5 (as amended June 29, 2014 at 07:47).
13. Deckro R. F., Hebert J. E., Verdini W. A., Grimsrud P. H., Venkateshwar S. Nonlinear time/cost tradeoff models in project management. Computers and Industrial Engineering, 1995, vol. 28, no. 2, pp. 219-229.
14. Stadtler H. Multilevel capacitated lot-sizing and resource-constrained project scheduling: An integrating perspective. International Journal of Production Research, 2005, vol. 43, no. 24, pp. 5253-5270.
15. Chassiakos A. P., Sakellaropoulos S. P. Time-cost optimization of construction projects with generalized activity constraints. Journal of Construction Engineering and Management, 2005, vol. 131, no. 10, pp. 1115-1124.
16. Internet page: https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1 %87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80%D0%B0 (as amended May 21, 2014 at 18:07).
17. Klein R., Scholl A. PROGRESS: Optimally solving the generalized resource-constrained project scheduling problem. Mathematical Methods of Operations Research, 2000, vol. 52, no. 3, pp. 467-488.
18. Brucker P., Knust S. Resource-constrained project scheduling and timetabling. Lecture Notes in Computer Science, 2001, vol. 2079, pp. 277-293.
19. Kolisch R. Integrated scheduling, assembly area- and part-assignment for large-scale, make-to-order assemblies. International Journal of Production Economics, 2000, vol. 64, no. 1-3, pp. 127-141.
20. Drexl A., Salewski F. Distribution requirements and compactness constraints in school timetabling. European Journal of Operational Research, 1997, vol. 102, no. 1, pp. 193-214.
21. Vanhoucke M. Work continuity constraints in project scheduling. Journal of Construction Engineering and Management, 2006, vol. 132, no. 1, pp. 14-25.
22. Pritsker A. A. B., Watters L. J., Wolfe P. M. Multiproject scheduling with limited resources: A zero-one programming approach. Management Science, 1969, vol. 16, no. 1, pp. 93-107.
23. Demeulemeester E. L., Herroelen W. S. Modelling setup times, process batches and transfer batches using activity network logic. European Journal of Operational Research, 1996, vol. 89, no. 2, pp. 355-365.
24. Blazewicz J., Lenstra J. K., Rinnooy Kan A. H. G. Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 1983, vol. 5, pp. 11-24.
25. Cesta A., Oddi A., Smith S. F. A constraint-based method for project scheduling with time windows. Journal of Heuristics, 2002, vol. 8, no. 1, pp. 109-136.
26. Ahuja H. N. Construction performance control by networks. John Wiley & Sons, New York, USA, 1976, 636 p.
27. Dorndorf U., Pesch E., Phan Huy T. A time-oriented branch-and-bound algorithm for resource-constrained project scheduling with generalized precedence constraints. Management Science, 2000, vol. 46, no. 10, pp. 1365-1384.
28. Davis E. W., Patterson J. H. A comparison of heuristic and optimum solutions in resource-constrained project scheduling. Management Science, 1975, vol. 21, no. 8, pp. 944-955.
29. Schwindt C. Generation of resource-constrained project scheduling problems subject to temporal constraints. Technical Report WIOR-543, Universität Karlsruhe, Germany, 1998.
30. Hegazy T. Optimization of resource allocation and leveling using genetic algorithms. Journal of Construction Engineering and Management, 1999, vol. 125, no. 3, pp. 167-175.
31. Neumann K., Zimmermann J. Exact and truncated branch-and-bound procedures for resource-constrained project scheduling with discounted cash flows and general temporal constraints. Central European Journal of Operations Research, 2002, vol. 10, no. 4, pp. 357-380.
32. Brooks G. N., White C. R. An algorithm for finding optimal or near optimal solutions to the production scheduling problem. Journal of Industrial Engineering, 1966, vol. 17, no. 2, pp. 173-186.
33. Neumann K., Zimmermann J. Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints. European Journal of Operational Research, 2000, vol. 127, no. 2, pp. 425-443.
34. Gomory R. E. An all integer programming algorithm. Chapter from book [[157]], pp. 193-206.
35. Neumann K., Schwindt C., Zimmermann J. Recent results on resource-constrained project scheduling with time windows: Models, solution methods, and applications. Central European Journal of Operations Research, 2002, vol. 10, no. 2, pp. 113-148.
36. Szwarg W. Solutions of the akers-friedman scheduling problem. Operations Research, 1960, vol. 8, no. 6, pp. 782-788.
37. Sabzehparvar M., Seyed-Hosseini S. M. A mathematical model for the multi-mode resource-constrained project scheduling problem with mode dependent time lags. Journal of Supercomputing, 2008, vol. 44, no. 3, pp. 257-273.
38. Ashour S. A Decomposition Approach for the Machine Scheduling Problem. University of Iowa, Iowa City, USA, 1967, 416 p.
39. Franck B., Neumann K. Resource-constrained project scheduling with time windows: Structural questions and priority rule methods. Technical Report WIOR-492, Universität Karlsruhe, Germany, 1997.
40. Giffler B., Thompson G. L., Van Ness V. Numerical experience with the linear and Monte-Carlo algorithms for solving production scheduling problems. Chapter from book [[157]], pp. 21-29.
41. Ballestin F., Valls V., Quintanilla S. Due dates and RCPSP. Chapter from book [[158]], pp. 79-104.
42. Page E. S. An approach to the scheduling of the N jobs on M machines. Journal of the Royal Statistical Society, 1961, vol. 23, no. 2, pp. 484-492.
43. Brânzei R., Ferrari G., Fragnelli V., Tijs S. Two approaches to the problem of sharing delay costs in joint projects. Annals of Operations Research, 2002, vol. 109, no. 1-4, pp. 359-374.
44. Kolisch R. Efficient priority rules for the resource-constrained project scheduling problem. Journal of Operations Management, 1996, vol. 14, no. 3, pp. 179-192.
45. Chiu H. N., Tsai D. M. An efficient search procedure for the resource-constrained multi-project scheduling problem with discounted cash flows. Construction Management and Economics, 2002, vol. 20, no. 1, pp. 55-66.
46. Boctor F. F. Some efficient multi-heuristic procedures for resource constrained project scheduling. European Journal of Operational Research, 1990, vol. 49, no. 1, pp. 3-13.
47. Özdamar L., Ulusoy G., Bayyigit M. A heuristic treatment of tardiness and net present value criteria in resource constrained project scheduling. International Journal of Physical Distribution and Logistics Management, 1998, vol. 28, no. 9/10, pp. 805-824.
48. Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 1979, vol. 5, pp. 287-326.
49. Baptiste P., Pape C. L., Nuijten W. Satisfiability tests and time-bound adjustments for cumulative scheduling problems. Annals of Operations Research, 1999, vol. 92, pp. 305-333.
50. Yang H. H., Chen Y. L. Finding the critical path in an activity network with time-switch constraints. European Journal of Operational Research, 2000, vol. 120, no. 3, pp. 603-613.
51. Brucker P., Drexl A., Möhring R., Neumann K., Pesch E. Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 1999, vol. 112, no. 1, pp. 3-41.
52. Vanhoucke M., Demeulemeester E. L., Herroelen W. S. Discrete time/cost trade-offs in project scheduling with time-switch constraints. Journal of the Operational Research Society, 2002, vol. 53, no. 7, pp. 741-751.
53. Słowin´ski R. Multiobjective network scheduling with efficient use of renewable and nonrenewable resources. European Journal of Operational Research, 1981, vol. 7, no. 3, pp. 265-273.
54. Krüger D., Scholl A. Managing and modelling general resource transfers in (multi-)project scheduling. OR Spektrum, 2010, vol. 32, no. 2, pp. 369-394.
55. Weglarz J. On certain models of resource allocation problems. Kybernetes, 1980, vol. 9, no. 1, pp. 61-66.
56. Elmaghraby S. E. An algebra for the analysis of generalized activity networks. Management Science, 1964, vol. 10, no. 3, pp. 494-514.
57. Böttcher J., Drexl A., Kolisch R., Salewski F. Project scheduling under partially renewable resource constraints. Management Science, 1999, vol. 45, no. 4, pp. 543-559.
58. Belhe U., Kusiak A. Resource-constrained scheduling of hierarchically structured design activity networks. IEEE Transactions on Engineering Management, 1995, vol. 42, no. 2, pp. 150-158.
59. Zhu G., Bard J. F., Yu G. A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem. INFORMS Journal on Computing, 2006, vol. 18, no. 3, pp. 377-390.
60. Neumann K. Stochastic project networks: Temporal analysis, scheduling and cost minimization. Series: Lecture Notes in Economics and Mathematical Systems, vol. 344, Springer, Berlin, Germany, 1990, 237 p.
61. Nudtasomboon N., Randhawa S. U. Resource-constrained project scheduling with renewable and non-renewable resources and time-resource tradeoffs. Computers and Industrial Engineering, 1997, vol. 32, no. 1, pp. 227-242.
62. Kuster J., Jannach D. Handling airport ground processes based on resource-constrained project scheduling. Lecture Notes in Computer Science, 2006, vol. 4031, pp. 166-176.
63. Neumann K., Schwindt C. Project scheduling with inventory constraints. Mathematical Methods of Operations Research, 2003, vol. 56, no. 3, pp. 513-533.
64. Viana A., P. de Sousa J. Using metaheuristics in multiobjective resource constrained project scheduling. European Journal of Operational Research, 2000, vol. 120, no. 2, pp. 359-374.
65. Bartels J. H., Zimmermann J. Scheduling tests in automotive R&D projects. European Journal of Operational Research, 2009, vol. 193, no. 3, pp. 805-819.
66. Vanhoucke M., Demeulemeester E. L., Herroelen W. S. An exact procedure for the resource-constrained weighted earliness-tardiness project scheduling problem. Annals of Operations Research, 2001, vol. 102, no. 1-4, pp. 179-196.
67. Schwindt C., Trautmann N. Batch scheduling in process industries: An application of resource-constrained project scheduling. OR Spectrum, 2000, vol. 22, no. 4, pp. 501-524.
68. Franck B., Schwindt C. Different resource-constrained project scheduling models with minimal and maximal time-lags. Technical Report WIOR-450, Universität Karlsruhe, Germany, 1995.
69. Neumann K., Schwindt C., Trautmann N. Scheduling of continuous and discontinuous material flows with intermediate storage restrictions. European Journal of Operational Research, 2005, vol. 165, no. 2, pp. 495-509.
70. Lorenzoni L. L., Ahonen H., G. de Alvarenga A. A multi-mode resource-constrained scheduling problem in the context of port operations. Computers and Industrial Engineering, 2006, vol. 50, no. 1-2, pp. 55-65.
71. Weglarz J., Blazewicz J., Cellary W., Słowin´ski R. Algorithm 520: An automatic revised simplex method for constrained resource network scheduling. ACM Transactions on Mathematical Software, 1977, vol. 3, no. 3, pp. 295-300.
72. Vanhoucke M. Scheduling an R&D project with quality-dependent time slots. Lecture Notes in Computer Science, 2006, vol. 3982, pp. 621-630.
73. Blazewicz J., Ecker K., Pesch E., Schmidt G., Weglarz J. Handbook on Scheduling: From Theory to Applications. Series: International Handbooks on Information Systems, Springer, Berlin, Germany, 2007, 647 p.
74. Rom W. O., Tukel O. I., Muscatello J. R. MRP in a job shop environment using a resource constrained project scheduling model. Omega, 2002, vol. 30, no. 4, pp. 275-286.
75. Kis T. A branch-and-cut algorithm for scheduling of projects with variable-intensity activities. Mathematical Programming, 2005, vol. 103, no. 3, pp. 515-539.
76. Nazareth T., Verma S., Bhattacharya S., Bagchi A. The multiple resource constrained project scheduling problem: A breadth-first approach. European Journal of Operational Research, 1999, vol. 112, no. 2, pp. 347-366.
77. Waligora G. Discrete-continuous project scheduling with discounted cash flows – A tabu search approach. Computers and Operations Research, 2008, vol. 35, no. 7, pp. 2141-2153.
78. Al-Fawzan M., Haouari M. A bi-objective model for robust resource-constrained project scheduling. International Journal of Production Economics, 2005, vol. 96, no. 2, pp. 175-187.
79. Kis T. RCPS with Variable intensity activities and feeding precedence constraints. Chapter from book [[158]], pp. 105-129.
80. Abbasi B., Shadrokh S., Arkat J. Bi-objective resource-constrained project scheduling with robustness and makespan criteria. Applied Mathematics and Computation, 2006, vol. 180, no. 1, pp. 146-152.
81. Jozefowska J., Mika M., Rozycki R., Waligora G., Weglarz J. Solving the discrete-continuous project scheduling problem via its discretization. Mathematical Methods of Operations Research, 2000, vol. 52, no. 3, pp. 489-499.
82. Kobylanski P., Kuchta D. A note on the paper by M. A. Al-Fawzan and M. Haouari about a bi-objective problem for robust resource-constrained project scheduling. International Journal of Production Economics, 2007, vol. 107, no. 2, pp. 496-501.
83. Weglarz J. Project scheduling with continuously divisible, doubly-constrained resources. Management Science, 1981, vol. 27, no. 9, pp. 1040-1053.
84. Chtourou H., Haouari M. A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling. Computers and Industrial Engineering, 2008, vol. 55, no. 1, pp. 183-194.
85. Bianco L., Dell’olmo P., Speranza M. G. Heuristics for multimode scheduling problems with dedicated resources. European Journal of Operational Research, 1998, vol. 107, no. 2, pp. 260-271.
86. Icmeli-Tukel O., Rom W. O. Ensuring quality in resource constrained project scheduling. European Journal of Operational Research, 1997, vol. 103, no. 3, pp. 483-496.
87. Bianco L., Caramia M., Dell’olmo P. Solving a preemptive project scheduling problem with coloring techniques. Chapter from book [[159]], pp. 135-146.
88. Van de Vonder S., Demeulemeester E. L., Herroelen W. S. A classification of predictive-reactive project scheduling procedures. Journal of Scheduling, 2007, vol. 10, no. 3, pp. 195-207.
89. Dorndorf U., Phan-Huy T., Pesch E. A survey of interval capacity consistency tests for time- and resource constrained scheduling. Chapter from book [[159]], pp. 213-238.
90. Sakkout H., Wallace M. Probe backtrack search for minimal perturbation in dynamic scheduling. Constraints, 2000, vol. 5, no. 4, pp. 359-388.
91. Dorndorf U., Pesch E., Phan-Huy T. Constraint propagation techniques for the disjunctive scheduling problem. Artificial Intelligence, 2000, vol. 122, no. 1-2, pp. 189-240.
92. Zhu G., Bard J. F., Yu G. Disruption management for resource-constrained project scheduling. Journal of the Operational Research Society, 2005, vol. 56, pp. 365-381.
93. Bomsdorf F., Derigs U. A model, heuristic procedure and decision support system for solving the movie shoot scheduling problem. OR-Spectrum, 2008, vol. 30, no. 4, pp. 751-772.
94. Neumann K., Schwindt C., Zimmermann J. Resource-constrained project scheduling with time windows: Recent developments and new applications. Chapter from book [[158]], pp. 375-407.
95. Klein R., Scholl A. Scattered branch and bound – An adaptive search strategy applied to resource-constrained project scheduling. Central European Journal of Operations Research, 1999, vol. 7, pp. 177-201.
96. Drexl A., Kimms A. Optimization guided lower and upper bounds for the resource investment problem. Journal of the Operational Research Society, 2001, vol. 52, no. 3, pp. 340-351.
97. Nonobe K., Ibaraki T. Formulation and tabu search algorithm for the resource constrained project scheduling problem. Chapter (pp. 557-588) from book Ribeiro C. C., Hansen P. (eds.) Essays and Surveys in Metaheuristics. Series: Operations Research/Computer Science Interfaces Series, vol. 15, Springer, Berlin, Germany, 2002, 664 p.
98. Ranjbar M., Kianfar F., Shadrokh S. Solving the resource availability cost problem in project scheduling by path relinking and genetic algorithm. Applied Mathematics and Computation, 2008, vol. 196, no. 2, pp. 879-888.
99. Pesch E. Lower bounds in different problem classes of project schedules with resource constraints. Chapter from book [[159]], pp. 53-76.
100. Yamashita D. S., Armentano V. A., Laguna M. Robust optimization models for project scheduling with resource availability cost. Journal of Scheduling, 2007, vol. 10, no. 1, pp. 67-76.
101. Klein R., Scholl A. Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling. European Journal of Operational Research, 1999, vol. 112, no. 2, pp. 322-346.
102. Shadrokh S., Kianfar F. A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty. European Journal of Operational Research, 2007, vol. 181, no. 1, pp. 86-101.
103. Klein R. Project scheduling with time-varying resource constraints. International Journal of Production Research, 2000, vol. 38, no. 16, pp. 3937-3952.
104. Nübel H. The resource renting problem subject to temporal constraints. OR-Spektrum, 2001, vol. 23, no. 3, pp. 359-381.
105. Hartmann S. Project scheduling under limited resources: Models, methods, and applications. Series: Lecture Notes in Economics and Mathematical Systems, vol. 478, Springer, Berlin, Germany, 1999, 221 p.
106. Ballestin F. A genetic algorithm for the resource renting problem with minimum and maximum time lags. Lecture Notes in Computer Science, 2007, vol. 4446, pp. 25-35.
107. Icmeli O., Rom W. O. Solving the resource constrained project scheduling problem with optimization subroutine library. Computers and Operations Research, 1996, vol. 23, no. 8, pp. 801-817.
108. Bandelloni M., Tucci M., Rinaldi R. Optimal resource leveling using non-serial dynamic programming. European Journal of Operational Research, 1994, vol. 78, no. 2, pp. 162-177.
109. Bartusch M., Möhring R. H., Radermacher F. J. Scheduling project networks with resource constraints and time windows. Annals of Operations Research, 1988, vol. 16, no. 1, pp. 201-240.
110. Davis K. R., Stam A., Grzybowski R. A. Resource constrained project scheduling with multiple objectives: A decision support approach. Computers and Operations Research, 1992, vol. 19, no. 7, pp. 657-669.
111. Debels D., Vanhoucke M. The impact of various activity assumptions on the lead time and resource utilization of resource-constrained projects. Computers and Industrial Engineering, 2008, vol. 54, no. 1, pp. 140-154.
112. Maniezzo V., Mingozzi A. The project scheduling problem with irregular starting time costs. Operations Research Letters, 1999, vol. 25, no. 4, pp. 175-182.
113. Demeulemeester E. L., Herroelen W. S. An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem. European Journal of Operational Research, 1996, vol. 90, no. 2, pp. 334-348.
114. Möhring R. H., Schulz A. S., Stork F., Uetz M. On project scheduling with irregular starting time costs. Operations Research Letters, 2001, vol. 28, no. 4, pp. 149-154.
115. Ballestin F., Valls V., Quintanilla S. Pre-emption in resource-constrained project scheduling. European Journal of Operational Research, 2008, vol. 189, no. 3, pp. 1136-1152.
116. Möhring R. H., Schulz A. S., Stork F., Uetz M. Solving project scheduling problems by minimum cut computations. Management Science, 2003, vol. 49, no. 3, pp. 330-350.
117. Buddhakulsomsiria J., Kim D. S. Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting. European Journal of Operational Research, 2006, vol. 175, no. 1, pp. 279-295.
118. Achuthan N., Hardjawidjaja A. Project scheduling under time dependent costs – A branch and bound algorithm. Annals of Operations Research, 2001, vol. 108, no. 1-4, pp. 55-74.
119. Buddhakulsomsiria J., Kim D. S. Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting. European Journal of Operational Research, 2007, vol. 178, no. 2, pp. 374-390.
120. Dodin B., Elimam A. A. Integrated project scheduling and material planning with variable activity duration and rewards. IIE Transactions, 2001, vol. 33, no. 11, pp. 1005-1018.
121. Franck B., Neumann K., Schwindt C. Project scheduling with calendars. OR Spektrum, 2001, vol. 23, no. 3, pp. 325-334.
122. Nonobe K., Ibaraki T. A metaheuristic approach to the resource constrained project scheduling with variable activity durations and convex cost functions. Chapter from book [[158]], pp. 225-248.
123. Drezet L. E., Billaut J. C. A project scheduling problem with labour constraints and time-dependent activities requirements. International Journal of Production Economics, 2008, vol. 112, no. 1, pp. 217-225.
124. Rummel J. L., Walter Z., Dewan R., Seidmann A. Activity consolidation to improve responsiveness. European Journal of Operational Research, 2005, vol. 161, no. 3, pp. 683-703.
125. Cavalcante C. C. B., pp. de Souza C., Savelsbergh M. W. P., Wang Y., Wolsey L. A. Scheduling projects with labor constraints. Discrete Applied Mathematics, 2001, vol. 112, no. 1-3, pp. 27-52.
126. Kimms A. Maximizing the net present value of a project under resource constraints using a lagrangian relaxation based heuristic with tight upper bounds. Annals of Operations Research, 2001, vol. 102, no. 1-4, pp. 221-236.
127. Mika M., Waligora G., Weglarz J. Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times. European Journal of Operational Research, 2008, vol. 187, no. 3, pp. 1238-1250.
128. Mika M., Waligora G., Weglarz J. Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models. European Journal of Operational Research, 2005, vol. 164, no. 3, pp. 639-668.
129. Mika M., Waligora G., Weglarz J. Modelling setup times in project scheduling. Chapter from book [[158]], pp. 131-165.
130. Padman R., Zhu D. Knowledge integration using problem spaces: A study in resource-constrained project scheduling. Journal of Scheduling, 2006, vol. 9, no. 2, pp. 133-152.
131. Drexl A., Nissen R., Patterson J. H., Salewski F. Progen/πx – An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions. European Journal of Operational Research, 2000, vol. 125, no. 1, pp. 59-72.
132. Vanhoucke M., Demeulemeester E. L., Herroelen W. S. On maximizing the net present value of a project under renewable resource constraints. Management Science, 2001, vol. 47, no. 8, pp. 1113-1121.
133. Vanhoucke M. Setup times and fast tracking in resource-constrained project scheduling. Computers and Industrial Engineering, 2008, vol. 54, no. 4, pp. 1062-1070.
134. Varma V. A., Uzsoy R., Pekny J., Blau G. Lagrangian heuristics for scheduling new product development projects in the pharmaceutical industry. Journal of Heuristics, 2007, vol. 13, no. 5, pp. 403-433.
135. Elmaghraby S. E. Activity networks: Project planning and control by network models. Wiley, New York, USA, 1977, 443 p.
136. Najafi A. A., Niaki S. T. A. A genetic algorithm for resource investment problem with discounted cash flows. Applied Mathematics and Computation, 2006, vol. 183, no. 2, pp. 1057-1070.
137. Alcaraz J., Maroto C., Ruiz R. Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms. Journal of the Operational Research Society, 2003, vol. 54, no. 6, pp. 614-626.
138. Herroelen W. S., P. van Dommelen, Demeulemeester E. L. Project network models with discounted cash flows: A guided tour through recent developments. European Journal of Operational Research, 1997, vol. 100, no. 1, pp. 97-121.
139. Bouleimen K., Lecocq H. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European Journal of Operational Research, 2003, vol. 149, no. 2, pp. 268-281.
140. Dayanand N., Padman R. On modelling payments in projects. Journal of the Operational Research Society, 1997, vol. 48, no. 9, pp. 906-918.
141. Hartmann S. Project scheduling with multiple modes: A genetic algorithm. Annals of Operations Research, 2001, vol. 102, no. 1-4, pp. 111-135.
142. Etgar R., Shtub A., LeBlanc L. J. Scheduling projects to maximize net present value – the case of time-dependent, contingent cash flows. European Journal of Operational Research, 1997, vol. 96, no. 1, pp. 90-96.
143. Jarboui B., Damak N., Siarry P., Rebai A. A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. Applied Mathematics and Computation, 2008, vol. 195, no. 1, pp. 299-308.
144. Hapke M., Jaszkiewicz A., Slowinski R. Interactive analysis of multiple-criteria project scheduling problems. European Journal of Operational Research, 1998, vol. 107, no. 2, pp. 315-324.
145. Jozefowska J., Mika M., Rozycki R., Waligora G., Weglarz J. Simulated annealing for multi-mode resource-constrained project scheduling. Annals of Operations Research, 2001, vol. 102, no. 1-4, pp. 137-155.
146. Slowinski R., Soniewicki B., Weglarz J. DSS for multiobjective project scheduling. European Journal of Operational Research, 1994, vol. 79, no. 2, pp. 220-229.
147. Özdamar L. A genetic algorithm approach to a general category project scheduling problem. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 1999, vol. 29, no. 1, pp. 44-59.
148. Dörner K. F., Gutjahr W. J., Hartl R. F., Strauss C., Stummer C. Nature-inspired metaheuristics for multiobjective activity crashing. Omega, 2008, vol. 36, no. 6, pp. 1019-1037.
149. Calhoun K. M., Deckro R. F., Moore J. T., Chrissis J. W., Hove J. C. V. Planning and re-planning in project and production scheduling. Omega, 2002, vol. 30, no. 3, pp. 155-170.
150. Nabrzynski J., Weglarz J. Knowledge-based multiobjective project scheduling problems. Chapter from book [[159]], pp. 383-411.
151. B. de Reyck, Herroelen W. S. The multi-mode resource-constrained project scheduling problem with generalized precedence relations. European Journal of Operational Research, 1999, vol. 119, no. 2, pp. 538-556.
152. Muth J. F., Thompson G. L. (eds.) Industrial Scheduling. Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1963, 467 p.
153. Heilmann R. Resource-constrained project scheduling: A heuristic for the multi-mode case. OR Spektrum, 2001, vol. 23, no. 3, pp. 335-357.
154. Jozefowska J., Weglarz J. (eds.) Perspectives in Modern Project Scheduling. Springer Science & Business Media, New York, USA, 2006, 466 p.
155. Heilmann R. A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags. European Journal of Operational Research, 2003, vol. 144, no. 2, pp. 348-365.
156. Weglarz J. (eds.) Project Scheduling: Recent Models, Algorithms and Applications. Springer, New York, USA, 1999, 535 p.
157. Li H., Womer K. Modeling the supply chain configuration problem with resource constraints. International Journal of Project Management, 2008, vol. 26, no. 6, pp. 646-654.
158. Tiwari V., Patterson J. H., Mabert V. A. Scheduling projects with heterogeneous resources to meet time and quality objectives. European Journal of Operational Research, 2009, vol. 193, no. 3, pp. 780-790.
159. Tareghian H. R., Taheri S. H. A solution procedure for the discrete time, cost and quality tradeoff problem using electromagnetic scatter search. Applied Mathematics and Computation, 2007, vol. 190, no. 2, pp. 1136-1145.
160. Salewski F., Schirmer A., Drexl A. Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application. European Journal of Operational Research, 1997, vol. 102, no. 1, pp. 88-110.
161. Demeulemeester E. L., B. de Reyck, Herroelen W. S. The discrete time/resource trade-off problem in project networks – A branch-and-bound approach. IIE Transactions, 2000, vol. 32, no. 11, pp. 1059-1069.
162. Ranjbar M., Kianfar F. Solving the discrete time/resource trade-off problem in project scheduling with genetic algorithms. Applied Mathematics and Computation, 2007, vol. 191, no. 2, pp. 451-456.
163. Ranjbar M., B. de Reyck, Kianfar F. A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling. European Journal of Operational Research, 2009, vol. 193, no. 1, pp. 35-48.
164. Akkan C., Drexl A., Kimms A. Network decomposition-based benchmark results for the discrete time-cost tradeoff problem. European Journal of Operational Research, 2005, vol. 165, no. 2, pp. 339-358.
165. Demeulemeester E. L., B. de Reyck, Foubert B., Herroelen W. S., Vanhoucke M. New computational results on the discrete time/cost trade-off problem in project networks. Journal of the Operational Research Society, 1998, vol. 49, no. 11, pp. 1153-1163.
166. Deckro R. F., Hebert J. E., Verdini W. A., Grimsrud P. H., Venkateshwar S. Nonlinear time/cost tradeoff models in project management. Computers and Industrial Engineering, 1995, vol. 28, no. 2, pp. 219-229.
167. Chassiakos A. P., Sakellaropoulos S. P. Time-cost optimization of construction projects with generalized activity constraints. Journal of Construction Engineering and Management, 2005, vol. 131, no. 10, pp. 1115-1124.
168. Klein R., Scholl A. PROGRESS: Optimally solving the generalized resource-constrained project scheduling problem. Mathematical Methods of Operations Research, 2000, vol. 52, no. 3, pp. 467-488.
169. Kolisch R. Integrated scheduling, assembly area- and part-assignment for large-scale, make-to-order assemblies. International Journal of Production Economics, 2000, vol. 64, no. 1-3, pp. 127-141.
170. Vanhoucke M. Work continuity constraints in project scheduling. Journal of Construction Engineering and Management, 2006, vol. 132, no. 1, pp. 14-25.
171. Demeulemeester E. L., Herroelen W. S. Modelling setup times, process batches and transfer batches using activity network logic. European Journal of Operational Research, 1996, vol. 89, no. 2, pp. 355-365.
172. Cesta A., Oddi A., Smith S. F. A constraint-based method for project scheduling with time windows. Journal of Heuristics, 2002, vol. 8, no. 1, pp. 109-136.
173. Dorndorf U., Pesch E., Phan Huy T. A time-oriented branch-and-bound algorithm for resource-constrained project scheduling with generalized precedence constraints. Management Science, 2000, vol. 46, no. 10, pp. 1365-1384.
174. Schwindt C. Generation of resource-constrained project scheduling problems subject to temporal constraints. Technical Report WIOR-543, Universität Karlsruhe, Germany, 1998.
175. Neumann K., Zimmermann J. Exact and truncated branch-and-bound procedures for resource-constrained project scheduling with discounted cash flows and general temporal constraints. Central European Journal of Operations Research, 2002, vol. 10, no. 4, pp. 357-380.
176. Neumann K., Zimmermann J. Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints. European Journal of Operational Research, 2000, vol. 127, no. 2, pp. 425-443.
177. Neumann K., Schwindt C., Zimmermann J. Recent results on resource-constrained project scheduling with time windows: Models, solution methods, and applications. Central European Journal of Operations Research, 2002, vol. 10, no. 2, pp. 113-148.
178. Sabzehparvar M., Seyed-Hosseini S. M. A mathematical model for the multi-mode resource-constrained project scheduling problem with mode dependent time lags. Journal of Supercomputing, 2008, vol. 44, no. 3, pp. 257-273.
179. Franck B., Neumann K. Resource-constrained project scheduling with time windows: Structural questions and priority rule methods. Technical Report WIOR-492, Universität Karlsruhe, Germany, 1997.
180. Ballestin F., Valls V., Quintanilla S. Due dates and RCPSP. Chapter from book [[158]], pp. 79-104.
181. Brânzei R., Ferrari G., Fragnelli V., Tijs S. Two approaches to the problem of sharing delay costs in joint projects. Annals of Operations Research, 2002, vol. 109, no. 1-4, pp. 359-374.
182. Chiu H. N., Tsai D. M. An efficient search procedure for the resource-constrained multi-project scheduling problem with discounted cash flows. Construction Management and Economics, 2002, vol. 20, no. 1, pp. 55-66.
183. Özdamar L., Ulusoy G., Bayyigit M. A heuristic treatment of tardiness and net present value criteria in resource constrained project scheduling. International Journal of Physical Distribution and Logistics Management, 1998, vol. 28, no. 9/10, pp. 805-824.
184. Baptiste P., Pape C. L., Nuijten W. Satisfiability tests and time-bound adjustments for cumulative scheduling problems. Annals of Operations Research, 1999, vol. 92, pp. 305-333.
185. Yang H. H., Chen Y. L. Finding the critical path in an activity network with time-switch constraints. European Journal of Operational Research, 2000, vol. 120, no. 3, pp. 603-613.
186. Vanhoucke M., Demeulemeester E. L., Herroelen W. S. Discrete time/cost trade-offs in project scheduling with time-switch constraints. Journal of the Operational Research Society, 2002, vol. 53, no. 7, pp. 741-751.
187. Krüger D., Scholl A. Managing and modelling general resource transfers in (multi-)project scheduling. OR Spektrum, 2010, vol. 32, no. 2, pp. 369-394.
188. Elmaghraby S. E. An algebra for the analysis of generalized activity networks. Management Science, 1964, vol. 10, no. 3, pp. 494-514.
189. Belhe U., Kusiak A. Resource-constrained scheduling of hierarchically structured design activity networks. IEEE Transactions on Engineering Management, 1995, vol. 42, no. 2, pp. 150-158.
190. Neumann K. Stochastic project networks: Temporal analysis, scheduling and cost minimization. Series: Lecture Notes in Economics and Mathematical Systems, vol. 344, Springer, Berlin, Germany, 1990, 237 p.
191. Kuster J., Jannach D. Handling airport ground processes based on resource-constrained project scheduling. Lecture Notes in Computer Science, 2006, vol. 4031, pp. 166-176.
192. Viana A., P. de Sousa J. Using metaheuristics in multiobjective resource constrained project scheduling. European Journal of Operational Research, 2000, vol. 120, no. 2, pp. 359-374.
193. Vanhoucke M., Demeulemeester E. L., Herroelen W. S. An exact procedure for the resource-constrained weighted earliness-tardiness project scheduling problem. Annals of Operations Research, 2001, vol. 102, no. 1-4, pp. 179-196.
194. Franck B., Schwindt C. Different resource-constrained project scheduling models with minimal and maximal time-lags. Technical Report WIOR-450, Universität Karlsruhe, Germany, 1995.
195. Lorenzoni L. L., Ahonen H., G. de Alvarenga A. A multi-mode resource-constrained scheduling problem in the context of port operations. Computers and Industrial Engineering, 2006, vol. 50, no. 1-2, pp. 55-65.
196. Vanhoucke M. Scheduling an R&D project with quality-dependent time slots. Lecture Notes in Computer Science, 2006, vol. 3982, pp. 621-630.
197. Rom W. O., Tukel O. I., Muscatello J. R. MRP in a job shop environment using a resource constrained project scheduling model. Omega, 2002, vol. 30, no. 4, pp. 275-286.
198. Nazareth T., Verma S., Bhattacharya S., Bagchi A. The multiple resource constrained project scheduling problem: A breadth-first approach. European Journal of Operational Research, 1999, vol. 112, no. 2, pp. 347-366.
199. Al-Fawzan M., Haouari M. A bi-objective model for robust resource-constrained project scheduling. International Journal of Production Economics, 2005, vol. 96, no. 2, pp. 175-187.
200. Abbasi B., Shadrokh S., Arkat J. Bi-objective resource-constrained project scheduling with robustness and makespan criteria. Applied Mathematics and Computation, 2006, vol. 180, no. 1, pp. 146-152.
201. Kobylanski P., Kuchta D. A note on the paper by M. A. Al-Fawzan and M. Haouari about a bi-objective problem for robust resource-constrained project scheduling. International Journal of Production Economics, 2007, vol. 107, no. 2, pp. 496-501.
202. Chtourou H., Haouari M. A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling. Computers and Industrial Engineering, 2008, vol. 55, no. 1, pp. 183-194.
203. Icmeli-Tukel O., Rom W. O. Ensuring quality in resource constrained project scheduling. European Journal of Operational Research, 1997, vol. 103, no. 3, pp. 483-496.
204. Van de Vonder S., Demeulemeester E. L., Herroelen W. S. A classification of predictive-reactive project scheduling procedures. Journal of Scheduling, 2007, vol. 10, no. 3, pp. 195-207.
205. Sakkout H., Wallace M. Probe backtrack search for minimal perturbation in dynamic scheduling. Constraints, 2000, vol. 5, no. 4, pp. 359-388.
206. Zhu G., Bard J. F., Yu G. Disruption management for resource-constrained project scheduling. Journal of the Operational Research Society, 2005, vol. 56, pp. 365-381.
207. Neumann K., Schwindt C., Zimmermann J. Resource-constrained project scheduling with time windows: Recent developments and new applications. Chapter from book [[158]], pp. 375-407.
208. Drexl A., Kimms A. Optimization guided lower and upper bounds for the resource investment problem. Journal of the Operational Research Society, 2001, vol. 52, no. 3, pp. 340-351.
209. Ranjbar M., Kianfar F., Shadrokh S. Solving the resource availability cost problem in project scheduling by path relinking and genetic algorithm. Applied Mathematics and Computation, 2008, vol. 196, no. 2, pp. 879-888.
210. Yamashita D. S., Armentano V. A., Laguna M. Robust optimization models for project scheduling with resource availability cost. Journal of Scheduling, 2007, vol. 10, no. 1, pp. 67-76.
211. Shadrokh S., Kianfar F. A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty. European Journal of Operational Research, 2007, vol. 181, no. 1, pp. 86-101.
212. Nübel H. The resource renting problem subject to temporal constraints. OR-Spektrum, 2001, vol. 23, no. 3, pp. 359-381.
213. Ballestin F. A genetic algorithm for the resource renting problem with minimum and maximum time lags. Lecture Notes in Computer Science, 2007, vol. 4446, pp. 25-35.
214. Bandelloni M., Tucci M., Rinaldi R. Optimal resource leveling using non-serial dynamic programming. European Journal of Operational Research, 1994, vol. 78, no. 2, pp. 162-177.
215. Davis K. R., Stam A., Grzybowski R. A. Resource constrained project scheduling with multiple objectives: A decision support approach. Computers and Operations Research, 1992, vol. 19, no. 7, pp. 657-669.
216. Maniezzo V., Mingozzi A. The project scheduling problem with irregular starting time costs. Operations Research Letters, 1999, vol. 25, no. 4, pp. 175-182.
217. Möhring R. H., Schulz A. S., Stork F., Uetz M. On project scheduling with irregular starting time costs. Operations Research Letters, 2001, vol. 28, no. 4, pp. 149-154.
218. Möhring R. H., Schulz A. S., Stork F., Uetz M. Solving project scheduling problems by minimum cut computations. Management Science, 2003, vol. 49, no. 3, pp. 330-350.
219. Achuthan N., Hardjawidjaja A. Project scheduling under time dependent costs – A branch and bound algorithm. Annals of Operations Research, 2001, vol. 108, no. 1-4, pp. 55-74.
220. Dodin B., Elimam A. A. Integrated project scheduling and material planning with variable activity duration and rewards. IIE Transactions, 2001, vol. 33, no. 11, pp. 1005-1018.
221. Nonobe K., Ibaraki T. A metaheuristic approach to the resource constrained project scheduling with variable activity durations and convex cost functions. Chapter from book [[158]], pp. 225-248.
222. Rummel J. L., Walter Z., Dewan R., Seidmann A. Activity consolidation to improve responsiveness. European Journal of Operational Research, 2005, vol. 161, no. 3, pp. 683-703.
223. Kimms A. Maximizing the net present value of a project under resource constraints using a lagrangian relaxation based heuristic with tight upper bounds. Annals of Operations Research, 2001, vol. 102, no. 1-4, pp. 221-236.
224. Mika M., Waligora G., Weglarz J. Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models. European Journal of Operational Research, 2005, vol. 164, no. 3, pp. 639-668.
225. Padman R., Zhu D. Knowledge integration using problem spaces: A study in resource-constrained project scheduling. Journal of Scheduling, 2006, vol. 9, no. 2, pp. 133-152.
226. Vanhoucke M., Demeulemeester E. L., Herroelen W. S. On maximizing the net present value of a project under renewable resource constraints. Management Science, 2001, vol. 47, no. 8, pp. 1113-1121.
227. Varma V. A., Uzsoy R., Pekny J., Blau G. Lagrangian heuristics for scheduling new product development projects in the pharmaceutical industry. Journal of Heuristics, 2007, vol. 13, no. 5, pp. 403-433.
228. Najafi A. A., Niaki S. T. A. A genetic algorithm for resource investment problem with discounted cash flows. Applied Mathematics and Computation, 2006, vol. 183, no. 2, pp. 1057-1070.
229. Herroelen W. S., P. van Dommelen, Demeulemeester E. L. Project network models with discounted cash flows: A guided tour through recent developments. European Journal of Operational Research, 1997, vol. 100, no. 1, pp. 97-121.
230. Dayanand N., Padman R. On modelling payments in projects. Journal of the Operational Research Society, 1997, vol. 48, no. 9, pp. 906-918.
231. Etgar R., Shtub A., LeBlanc L. J. Scheduling projects to maximize net present value – the case of time-dependent, contingent cash flows. European Journal of Operational Research, 1997, vol. 96, no. 1, pp. 90-96.
232. Hapke M., Jaszkiewicz A., Slowinski R. Interactive analysis of multiple-criteria project scheduling problems. European Journal of Operational Research, 1998, vol. 107, no. 2, pp. 315-324.
233. Slowinski R., Soniewicki B., Weglarz J. DSS for multiobjective project scheduling. European Journal of Operational Research, 1994, vol. 79, no. 2, pp. 220-229.
234. Dörner K. F., Gutjahr W. J., Hartl R. F., Strauss C., Stummer C. Nature-inspired metaheuristics for multiobjective activity crashing. Omega, 2008, vol. 36, no. 6, pp. 1019-1037.
235. Nabrzynski J., Weglarz J. Knowledge-based multiobjective project scheduling problems. Chapter from book [[159]], pp. 383-411.
236. Muth J. F., Thompson G. L. (eds.) Industrial Scheduling. Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1963, 467 p.
237. Jozefowska J., Weglarz J. (eds.) Perspectives in Modern Project Scheduling. Springer Science & Business Media, New York, USA, 2006, 466 p.
238. Weglarz J. (eds.) Project Scheduling: Recent Models, Algorithms and Applications. Springer, New York, USA, 1999, 535 p.
Review
For citations:
Anichkin A.S., Semenov V.A. A survey of emerging models and methods of scheduling. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(3):5-50. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(3)-1
Email this article 