Dominance relations for two-machine flow shop problem with late work criterion

• Autorzy: Sterna M.
• Języki publikacji: EN

Abstrakty

EN

The paper concerns the two-machine non-preemptive flow shop scheduling problem with a total late work criterion and a common due date (F2/dj = d/ Y). The late work performance measure estimates the quality of a solution wit h regard to the duration of late parts of activities performed in the system, not taking into account the quantity of this delay. In the paper, a few theorems are formulated and proven, describing features of an optimal solution for the problem mentioned, which is NP-hard. These theorems can be used in exact exponential algorithms (as dominance relations reducing the number of solutions enumerated explicitly), as well as in heuristic and metaheuristic methods (supporting the construction of suboptimal schedules of a good quality).

Słowa kluczowe

EN

scheduling; flow shop; late work criterion; dominance relation

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2007
• Tom: Vol. 55, nr 1
• Strony: 59--69
• Opis fizyczny: Bibliogr. 26 poz., rys.

Twórcy

autor

Sterna M.

• Institute of Computing Science, Poznań University of Technology, 2 Piotrowo St., 60-965 Poznań, Poland,

Bibliografia

• [1] J. Błażewicz, K Ecker, E. Pesch, G. Schmidt, and J. Węglarz, Scheduling Computer and Manufacturing Processes, 2nd ed., Springer, Berlin, 200l.
• [2] P. Brucker, Scheduling Algorithms, Springer, Berlin, 1998.
• [3] M. Pinedo and X. Chao, Operation Scheduling with Applications in Manufacturing and Services, McGraw-Hill, Boston, 1999.
• [4] J.Y-T. Leung, "Minimizing total weighted error for imprecise computation tasks and related problems", in: Handbook of Scheduling: Algorithms, Models, and Performance Analysis, pp. 1-16, edited by J.Y-T Leung, CRC Press, Boca Raton, 2004.
• [5] J. Błażewicz, "Scheduling preemptible tasks on parallel processors with information loss", Recherche Technique et Science Informatiques 3(6), 415-420 (1984).
• [6] J. Błażewicz and G. Finke, "Minimizing mean weighted execution time lass on identical and uniform processors", Information Processing Letters 24, 259-263 (1987).
• [7] C.N. Potts and L.N. Van Wassenhove, "Single machine scheduling to minimize total late work", Operations Research 40(3), 586-595 (1991).
• [8] C.N. Potts and L.N. Van Wassenhove, "Approximation algorithms for scheduling a single machine to minimize total late work", Operations Research Letters 11,261-266 (1991).
• [9] A.M.A. Hariri, C.N. Potts, and L.N. Van Wassenhove, "Single machine scheduling to minimize total late work", INFORMS Journal on Computing 7, 232-242 (1995).
• [10] M.Y. Kovalyov, C.N. Potts, and L.N. Van Wassenhove, "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).
• [11] D.S. Hochbaum and R Shamir, "Minimizing the number of tardy job unit under release time constraints", Discrete Applied Mathematics 28, 45-57 (1990).
• [12] J.Y-T. Leung, V.KM. Yu, and W-D. Wei, "Minimizing the weighted number of tardy task units", Discrete Applied Mathematics 51, 307-316 (1994).
• [13] RB. Kethley and B. Alidaee, "Single machine scheduling to minimize total late work: a comparison of scheduling rules and search algorithms", Computers 8 Industrial Engineering 43, 509-528 (2002).
• [14] S.G. Kolliopoulos and G. Steiner, "Approximation algorithms for minimizing total weighted tardiness on a single machine", Lectures Notes in Computer Science 2996, 176-186 (2004).
• [15] G.J. Woeginger, "When does a dynamic programming formulation guarantee the existence of an FPTAS?" in: Electronic Colloquium on Computational Complexity Report TR01-084, University of Trier, 2001.
• [16] J. Blażewicz, E. Pesch, M. Sterna, and F. Werner, "Total late work criteria for shop scheduling problems", in: Operations Research Proceedings edited by K. Inderfurth, G. Schwödiauer, W. Domschke, F. Juhnke, P. Kleinschmidt, G. Wäscher, pp. 354-359, Springer, Berlin, 2000.
• [17] J. Blażewicz, E. Pesch, M. Sterna, and F. Werner, "Open shop scheduling problems with late work criteria", Discrete Applied Mathematics 134, 1-24 (2004).
• [18] J. Blażewicz, E. Pesch, M. Sterna, and F. Werner, "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).
• [19] J. Błażewicz, E. Pesch, M. Sterna, and F. Werner, "A note on two-machine job shop with late work criterion", Journal of Scheduling 10 (2), 87-97 (2007).
• [20] J. Błażewicz, E. Pesch, M. Sterna, and F. Werner, "Flow shop scheduling with late work criterion - choosing the best solution strategy, Lecture Notes in Computer Science 3285, 68-75 (2004).
• [21] J. Błażewicz, E. Pesch, M. Sterna, and F. Werner, "A comparison of solution procedures for two-machine flow shop scheduling with late work criterion", Computers & Industrial Engineering 49, 611-624 (2005).
• [22] J. Błażewicz, E. Pesch, M. Sterna, and F. Werner, "Metaheuristics for late work minimization in two-machine flow shop with common due date", Lecture Notes in Artificial lntelligence 3698, 222-234 (2005).
• [23] M. Sterna, Problems and Algorithms in Non-Classical Shop Scheduling, Scientific Publishers of the Polis h Academy of Sciences, Poznań, 2000.
• [24] M.R Garey and D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-completeness, W.H. Freeman and Co., San Francisco, 1979.
• [25] B.M.T. Lin, F.C. Lin, and RC.T. Lee, "Two-machine flow shop scheduling to minimize total late work", Engineering Optimization 38(4),501-509 (2006).
• [26] S.M. Johnson, "Optimal two- and three-stage production schedules with setup times included", Naval Research Logistics Quarterly 1, 61-68 (1954).