Resource Management in Machine Scheduling Problems: A Survey
DOI:
https://doi.org/10.7494/dmms.2007.1.2.59Keywords:
scheduling, resource allocation, resource dependent processing times, resource dependent release datesAbstract
The paper is a survey devoted to job scheduling problems with resource allocation. We present the results available in the scientific literature for commonly used models of job processing times and job release dates, i.e., the models in which the job processing time or the job release date is given as a linear or convex function dependent on the amount of the additional resource allotted to the job. The scheduling models with resource dependent processing times or resource dependent release dates extend the classical scheduling models to reflect more precisely scheduling problems that appear in real life. Thus, in this paper we present the computational complexity results and solution algorithms that have been developed for this kind of problems.
References
Alidaee B. & Ahmadian A. (1993). Two parallel machine sequencing problems involving controllable job processing times. European Journal of Operational Research, 70(3), pp. 335–341. DOI: https://doi.org/10.1016/0377-2217(93)90245-I
Błażewicz J., Ecker K.H., Pesch E., Schmidt G. & Węglarz J. (2001). Scheduling Computer and Manufacturing Processes. 2nd Edition. Berlin–Heidelberg: Springer. DOI: https://doi.org/10.1007/978-3-662-04363-9
Chen Z.-L. (2004). Simultaneous job scheduling and resource allocation on parallel machines. Annals of Operations Research, 129, pp. 135–153. DOI: https://doi.org/10.1023/B:ANOR.0000030685.31167.11
Chen Z.-L., Lu Q. & Tang G. (1997). Single machine scheduling with discretely controllable processing times. Operations Research Letters, 21(2), pp. 69–76. DOI: https://doi.org/10.1016/S0167-6377(97)00010-2
Cheng T.C.E., Chen Z.-L. & Li C.-L. (1996). Parallel-machine scheduling with controllable processing times. IIE Transactions, 28(2), pp. 177–180. DOI: https://doi.org/10.1080/07408179608966263
Cheng T.C.E., Chen Z.-L. & Li C.-L. (1996). Single-machine scheduling with trade-off between number of tardy jobs and resource allocation. Operations Research Letters, 19(5), pp. 237–242. DOI: https://doi.org/10.1016/S0167-6377(96)00035-1
Cheng T.C.E., Chen Z.-L., Li C.-L. & Lin B.M.-T. (1998). Scheduling to minimize the total compression and late costs. Naval Research Logistics, 45(1), pp. 67–82. DOI: https://doi.org/10.1002/%28SICI%291520-6750%28199802%2945%3A1%3C67%3A%3AAID-NAV4%3E3.0.CO%3B2-J
Cheng T.C.E. & Janiak A. (1994). Resource optimal control in some single-machine scheduling problems. IEEE Transactions on Automatic Control, 39(6), pp. 1243–1246. DOI: https://doi.org/10.1109/9.293187
Cheng T.C.E. & Janiak A. (2000). A permutation flow-shop scheduling problem with convex models of operation processing times. Annals of Operations Research, 96, pp. 39–60. DOI: https://doi.org/10.1023/A:1018943300630
Cheng T.C.E., Janiak A. & Kovalyov M.Y. (1998). Bicriterion single machine scheduling with resource dependent processing times. SIAM Journal on Optimization, 8(2), pp. 617–630. DOI: https://doi.org/10.1137/S1052623495288192
Cheng T.C.E. & Kovalyov M.Y. (1995). Single machine batch scheduling with deadlines and resource dependent processing times. Operations Research Letters, 17(5), pp. 243–249. DOI: https://doi.org/10.1016/0167-6377(95)00011-8
Cheng T.C.E., Oğuz C. & Qi X.D. (1996). Due-date assignment and single machine scheduling with compressible processing times. International Journal of Production Economics, 43(2–3), pp. 107–113. DOI: https://doi.org/10.1016/0925-5273(96)00041-2
Cheng T.C.E. & Shakhlevich N.V. (1999). Proportionate flow shop with controllable processing times. Journal of Scheduling, 2(6), pp. 253–265. DOI: https://doi.org/10.1002/%28SICI%291099-1425%28199911%2F12%292%3A6%3C253%3A%3AAID-JOS30%3E3.0.CO%3B2-R
Garey M.R. & Johnson D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman.
Garey M.R., Johnson D.S. & Sethi R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), pp. 117–129. DOI: https://doi.org/10.1287/moor.1.2.117
Grabowski J. & Janiak A. (1987). Job-shop scheduling with resource-time models of operations. European Journal of Operational Research, 28(1), pp. 58–73. DOI: https://doi.org/10.1016/0377-2217(87)90169-X
Graham R.L., Lawler E.L., Lenstra J.K. & Rinnooy Kan A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling theory: A survey. Annals of Discrete Mathematics, 5, pp. 287–326. DOI: https://doi.org/10.1016/S0167-5060(08)70356-X
Hamacher H.W. & Tufekci S. (1984). Algebraic flows and time-cost tradeoff problems. Annals of Discrete Mathematics, 19, pp. 165–182. DOI: https://doi.org/10.1016/S0304-0208(08)72961-X
Jackson J.R. (1955). Scheduling a Production Line to Minimize Maximum Tardiness. Management Sciences Research Project, Research Report No. 43. Los Angeles: University of California.
Janiak A. (1986). Job scheduling problems on a single machine with resource allocation [in Polish]. Zeszyty Naukowe Politechniki Śląskiej, seria Automatyka, 84(894), pp. 81–92.
Janiak A. (1982). Job-shop scheduling with resource constraints. In: Proceedings of the International AMSE Conference: Modelling and Simulation, vol. 2, pp. 97–110.
Janiak A. (1986). On a single machine sequencing to minimize the maximum job cost subject to resource and precedence constraints. Archiwum Automatyki i Telemechaniki, 31(4), pp. 415–417.
Janiak A. (1986). One-machine scheduling problems with resource constraints. In: System Modelling and Optimization. Lecture Notes in Control and Information Sciences, 84, pp. 358–364. Berlin–Heidelberg: Springer. DOI: https://doi.org/10.1007/BFb0043857
Janiak A. (1986). Time-optimal control in a single machine problem with resource constraints. Automatica, 22(6), pp. 745–747. DOI: https://doi.org/10.1016/0005-1098(86)90014-2
Janiak A. (1987). Minimization of the maximum tardiness in one-machine scheduling problem subject to precedence and resource constraints. International Journal of Systems Analysis, Modelling and Simulation, 4(6), pp. 549–556.
Janiak A. (1987). One-machine scheduling with allocation of continuously-divisible resource and with no precedence constraints. Kybernetika, 23(4), pp. 289–293.
Janiak A. (1988). General flow-shop scheduling with resource constraints. International Journal of Production Research, 26(6), pp. 1089–1103. DOI: https://doi.org/10.1080/00207548808947920
Janiak A. (1988). Minimization of the total resource consumption in permutation flow-shop sequencing subject to a given makespan. Journal of Modelling, Simulation and Control, 13(2), pp. 1–11.
Janiak A. (1988). Single machine sequencing with linear models of jobs subject to precedence constraints. Archiwum Automatyki i Telemechaniki, 33(2), pp. 203–210.
Janiak A. (1989). Minimization of resource consumption under a given deadline in the two-processor flow-shop scheduling problem. Information Processing Letters, 32(3), pp. 101–112. DOI: https://doi.org/10.1016/0020-0190(89)90009-4
Janiak A. (1989). Minimization of the blooming mill standstills—mathematical model, suboptimal algorithms. Mechanika AGH, 8(2), pp. 37–49.
Janiak A. (1991). Exact and Approximate Algorithms of Job Sequencing and Resource Allocation in Discrete Manufacturing Processes [in Polish]. Prace Naukowe Instytutu Cybernetyki Technicznej Politechniki Wrocławskiej, Monografie, 87(20). Wrocław: Wydawnictwo Politechniki Wrocławskiej.
Janiak A. (1991). Single machine scheduling problem with a common deadline and resource dependent release dates. European Journal of Operational Research, 53(3), pp. 317–325. DOI: https://doi.org/10.1016/0377-2217(91)90065-4
Janiak A. (1995). Single machine scheduling problem with precedence and resource constraints [in Polish]. Zeszyty Naukowe Politechniki Śląskiej, seria Automatyka, 116(1296), pp. 31–47.
Janiak A. (1996). Analysis of computational complexity of single machine scheduling problems with release dates dependent on resources [in Polish]. Zeszyty Naukowe Politechniki Śląskiej, seria Automatyka, 117(1337), pp. 69–84.
Janiak A. (1997). Computational complexity analysis of single machine scheduling problems with job release dates dependent on resources. In: Proceedings of the Symposium on Operations Research (SOR ’96), Braunschweig, Germany, September 3–6, 1996, pp. 203–207. Berlin–Heidelberg: Springer. DOI: https://doi.org/10.1007/978-3-642-60744-8_37
Janiak A. (1998). Minimization of the makespan in a two-machine problem under given resource constraints. European Journal of Operational Research, 107(2), pp. 325–337. DOI: https://doi.org/10.1016/S0377-2217(97)00343-3
Janiak A. (1998). Single machine sequencing with linear models of release dates. Naval Research Logistics, 45(1), pp. 99–113. DOI: https://doi.org/10.1002/%28SICI%291520-6750%28199802%2945%3A1%3C99%3A%3AAID-NAV6%3E3.0.CO%3B2-G
Janiak A. (1999). Selected Problems and Algorithms for Task Scheduling and Resource Allocation [in Polish]. Problemy Współczesnej Nauki. Teoria i Zastosowania – Informatyka. Warszawa: Akademicka Oficyna Wydawnicza PLJ.
Janiak A. & Chudzik K. (1997). Classical genetic approach to some flow-type manufacturing problem. In: Proceedings of the Fourth International Symposium on Methods and Models in Automation and Robotics (MMAR ’97), Międzyzdroje, Poland, August 26–29, 1997, vol. 3, pp. 1077–1082.
Janiak A. & Grabowski J. (1980). Optimization problems of scheduling with resource allocation in manufacturing processes [in Russian]. In: Proceedings of the VII Polish-Bulgarian Symposium, Warsaw, pp. 129–138.
Janiak A. & Kovalyov M.Y. (1996). Single machine scheduling subject to deadlines and resource dependent processing times. European Journal of Operational Research, 94(2), pp. 284–291. DOI: https://doi.org/10.1016/0377-2217(96)00129-4
Janiak A., Kovalyov M.Y., Kubiak W. & Werner F. (2005). Positive half-products and scheduling with controllable processing times. European Journal of Operational Research, 165(2), pp. 416–422. DOI: https://doi.org/10.1016/j.ejor.2004.04.012
Janiak A. & Li C.-L. (1994). Scheduling to minimize the total weighted completion time with a constraint on the release time resource consumption. Mathematical and Computer Modelling, 20(2), pp. 53–58. DOI: https://doi.org/10.1016/0895-7177(94)90206-2
Janiak A. & Lichtenstein M. (2004). Optimal resource distribution in scheduling problems with resource dependent setup and processing times. In: Proceedings of the 10th IEEE International Conference on Methods and Models in Automation and Robotics (MMAR 2004), Międzyzdroje, Poland, August 30–September 2, 2004, vol. 2.
Janiak A. & Portmann M.-C. (1998). Genetic algorithm for the permutation flow-shop scheduling problem with linear models of operations. Annals of Operations Research, 83, pp. 95–114. DOI: https://doi.org/10.1023/A:1018924517216
Janiak A. & Szkodny T. (1994). Job-shop scheduling with convex models of operations. Mathematical and Computer Modelling, 20(2), pp. 59–68. DOI: https://doi.org/10.1016/0895-7177(94)90207-0
Jansen K., Mastrolilli M. & Solis-Oba R. (2005). Approximation schemes for job shop scheduling problems with controllable processing times. European Journal of Operational Research, 167(2), pp. 297–319. DOI: https://doi.org/10.1016/j.ejor.2004.03.025
Jansen K. & Mastrolilli M. (2004). Approximation schemes for parallel machine scheduling problems with controllable processing times. Computers & Operations Research, 31(10), pp. 1565–1581. DOI: https://doi.org/10.1016/S0305-0548(03)00101-1
Johnson S.M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), pp. 61–68. DOI: https://doi.org/10.1002/nav.3800010110
Józefowska J. & Węglarz J. (1996). Discrete-continuous scheduling problems—mean completion time results. European Journal of Operational Research, 94(2), pp. 302–309. DOI: https://doi.org/10.1016/0377-2217(96)00130-0
Józefowska J. & Węglarz J. (1998). On a methodology for discrete-continuous scheduling. European Journal of Operational Research, 107(2), pp. 338–353. DOI: https://doi.org/10.1016/S0377-2217(97)00346-9
Karmarkar N. (1984). A new polynomial-time algorithm for linear programming. Combinatorica, 4(4), pp. 373–395. DOI: https://doi.org/10.1007/BF02579150
Kaspi M. & Shabtay D. (2006). A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates. Computers & Operations Research, 33(10), pp. 3015–3033. DOI: https://doi.org/10.1016/j.cor.2005.02.032
Khachiyan L.G. (1979). A polynomial algorithm in linear programming. Soviet Mathematics Doklady, 20(1), pp. 191–194.
Kovalyov M.Y. (1995). Improving the complexities of approximation algorithms for optimization problems. Operations Research Letters, 17(2), pp. 85–87. DOI: https://doi.org/10.1016/0167-6377(95)91591-Z
Lee C.-Y. & Lei L. (2001). Multiple-project scheduling with controllable project duration and hard resource constraint: Some solvable cases. Annals of Operations Research, 102, pp. 287–307. DOI: https://doi.org/10.1023/A:1010918518726
Lenstra J.K., Rinnooy Kan A.H.G. & Brucker P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, pp. 343–362. DOI: https://doi.org/10.1016/S0167-5060(08)70743-X
Li C.-L. (1994). Scheduling with resource-dependent release dates—A comparison of two different resource consumption functions. Naval Research Logistics, 41(6), pp. 807–819. DOI: https://doi.org/10.1002/1520-6750%28199410%2941%3A6%3C807%3A%3AAID-NAV3220410609%3E3.0.CO%3B2-8
Li C.-L. (1995). Scheduling to minimize the total resource consumption with a constraint on the sum of completion times. European Journal of Operational Research, 80(2), pp. 381–388. DOI: https://doi.org/10.1016/0377-2217(93)E0255-V
Li C.-L., Sewell E.C. & Cheng T.C.E. (1995). Scheduling to minimize release-time resource consumption and tardiness penalties. Naval Research Logistics, 42(6), pp. 949–966. DOI: https://doi.org/10.1002/1520-6750%28199509%2942%3A6%3C949%3A%3AAID-NAV3220420607%3E3.0.CO%3B2-3
Mastrolilli M. (2003). Notes on max flow time minimization with controllable processing times. Computing, 71(4), pp. 375–386. DOI: https://doi.org/10.1007/s00607-003-0029-z
Moore J.M. (1968). An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15(1), pp. 102–109. DOI: https://doi.org/10.1287/mnsc.15.1.102
Nowicki E. (1993). An approximation algorithm for the m-machine permutation flow shop scheduling problem with controllable processing times. European Journal of Operational Research, 70(3), pp. 342–349. DOI: https://doi.org/10.1016/0377-2217(93)90246-J
Nowicki E. (1994). An approximation algorithm for a single-machine scheduling problem with release times, delivery times and controllable processing times. European Journal of Operational Research, 72(1), pp. 74–81. DOI: https://doi.org/10.1016/0377-2217(94)90331-X
Nowicki E. & Zdrzałka S. (1988). A two-machine flow shop scheduling problem with controllable job processing times. European Journal of Operational Research, 34(2), pp. 208–220. DOI: https://doi.org/10.1016/0377-2217(88)90355-4
Nowicki E. & Zdrzałka S. (1990). A survey of results for sequencing problems with controllable processing times. Discrete Applied Mathematics, 26(2–3), pp. 271–287. DOI: https://doi.org/10.1016/0166-218X(90)90105-L
Nowicki E. & Zdrzałka S. (1995). A bicriterion approach to preemptive scheduling of parallel machines with controllable job processing times. Discrete Applied Mathematics, 63(3), pp. 237–256. DOI: https://doi.org/10.1016/0166-218X(94)00071-5
Panwalkar S.S. & Rajagopalan R. (1992). Single-machine sequencing with controllable processing times. European Journal of Operational Research, 59(2), pp. 298–302. DOI: https://doi.org/10.1016/0377-2217(92)90144-X
Shabtay D. (2004). Single and a two-resource allocation algorithms for minimizing the maximal lateness in a single machine-scheduling problem. Computers & Operations Research, 31(8), pp. 1303–1315. DOI: https://doi.org/10.1016/S0305-0548(03)00081-9
Shabtay D. & Kaspi M. (2004). Minimizing the total weighted flow time in a single machine with controllable processing times. Computers & Operations Research, 31(13), pp. 2279–2289. DOI: https://doi.org/10.1016/S0305-0548(03)00187-4
Shmoys D.B. & Tardos É. (1993). An approximation algorithm for the generalized assignment problem. Mathematical Programming, 62, pp. 461–474. DOI: https://doi.org/10.1007/BF01585178
Smith W.E. (1956). Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1–2), pp. 59–66. DOI: https://doi.org/10.1002/nav.3800030106
Trick M.A. (1994). Scheduling multiple variable-speed machines. Operations Research, 42(2), pp. 234–248. DOI: https://doi.org/10.1287/opre.42.2.234
Tuzikov A.V. (1984). A two-criterion scheduling problem allowing for variation in job execution time. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 24(10), pp. 1585–1590. DOI: https://doi.org/10.1016/0041-5553(84)90181-2
Vasilev S.H. & Foote B.L. (1997). On minimizing resource consumption with constraints on the makespan and the total completion time. European Journal of Operational Research, 96(3), pp. 612–621. DOI: https://doi.org/10.1016/S0377-2217(96)00095-1
Vickson R.G. (1980). Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine. Operations Research, 28(5), pp. 1155–1167. DOI: https://doi.org/10.1287/opre.28.5.1155
Vickson R.G. (1980). Two single machine sequencing problems involving controllable job processing times. AIIE Transactions, 12(3), pp. 258–262. DOI: https://doi.org/10.1080/05695558008974515
Van Wassenhove L.N. & Baker K.R. (1982). A bicriterion approach to time/cost trade-offs in sequencing. European Journal of Operational Research, 11(1), pp. 48–54. DOI: https://doi.org/10.1016/S0377-2217(82)80008-8
Węglarz J. (1980). Multiprocessor scheduling with memory allocation—A deterministic approach. IEEE Transactions on Computers, C-29(8), pp. 703–709. DOI: https://doi.org/10.1109/TC.1980.1675652
Zdrzałka S. (1991). Scheduling jobs on a single machine with release dates, delivery times and controllable processing times: Worst-case analysis. Operations Research Letters, 10(9), pp. 519–524. DOI: https://doi.org/10.1016/0167-6377(91)90071-V
Zhang F., Tang G. & Chen Z.-L. (2001). A 3/2-approximation algorithm for parallel machine scheduling with controllable processing times. Operations Research Letters, 29(1), pp. 41–47. DOI: https://doi.org/10.1016/S0167-6377(01)00080-3
