×

Metaheuristic approaches for the two-machine flow-shop problem with weighted late work criterion and common due date. (English) Zbl 1141.90018

Summary: In this paper, metaheuristic approaches for the two-machine flow-shop problem with a common due date and the weighted late work performance measure \((F2|d_{j}=d|Y_{w})\) are presented. The late work criterion estimates the quality of a solution with regard to the duration of the late parts of jobs, not taking into account the quantity of the delay for the fully late activities. Since the problem mentioned is known to be NP-hard, three trajectory methods, namely simulated annealing, tabu search and variable neighborhood search are proposed based on the special features of the case under consideration. Then, the results of computational experiments are reported, in which the metaheuristics were compared one to each other, as well to an exact approach and a list scheduling algorithm.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blazewicz, J.; Ecker, K.; Pesch, E.; Schmidt, G.; Weglarz, J., Scheduling computer and manufacturing processes (2001), Springer: Springer Berlin, Heidelberg, New York · Zbl 0985.90033
[2] Brucker, P., Scheduling algorithms (1998), Springer: Springer Berlin, Heidelberg, New York · Zbl 0914.90157
[3] Chen, B.; Potts, C. N.; Woeginger, G. J., A review of machine scheduling, (Du, D.-Z.; Pardalos, P. M., Handbook of combinatorial optimization (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Boston)
[4] Pinedo, M.; Chao, X., Operation scheduling with applications in manufacturing and services (1999), Irwin/McGraw-Hill: Irwin/McGraw-Hill Boston
[5] Blazewicz, J., Scheduling preemptible tasks on parallel processors with information loss, Technique et Science Informatiques, 3, 6, 415-420 (1984) · Zbl 0565.68037
[6] Blazewicz, J.; Finke, G., Minimizing mean weighted execution time loss on identical and uniform processors, Information Processing Letters, 24, 259-263 (1987) · Zbl 0626.90037
[7] Hariri, A. M.A.; Potts, C. N.; Van Wassenhove, L. N., Single machine scheduling to minimize total late work, INFORMS Journal on Computing, 7, 232-242 (1995) · Zbl 0859.90084
[8] Hochbaum, D. S.; Shamir, R., Minimizing the number of tardy job unit under release time constraints, Discrete Applied Mathematics, 28, 45-57 (1990) · Zbl 0707.90049
[9] Kethley, R. B.; Alidaee, B., Single machine scheduling to minimize total late work: a comparison of scheduling rules and search algorithms, Computers and Industrial Engineering, 43, 509-528 (2002)
[10] Kovalyov, M. Y.; Potts, C. N.; Van Wassenhove, L. N., A fully polynomial approximation scheme for scheduling a single machine to minimize total weighted late work, Mathematics of Operations Research, 19, 1, 86-93 (1994) · Zbl 0799.90064
[11] Leung, J. Y-T.; Yu, V. K.M.; Wei, W.-D., Minimizing the weighted number of tardy task units, Discrete Applied Mathematics, 51, 307-316 (1994) · Zbl 0811.68063
[12] Potts, C. N.; Van Wassenhove, L. N., Single machine scheduling to minimize total late work, Operations Research, 40, 3, 586-595 (1991) · Zbl 0756.90051
[13] Potts, C. N.; Van Wassenhove, L. N., Approximation algorithms for scheduling a single machine to minimize total late work, Operations Research Letters, 11, 261-266 (1991) · Zbl 0767.90039
[14] Blazewicz, J.; Pesch, E.; Sterna, M.; Werner, F., Total late work criteria for shop scheduling problems, (Inderfurth, K.; Schwoediauer, G.; Domschke, W.; Juhnke, F.; Kleinschmidt, P.; Waescher, G., Operations Research Proceedings 1999 (2000), Springer: Springer Berlin), 354-359 · Zbl 1015.90037
[15] Blazewicz J, Pesch E, Sterna M, Werner F. Revenue management in a job-shop: a dynamic programming approach. Preprint Nr. 40/03, FMA, Otto-von-Guericke-University Magdeburg; 2003.; Blazewicz J, Pesch E, Sterna M, Werner F. Revenue management in a job-shop: a dynamic programming approach. Preprint Nr. 40/03, FMA, Otto-von-Guericke-University Magdeburg; 2003.
[16] Blazewicz, J.; Pesch, E.; Sterna, M.; Werner, F., Open shop scheduling problems with late work criteria, Discrete Applied Mathematics, 134, 1-24 (2004) · Zbl 1043.90026
[17] Blazewicz, J.; Pesch, E.; Sterna, M.; Werner, F., The two-machine flow-shop problem with weighted late work criterion and common due date, European Journal of Operational Research, 165, 2, 408-415 (2005) · Zbl 1066.90023
[18] Blazewicz, J.; Pesch, E.; Sterna, M.; Werner, F., A comparison of solution procedures for two-machine flow shop scheduling with late work criterion, Computers and Industrial Engineering, 49, 4, 611-624 (2005)
[19] Blazewicz J, Pesch E, Sterna M, Werner F. Metaheuristic approaches for the two-machine flow-shop problem with weighted late work criterion and common due date. Preprint Nr. 32, FMA, Otto-von-Guericke-University Magdeburg; 2005.; Blazewicz J, Pesch E, Sterna M, Werner F. Metaheuristic approaches for the two-machine flow-shop problem with weighted late work criterion and common due date. Preprint Nr. 32, FMA, Otto-von-Guericke-University Magdeburg; 2005. · Zbl 1066.90023
[20] Leung, J. Y.-T., Minimizing total weighted error for imprecise computation tasks and related problems, (Leung, J. Y.-T., Handbook of scheduling: algorithms, models, and performance analysis (2004), CRC Press: CRC Press Boca Raton, FL), 1-16
[21] Sterna, M., Problems and algorithms in non-classical shop scheduling (2000), Scientific Publishers of the Polish Academy of Sciences, Poland: Scientific Publishers of the Polish Academy of Sciences, Poland Poznan
[22] Garey, M. R.; Johnson, D. S., Computers and intractability (1979), W.H. Freeman and Co.: W.H. Freeman and Co. San Francisco · Zbl 0411.68039
[23] Blum, Ch.; Roli, A., Metaheuristics in combinatorial optimization: overview and conceptual comparison, ACM Computing Surveys, 35, 3, 268-308 (2003)
[24] Crama, Y.; Kolen, A.; Pesch, E., Local search in combinatorial optimization, Lecture Notes in Computer Science, 931, 157-174 (1995)
[25] Johnson, S. M., Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61-68 (1954) · Zbl 1349.90359
[26] Haupt, R., A survey of priority rule—based scheduling, OR Sektrum, 11, 3-16 (1989) · Zbl 0658.90047
[27] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162
[28] Glover, F.; Laguna, M., Tabu search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0930.90083
[29] Hansen, P.; Mladenović, N., An introduction to variable neighbour search, (Voss, S.; Martello, S.; Osman, I.; Roucairol, C., Metaheuristics: advances and trends in local search paradigms for optimization (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 433-458 · Zbl 0985.90095
[30] Barr, R. S.; Golden, B. L.; Kelly, J. P.; Resende, M. G.C.; Stewart, W. R., Designing and reporting on computational experiments with heuristic methods, Journal of Heuristics, 1, 9-32 (1995) · Zbl 0853.68154
[31] Hooker, J. N., Testing heuristics: we have it all wrong, Journal of Heuristics, 1, 33-42 (1995) · Zbl 0853.68155
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.