Resource management in machine scheduling problems: a survey

• Autorzy: Janiak A. , Janiak W. , Lichtenstein M.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

scheduling; resource allocation; resource dependent processing times; resource dependent release dates

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Decision Making in Manufacturing and Services
• Rocznik: 2007
• Tom: Vol. 1, no. 1-2
• Strony: 59--89
• Opis fizyczny: Bibliogr. 83 poz., tab.

Twórcy

autor

Janiak A.

• Institute of Computer Engineering, Wrocław University of Technology, Control and Robotics, Poland

autor

Janiak W.

• A student of the Faculty of Computer Science and Management, Wrocław University of Technology, Poland

autor

Lichtenstein M.

• Institute of Computer Engineering, Wrocław University of Technology, Control and Robotics, Poland

Bibliografia

• 1. B. Alidaee, A. Ahmadian, Two parallel machine sequencing problems involving controllable job processing times, European Journal of Operational Research, 70, (1993), 335–341.
• 2. J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, J. Weglarz, Scheduling Computer and Manufacturing Processes, Springer, Berlin, 2001.
• 3. Z. Chen, Simultaneous job scheduling and resource allocation on parallel machines, Annals of Operations Research, 129, (2004), 135–153.
• 4. Z. Chen, Q. Lu, G. Tang, Single machine scheduling with discretely controllable processing times, Operations Research Letters, 21, (1997), 69–76.
• 5. T. Cheng, Z. Chen, C.-L. Li, Parrallel-machine scheduling with controllable processing times, IIE Transactions, 28.
• 6. T. Cheng, Z.-L. Chen, C.-L. Li, Single-machine scheduling with trade-off between number of tardy jobs and resource allocation, Operations Research Letters, 16, (1996), 237–242.
• 7. T. Cheng, Z.-L. Chen, C.-L. Li, B.-T. Lin, Scheduling to minimize the total compression and late costs, Naval Research Logistics, 45, (1998), 67–82.
• 8. T. Cheng, A. Janiak, Resource optimal control in some single-machine scheduling problems, IEEE Transation on Automatic Control, 39 (6), (1994), 1243–1246.
• 9. T. Cheng, A. Janiak, A permutation flow-shop scheduling problem with convex models of operation processing times, Annals of Operations Research, 96, (2000), 39–60.
• 10. T. Cheng, A. Janiak, M. Kovalyov, Bicriterion single machine scheduling with resource dependent processing times, SIAM Journal of Optimization, 8, (1998), 617–630.
• 11. T. Cheng, M. Kovalyov, Single machine batch scheduling with deadlines and resource dependent processing times, Operations Research Letters, 17, (1995), 243–248.
• 12. T. Cheng, C. Oguz, X. Qi, Due-date assignment and single machine scheduling with compressible processing times, International Journal of Production Economics, 43, (1996), 107–113.
• 13. T. Cheng, N. Shakhlevich, Proportionate flow shop with controllable processing times, Journal of Scheduling, 2, (1999), 253–265.
• 14. M. Garey, D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completness, W.H. Freeman, San Francisco, 1979.
• 15. M. Garey, D. Johnson, R. Sethi, The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1, (1976), 117–129.
• 16. J. Grabowski, A. Janiak, Job-shop scheduling with resource-time models of operations, European Journal of Operational Research, 28, (1987), 58–73.
• 17. R. Graham, E. Lawler, J. Lenstra, A. Rinnoy Kan, Optimization and approximation in deterministic sequencing and scheduling theory: a survey, Annals of Discrete Mathematics, 5, (1979), 287–326.
• 18. H. Hamacher, S. Tufekci, Algebraic flows and time-cost trade off problems, Annals of Discrete Mathematics, 19, (1984), 165–182.
• 19. J. Jackson, Scheduling a production line to minimize maximum tardiness, Management Science Research Project Research report 43, University of California, Los Angeles, CA., 1955.
• 20. A. Janiak, Job scheduling problems on single machine with resource allocation(in Polish), Zeszyty Naukowe Politechniki Slaskiej seria Automatyka, z. 84, 894, (1986), 81–92.
• 21. A. Janiak, Job-shop scheduling with resource constraints, in G. Mesnard, editor, Proceedings of the International AMSE Conference: Modeling and Simulation, 1986, 97–110.
• 22. A. Janiak, On a single machine sequencing to minimize the maximum job cost subject to resource and precedence constraints, Archiwum Automatyki i Telemetryki, t. 31, z. 4, (1986), 415–417.
• 23. A. Janiak, One-machine scheduling problems with resource constraints, Springer-Verlag, volume 84 of Lecture Notes in Control and Information Science, chapter System Modeling and Optimization, 1986.
• 24. A. Janiak, Time-optimal control in a single machine problem with resource constrains, Automatica, 22 (6), (1986), 745–747.
• 25. A. Janiak, Minimization of the maximum tardiness in one-machine scheduling problem subject to precedence and resource constraints, International Journal of System Analysis - Modeling - Simulation, 4 (6), (1987), 549–556.
• 26. A. Janiak, One-machine scheduling with allocation of continuosly-divisable resource and with no precedence constraints, Kybernetika, 23 (4), (1987), 289–293.
• 27. A. Janiak, General flow-shop scheduling with resource constraints, International Journal of Production Research, 26 (6), (1988), 1089–1103.
• 28. A. Janiak, Minimization of the total resource consumption in permutation flow-shop sequencing subject to a given makespan, Journal of Modeling Simulation and Control (AMSE Press), 13 (2), (1988), 1–11.
• 29. A. Janiak, Single machine sequencing with linear models of jobs subject to precedence constraints, Archiwum Automatyki i Telemetryki, 33 (2), (1988), 203–210.
• 30. A. Janiak, Minimalization of the total resource consumption under a given deadline in two-processor flow-shop scheduling problem, Information Processing Letters, 32 (2), (1989), 101–112.
• 31. A. Janiak, Minimization of the blooming mill standstills - mathematical model – suboptimals algorithms, Mechanika AGH, 8 (2), (1989), 37–49.
• 32. A. Janiak, Exact and approximate algorithms of job sequencing and resource allocation in discrete manufacturing pocesses (in Polish), Monografie,Wydawnictwo Politechniki Wroclawskiej, Prace Naukowe Instytutu Cybernetyki Technicznej Politechniki Wroclawskiej edition, 1991.
• 33. A. Janiak, Single machine scheduling problem with a common deadline and resource dependent release dates, European Journal of Operational Research, 53 (3), (1991), 317–325.
• 34. A. Janiak, Single machine scheduling problem with precedence and resource costraints (in Polish), Zeszyty Naukowe Politechniki Slaskiej, seria Automatyka, z. 116, 31–47.
• 35. A. Janiak, Analysis of computational complexity of single machine scheduling problems with release dates dependent on resources(in Polish), Zeszyty Naukowe Politechniki Slaskiej, seria Automatyka, z. 117, 69–84.
• 36. A. Janiak, Computational complexity analysis of single machine scheduling problems with job release dates dependent on resources, in Proceedings of the Symposium on Operations Research (SOR96), Braunschweig, September 3-6, Springer-Verlag, 1997, 203–207.
• 37. A. Janiak, Minimization of the makespan in a two-machine problem under given resource constraints, European Journal of Operational Research, 107, (1998), 325–337.
• 38. A. Janiak, Single machine sequencing with linear models of release dates, Naval Research Logistics, 45, (1998), 99–113.
• 39. A. Janiak, Selected problems and algorithms for task schedulig and Resource Allocation (in Polish), Problemy Wspolczesnej Nauki, Teoria i Zastosowania - Informatyka, Akademicka Oficyna Wydawnicza PLJ, Warszawa, 1999.
• 40. A. Janiak, K. Chudzik, Classical genetic approach to some flow type manufacturing problem, in K. R. Domek S., Emirsajlow A., editor, Proceedings of the Fourth International Symposium on Methods and Models in Automation and Robotics, Miedzyzdroje Poland, 26-29 August,, 1997, vol. 3, pp. 1077–1082.
• 41. A. Janiak, J. Grabowski, Optimization problems of sceduling with resource allocation in manufacturing processes (in Russian), in Proceedings of the VII Polish-Bulgarian Symposium, Warsaw, 1980, 129–138.
• 42. A. Janiak, M. Kovalyov, Single machine scheduling subject to deadlines and resource dependent processing times, European Journal of Operational Research, 94, (1996), 284–291.
• 43. A. Janiak, M. Kovalyov, W. Kubiak, F. Werner, Positive half-products and scheduling with controllable processing times, European Journal of Operational Research, 165, (2005), 416–422.
• 44. A. Janiak, C.-L. Li, Scheduling to minimize the total wighted completion time with a constraint on the release time resource consumption, Mathematics of Computation Modelling, 20 (2), (1994), 53–58.
• 45. A. Janiak, M. Lichtenstein, 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, Miedzyzdroje, Poland, 30 August - 2 September, vol. 2, 2004.
• 46. A. Janiak, M.-C. Portmann, Genetic algorithm for the permutation flow-shop scheduling problem with linear models of operations, Annals of Operation Research, 83, (1998), 95–114.
• 47. A. Janiak, T. Szkodny, Job-shop scheduling with convex models of operations, Mathematics of Computation Modelling, 20 (2), (1994), 59–68.
• 48. K. Jansen, M. Mastrolilli, R. Solis-Oba, Approximation schemes for job shop scheduling problems with controllable processing times, European Journal of Operational Research, 167, (2005), 297–319.
• 49. K. Jansena, M. Mastrolilli, Approximation schemes for parallel machine scheduling problems with controllable processing times, Computers & Operations Research, 31, (2004), 1565–1581.
• 50. S. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, (1954), 61–68.
• 51. J. Jozefowska, J. Weglarz, Discrete-continuous scheduling problems – mean completion time results, European Journal of Operational Research, 94/2, (1996), 302–310.
• 52. J. Jozefowska, J.Weglarz, On a methodology for discrete-continuous scheduling problems, European Journal of Operational Research, 107/2, (1998), 338–353.
• 53. N. Karmarkar, A new polynomial - time algorithm for linear programming, Combinatorica, 4 (4), (1984), 373–395.
• 54. M. Kaspi, D. Shabtay, A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates, Computers & Operations Research, 33, (2006), 3015–3033.
• 55. L. Khachiyan, A polynomial algorithm in linear programming, Soviet Mathematical Doklady, 5 (20), (1979), 191–194.
• 56. M. Kovalyov, Improving the cpmplexities of approximation algorithms for opimization problems, Operations Research Letters, 17, (1995), 85–87.
• 57. C.-Y. Lee, L. Lei, Multiple-project scheduling with controllable project duration and hard resource constraint: Some solvable cases, Annals of Operations Research, 102, (2001), 287–307.
• 58. J. Lenstra, A. Rinnoy Kan, P. Brucker, Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, (1977), 343–362.
• 59. C.-L. Li, Scheduling with resource-dependent release dates - a comparison of two different resource consumption functions, Naval Research Logistics, 41, (1994), 807–819.
• 60. C.-L. Li, Scheduling to minimize the total resource consumption with a constraint on the sum of completion times, European Journal of Operational Research, 80, (1995), 381–388.
• 61. C.-L. Li, E. Sewell, T. Cheng, Scheduling to minimize release-time resource consumption and tardiness penalties, Naval Research Logistics, 42, (1995), 949–966.
• 62. M. Mastrolilli, Notes on max flow time minimization with controllable processing times, Computing, 71, (2003), 375–386.
• 63. J. Moore, An job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15, (1968), 102–109.
• 64. E. Nowicki, An approximation algorithm for the m-machine permutation flow shop scheduling problem with controllable processing times, European Journal of Operational Research, 70, (1993), 342–349.
• 65. E. Nowicki, An approximation algorithm for a single-machine scheduling problem with release times, delivery times and controllable processing times, European Journal of Operational Research, 72, (1994), 74–81.
• 66. E. Nowicki, S. Zdrzalka, A two machine flow shop scheduling problem with controllable job processing times, European Journal of Operational Research, 34, (1988), 208–220.
• 67. E. Nowicki, S. Zdrzalka, A survey of results for sequencing problems with controllable processing times, Discrete Applied Mathematics, 26, (1990), 271–287.
• 68. E. Nowicki, S. Zdrzalka, A bicriterion approach to preemptive scheduling of parallel machines with controllable job processing times, Discrete Applied Mathematics, 63, (1995), 237–256.
• 69. S. Panwalkar, R. Rajagopalan, Single-machine sequencing with controllable processing times, European Journal of Operational Research, 59, (1992), 298–302.
• 70. D. Shabtay, Single and a two-resource allocation algorithms for minimizing the maximal lateness in a single machine-scheduling problem, Computers and Operations Research, 31 (8), (2004), 1303–1315.
• 71. D. Shabtay, M. Kaspi, Minimizing the total weighted flow time in a single machine with controllable processing times, Computers and Operations Research, 31 (13), (2004), 2279–2289.
• 72. D. Shmoys, E. Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming, 62, (1993), 461–474.
• 73. W. Smith, Various optimizers for single-stage production, Naval Research Logistics Quartery, 3, (1956), 59–66.
• 74. M. Trick, Scheduling multiple variable-speed machines, Operations Research, 42 (2), (1994), 234–248.
• 75. A. Tuzikow, O dwuchkriterjalnej zadace teorii raspisanij z ucatom izmienienija dlitelnostej obsluzivanija, Zurnal Vycislitelnoj Matematyki i Matematiceskoj Fizyki, 10, (1984), 1585–1590.
• 76. S. Vasiliev, B. Foote, On minimizing resource consumption with constraints on the makespan and the total completion time, Europenan Journal of Operational Research, 96, (1997), 612–621.
• 77. R. Vickson, Choosing the job sequence and processing times to minimize total processing plus flow cost of a single machine, Operations Research, 28 (5), (1980), 1155–1167.
• 78. R. Vickson, Two single machine sequencing problems involving controllable job processing times, AIIE Transactions, 12 (3), (1980), 258–262.
• 79. L. V. Wassenhove, K. Baker, A bicriterion approach to time/cost trade-offs in sequencing, European Journal of Operational Research, 11, (1982), 48–54.
• 80. J. Weglarz, Multiprocessor scheduling with memory allocation – a deterministic approach, IEEE Trans. Computers, C-29/8, (1980), 703–710.
• 81. S. Zdrzalka, Scheduling jobs on a single machine with release dates, due dates and controllable processing times: worst-case analysis, Operations Research Letters, 10, (1991), 519–523.
• 82. S. Zdrzalka, An approximation algorithm for a single-machine scheduling prolem with release times, delivery times and controllable processing times, European Journal of Operational Research, 72, (1994), 74–81.
• 83. F. Zhang, G. Tang, Z.-L. Chen, A 3/2-approximation algorithm for parallel machine scheduling with controllable processing times, Operations Research Letters, 29, (2001), 41–47.