×

Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms. (English) Zbl 1205.90129

Summary: We consider a class of non-identical parallel-machine scheduling problems in which the goal is to minimize total (or mean) weighted (or unweighted) completion time. Models and relaxations are collected and classified in this paper. Heuristics and optimizing techniques are surveyed for the problems. And a few of interesting areas for future research are also provided.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lee, C. Y.; Lei, L.; Pinedo, M., Current trends in deterministic scheduling, Ann. Oper. Res., 70, 1-41 (1997) · Zbl 0890.90102
[2] Cheng, T. C.E.; Sin, C., A state-of-the-art review of parallel-machine scheduling research, Eur. J. Oper. Res., 47, 271-292 (1990) · Zbl 0707.90053
[3] Mokotoff, E., Parallel machine scheduling problems: a survey, Asia-Pacific J. Oper. Res., 18, 193-242 (2001) · Zbl 1042.90564
[4] Baker, K.; Scudder, G., Scheduling with earliness and tardiness penalties: a review, Oper. Res., 38, 22-36 (1990) · Zbl 0699.90052
[5] Allahverdi, A.; Gupta, J. N.D.; Aldowaisan, T., A review of scheduling research involving setup considerations, Manage. Sci., 27, 219-239 (1999)
[6] Gordon, V.; Proth, J. M.; Chu, C., A survey of the state-of-the-art of common due date assignment and scheduling research, Eur. J. Oper. Res., 139, 1-25 (2002) · Zbl 1009.90054
[7] Cheng, T. C.E.; Ding, Q.; Lin, B. M.T., A concise survey of scheduling with time-dependent processing times, Eur. J. Oper. Res., 152, 1-13 (2004) · Zbl 1030.90023
[8] McNaughton, R., Scheduling with deadlines and loss functions, Manage. Sci., 6, 1-12 (1959) · Zbl 1047.90504
[9] Horn, W., Minimizing average flow time with parallel machines, Oper. Res., 21, 846-847 (1973) · Zbl 0259.90030
[10] Bruno, J. L.; Coffman, E. G.; Sethi, R., Scheduling independent tasks to reduce mean finishing time, AIIE Trans., 17, 382-387 (1974) · Zbl 0283.68039
[11] Du, J.; Leung, J. Y.T., Minimizing mean flow time in two-machine open shops and flow shops, J. Algor., 14, 24-44 (1993) · Zbl 0768.90039
[12] Phillips, C.; Stein, C.; Wein, J., Minimizing average completion time in the presence of release dates, Math. Program. Soc., 82, 199-223 (1998) · Zbl 0920.90074
[13] Elmaghraby, S. E.; Park, S. H., Scheduling jobs on a number of identical machines, AIIE Trans., 6, 1-13 (1974)
[14] Baker, K.; Merten, A. G., Scheduling with parallel machines and linear delay costs, Naval Res. Logist. Quart., 20, 793-804 (1973) · Zbl 0273.90030
[15] Barnes, J. W.; Brennan, J. J., An improved algorithm for scheduling jobs on identical machines, AIIE Trans., 9, 25-31 (1977)
[16] Eastman, W. L.; Even, S.; Isaacs, I. M., Bounds for the optimal scheduling of n jobs on m processors, Manage. Sci., 11, 268-279 (1964)
[17] Sarin, S. C.; Ahn, S.; Bishop, A. B., An improved branching scheme for the branch and bound procedure of scheduling n jobs on m parallel machines to minimize total weighted flowtime, Int. J. Product. Res., 26, 1183-1191 (1988) · Zbl 0641.90043
[18] Webster, S., New bounds for the identical parallel processor weighted flow time problem, Manage. Sci., 38, 124-136 (1992) · Zbl 0777.90020
[19] Belouadah, H.; Potts, C. N., Scheduling identical parallel machines to minimize total weighted completion time, Discrete Appl. Math., 48, 201-218 (1994) · Zbl 0809.90073
[20] Azizoglu, M.; Kirca, O., On the minimization of total weighted flow time with identical and uniform parallel machines, Eur. J. Oper. Res., 113, 91-100 (1999) · Zbl 0933.90025
[21] Azizoglu, M.; Kirca, O., Scheduling jobs on unrelated parallel machines to minimize regular total cost functions, AIIE Trans., 31, 153-159 (1999)
[22] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044
[23] Vredeveld, T.; Hurkens, C., Experimental comparison of approximation algorithms for scheduling unrelated parallel machines, INFORMS J. Comput., 14, 175-189 (2002) · Zbl 1238.90071
[24] Blazewicz, J.; Dror, M.; Weglarz, J., Mathematical programming formulations for machine scheduling: a survey, Eur. J. Oper. Res., 51, 283-300 (1991) · Zbl 0734.90040
[25] Skutella, M., Convex quadratic and semidefinite programming relaxations in scheduling, J. ACM, 48, 206-242 (2001) · Zbl 1323.90024
[26] Lenstra, J. K.; Shmoys, D. B.; Tardos, E., Approximation algorithms for scheduling unrelated parallel machines, Math. Program., 46, 259-271 (1990) · Zbl 0715.90063
[27] Chen, Z-L.; Powell, W. B., Solving parallel machine scheduling problems by column generation, INFORMS J. Comput., 11, 78-94 (1999) · Zbl 1034.90506
[28] Hall, L. A.; Schulz, A. S.; Shmoys, D. B.; Wein, J., Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Math. Oper. Res., 22, 513-544 (1997) · Zbl 0883.90064
[29] Dyer, M. E.; Wolsey, L. A., Formulating the single machine sequencing problem with release dates as a mixed integer program, Discrete Appl. Math., 26, 255-270 (1990) · Zbl 0694.90060
[30] F. Afrati, E. Bampis, Chekuri, et al., Approximation schemes for minimizing average weighted completion time with release dates, in: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1999, pp. 32-43.; F. Afrati, E. Bampis, Chekuri, et al., Approximation schemes for minimizing average weighted completion time with release dates, in: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1999, pp. 32-43.
[31] Belouadah, H.; Posner, M. E.; Potts, C. N., Scheduling with release dates on a single machine to minimize total weighted completion time, Discrete Appl. Math., 36, 213-231 (1992) · Zbl 0757.90032
[32] Queyranne, M., Structure of a simple scheduling polyhedron, Math. Program., 58, 263-285 (1993) · Zbl 0778.90031
[33] M. Goemans, A supermodular relaxation for scheduling with release dates, in: Proceedings of the Fifth MPS Conference on Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science (LNCS) 1084, Springer-Verlag, Berlin, Germany, 1996, pp. 288-300.; M. Goemans, A supermodular relaxation for scheduling with release dates, in: Proceedings of the Fifth MPS Conference on Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science (LNCS) 1084, Springer-Verlag, Berlin, Germany, 1996, pp. 288-300. · Zbl 1414.90149
[34] Goemans, M.; Queyranne, M.; Schulz, S.; Skutella, M.; Wang, Y., Single machine scheduling with release dates, SIAM J. Discrete Math., 15, 165-192 (2002) · Zbl 1009.90096
[35] M.W.P. Savelsbergh, R.N. Uma, J. Wein, An experimental study of LP-based approximation algorithms for scheduling problems, in: Proceedings of the Ninth Annual ACM-AIAM Symposium on Discrete Algorithms, January 25-27, San Francisco, California, United States, 1998, pp. 453-462.; M.W.P. Savelsbergh, R.N. Uma, J. Wein, An experimental study of LP-based approximation algorithms for scheduling problems, in: Proceedings of the Ninth Annual ACM-AIAM Symposium on Discrete Algorithms, January 25-27, San Francisco, California, United States, 1998, pp. 453-462. · Zbl 0938.68534
[36] Möhring, R. H.; Schulz, S.; Uetz, M., Approximation in stochastic scheduling: the power of LP-based priority policies, J. ACM, 46, 924-942 (1999) · Zbl 1176.90262
[37] A.S. Schulz, M. Skutella, Random-based scheduling: new approximations and LP lower bounds, J. Rolim (Ed.), Randomization and Approximation Techniques in Computer Science, in: Proceedings of the First International Symposium on Randomization and Approximation Techniques in Computer Science (Random’97), Lecture Notes in Computer Science (LNCS) 1269, Springer, Berlin, Germany, 1997, pp. 119-133.; A.S. Schulz, M. Skutella, Random-based scheduling: new approximations and LP lower bounds, J. Rolim (Ed.), Randomization and Approximation Techniques in Computer Science, in: Proceedings of the First International Symposium on Randomization and Approximation Techniques in Computer Science (Random’97), Lecture Notes in Computer Science (LNCS) 1269, Springer, Berlin, Germany, 1997, pp. 119-133.
[38] Kozlov, M. K.; Tarasov, S. P.; Hačijan, L. G., Polynomial solvability of convex quadratic programming, Sov. Math. Dok, 20, 1108-1111 (1979) · Zbl 0434.90071
[39] Chung, S. J.; Murty, K. G., Polynomially bounded ellipsoid algorithms for convex quadratic programming, (Mangasarian, O. L.; Meyer, R. R.; Robinson, S. M., Nonlinear Programming, vol. 4 (1981), Academic Press: Academic Press Orlando, FL), 439-485
[40] M. Skutella, Approximation and Randomization in Scheduling. Ph.D. thesis, Fachbereich Mathematik, Technische Universität Berlin, Berlin, Germany, 1998.; M. Skutella, Approximation and Randomization in Scheduling. Ph.D. thesis, Fachbereich Mathematik, Technische Universität Berlin, Berlin, Germany, 1998. · Zbl 1050.90526
[41] Zhang, F.; Tang, G.; Chen, Z., A 3/2-approximation algorithm for parallel machine scheduling with controllable processing times, Oper. Res. Lett., 29, 41-47 (2001) · Zbl 0981.90027
[42] S.J. Van der Linden, Convex quadratic relaxations and approximation algorithms: a computational study, Master’s thesis, Department of Operational Research and Management, University of Amsterdam, Amsterdam, The Netherlands, 2000.; S.J. Van der Linden, Convex quadratic relaxations and approximation algorithms: a computational study, Master’s thesis, Department of Operational Research and Management, University of Amsterdam, Amsterdam, The Netherlands, 2000.
[43] Lawler, E. L.; Moore, J. M., A functional equation and its application to resource allocation and scheduling problems, Manage. Sci., 16, 77-84 (1969) · Zbl 0184.23303
[44] Lee, C. Y.; Uzsoy, R., A new dynamic programming algorithm for the parallel machines total weighted completion time problem, Oper. Res. Lett., 11, 73-75 (1992) · Zbl 0760.90057
[45] Phillips, C.; Stein, C.; Wein, J., Task scheduling in networks, SIAM J. Discrete Math., 10, 573-598 (1997) · Zbl 0885.68020
[46] Shmoys, D. B.; Tardos, E., An approximation algorithm for the generalized assignment problem, Math. Program., 62, 461-474 (1993) · Zbl 0804.90077
[47] Schulz, A. S.; Skutella, M., Scheduling unrelated machines by randomized rounding, SIAM J. Discrete Math., 15, 450-469 (2002) · Zbl 1055.90040
[48] Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 1115-1145 (1995) · Zbl 0885.68088
[49] J.A. Hoogeveen, P. Schuurman, G.J. Woeginger, Non-approximability results for scheduling problems with minsum criteria, in: Proceedings of the Sixth Conference on Integer Programming and Combinatorial Optimization (IPCO’98), LNCS 1412, Springer, Berlin, Germany, 1998, pp. 353-366.; J.A. Hoogeveen, P. Schuurman, G.J. Woeginger, Non-approximability results for scheduling problems with minsum criteria, in: Proceedings of the Sixth Conference on Integer Programming and Combinatorial Optimization (IPCO’98), LNCS 1412, Springer, Berlin, Germany, 1998, pp. 353-366. · Zbl 0911.90208
[50] M.G.C. Resende, P.M. Pardalos, S.D. Ekşiog˜lu, Parallel metaheuristics for combinatorial optimization. The International School on Advanced Algorithmic Techniques for Parallel Computations with Applications, Natal Brazil, October 2, 1999, pp. 1-21.; M.G.C. Resende, P.M. Pardalos, S.D. Ekşiog˜lu, Parallel metaheuristics for combinatorial optimization. The International School on Advanced Algorithmic Techniques for Parallel Computations with Applications, Natal Brazil, October 2, 1999, pp. 1-21.
[51] Verhoeven, M. G.A.; Aarts, E. H.L., Parallel Local Search, J. Heurist., 1, 43-65 (1995) · Zbl 0853.68156
[52] Blum, C.; Roli, A., Metaheuristics in combinatorial optimization: overview and conceptual comparison, ACM Comput. Surveys, 35, 268-308 (2003)
[53] Dimipoulos, C.; Zalzala, A. M.S., Recent development in evolutionary computation for manufacturing optimization: problems, solutions and comparisons, IEEE Trans. Evol. Comput., 4, 93-113 (2000)
[54] Aytug, H.; Khouja, M.; Vergara, F. E., Use of genetic algorithms to solve production and operations management problems: a review, Int. J. Product. Res., 41, 3955-4009 (2003)
[55] Gravel, M.; Price, W. L.; Gagne, C., Scheduling jobs in an alcan aluminium foundry using a genetic algorithm, Int. J. Product. Res., 38, 3031-3041 (2000)
[56] Fowler, J. W.; Horng, S.; Cochran, J. K., A hybridized genetic algorithm to solve parallel machine scheduling problems with sequence dependent setups, Int. J. Ind. Eng., 10, 232-243 (2003)
[57] Brucker, P.; Kampmeyrer, T., Tabu search algorithms for cyclic machine scheduling problems, J. Sched., 8, 303-322 (2005) · Zbl 1123.90018
[58] Laguna, M.; Velaverde, J. L.G., A search heuristic for just-in-time scheduling in parallel machines, J. Intell. Manufact., 2, 253-260 (1991)
[59] Barnes, J. W.; Laguna, M., Solving the multiple machine weighted flow time using tabu search, IIE Trans., 25, 121-128 (1993)
[60] Hübscher, R.; Glover, F., Applying tabu search with influential diversification to multiprocessor scheduling, Comput. Oper. Res., 21, 877-884 (1994) · Zbl 0814.90048
[61] França, P. M.; Gendreau, M.; Laporte, G.; Müller, F. M., The m-traveling salesman problem with minimax objective, Transport. Sci., 29, 267-275 (1995) · Zbl 0858.90128
[62] Smith, W. E., Various optimizes for single-stage production, Naval Res. Logist. Quart., 3, 59-66 (1956)
[63] Weng, M. X.; Lu, J.; Ren, H., Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective, Int. J Product. Econ., 70, 215-226 (2001)
[64] Woeginger, G. J., A comment on scheduling on uniform machines under chain-type precedence constraints, Oper. Res. Lett., 26, 107-109 (2000) · Zbl 0955.90036
[65] Epstein, L., Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios, Oper. Res. Lett., 29, 93-98 (2001) · Zbl 0981.90024
[66] Du, D., Optimal preemptive semi-online scheduling on two uniform processors, Infor. Process. Lett., 92, 219-223 (2004) · Zbl 1173.68404
[67] Koulamas, C.; Kyparisis, G. J., Scheduling on uniform parallel machines to minimize maximum lateness, Oper. Res. Lett., 26, 175-179 (2000) · Zbl 0971.90035
[68] Balakrishnan, N.; Kanet, J. J.; Sridharan, V., Early/tardy scheduling with sequence dependent setups on uniform parallel machines, Comput. Oper. Res., 26, 127-141 (1999) · Zbl 0947.90043
[69] Ventura, J. A.; Kim, D., Parallel machine scheduling with earliness-tardiness penalties and additional resource constraints, Comput. Oper. Res., 30, 1945-1958 (2003) · Zbl 1047.90023
[70] Chen, H.; Luh, P. B., An alternative framework to Lagrangian relaxation approach for job shop scheduling, Eur. J. Oper. Res., 149, 499-512 (2003) · Zbl 1033.90036
[71] Baptiste, P.; Peridy, L.; Pinson, E., A branch and bound to minimize the number of late jobs on a single machine with release time constraints, Eur. J. Oper. Res., 144, 1-11 (2003) · Zbl 1037.90022
[72] Thomalla, C. S., Job shop scheduling with alternative process plans, Int. J. Product. Econ., 74, 125-134 (2001)
[73] Webster, S., Weighted flow time bounds for scheduling identical processors, Eur. J. Oper. Res., 80, 103-111 (1995) · Zbl 0927.90056
[74] Brown, D. E.; Scherer, W. T., Intelligent Scheduling Systems (1995), Kluwer Academic Publishers
[75] Lenstra, J. K.; Rinnooy Kan, A. H.G., Complexity of scheduling under precedence constraints, Oper. Res., 26, 22-35 (1978) · Zbl 0371.90060
[76] J. Labetoulle, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, Preemptive scheduling of uniform machines subject to release dates, in: Progress in combinatorial optimization (Waterloo), 1982, pp. 245-261.; J. Labetoulle, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, Preemptive scheduling of uniform machines subject to release dates, in: Progress in combinatorial optimization (Waterloo), 1982, pp. 245-261. · Zbl 0554.90059
[77] Du, J.; Leung, J. Y.T., Minimizing total tardiness on one machine is NP-hard, Math. Oper. Res., 15, 483-495 (1990) · Zbl 0714.90052
[78] Leung, J. Y.T.; Young, G. H., Preemptive scheduling to minimize mean weighted flow time, Infor. Process. Lett., 34, 47-51 (1990) · Zbl 0695.68029
[79] R.A. Sitters, Two NP-hardness results for preemptive minsum scheduling of unrelated parallel machines, in: Proceedings of Eighth International IPCO Conference, Lecture Notes in Computer Science 2001, pp. 396-405.; R.A. Sitters, Two NP-hardness results for preemptive minsum scheduling of unrelated parallel machines, in: Proceedings of Eighth International IPCO Conference, Lecture Notes in Computer Science 2001, pp. 396-405. · Zbl 1010.90025
[80] P. Brucker, S.A. Kravchenko, Complexity of mean flow time scheduling problems with release dates, OSM Reihe P, Heft 251, Universität Osnabrück, Fachbereich Mathematik/Informatik, 2004.; P. Brucker, S.A. Kravchenko, Complexity of mean flow time scheduling problems with release dates, OSM Reihe P, Heft 251, Universität Osnabrück, Fachbereich Mathematik/Informatik, 2004.
[81] L.A. Hall, D.B. Shmoys, J. Wein, Scheduling to minimize average completion time: off-line and on-line approximation algorithms, in: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996, pp. 142-151.; L.A. Hall, D.B. Shmoys, J. Wein, Scheduling to minimize average completion time: off-line and on-line approximation algorithms, in: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996, pp. 142-151. · Zbl 0845.90071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.