Single processor scheduling problems with various models of a due window assignment

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

Abstrakty

EN

In the paper we investigate four single processor scheduling problems, which deal with the process of the negotia-tion between a producer and a customer about delivery time of final products. This process is modeled by a due window, which is a generalization of well known classical due date and describes a time interval, in which a job should be finished. Due window assignment is a new approach, which has been investigated in the scientific literature for a few years. In this paper we consider various models of due window assignment. To solve the formu-lated problems we have to find such a schedule of jobs and such an assignment of due windows to each job, which minimizes a given criterion dependent on the maximum or total earliness and tardiness of jobs and due window parameters. One of the main results is the mirror image of the solutions of the considered problems and other problems presented in the scientific literature. The wide survey of the literature is also given.

Słowa kluczowe

EN

scheduling; single machine; earliness/tardiness; due window assignment

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2009
• Tom: Vol. 57, nr 1
• Strony: 95--101
• Opis fizyczny: Bibliogr. 38 poz., rys.

Twórcy

autor

Janiak A.

autor

Janiak W.A.

autor

Marek M.

• Institute of Computer Engineering, Control and Robotics, Wrocław University of Technology, 11/17 Janiszewskiego St., 50-372 Wrocław, Poland,

Bibliografia

• [1] M. Sterna, "Dominance relations for two-machine flow shop problem with late work criterion", Bull. Pot. Ac.: Tech. 55(1), 59-69 (2007).
• [2] T.C.E. Cheng and M.C. Gupta, "Survey of scheduling research involving due date determination decision", Eur. J. Operational Research 38, 156-166 (1989).
• [3] C. Chengbin, Y. Gordon and I.-M. Proth, "A survey of the state-of-the-art of common due date assignment and scheduling research", Eur. J. Operational Research 139, 1-25 (2002).
• [4] C. Chengbin, V.Gordon, and I.-M. Proth, "Due date assignment and scheduling: SLK, TWK and other due date assignment models", Production Planning & Control 13 (2), 117-132 (2002).
• [5] A. Federgruen and G. Mosheiov, "Simultaneous optimization of efficiency and performance balance measures in single-machine scheduling problems", Naval Research Logistics 40, 952-970 (1993).
• [6] A. Federgruen and G. Mosheiov, "Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs", Operations Research Letters 16, 199-208 (1994).
• [7] X. Cai, V.Y.S. Lum, and I.M.T. Chan, "Scheduling about a common due date with job-dependent asymmetric earliness and tardiness penalties", Eur. J. Operational Research 98, 154-168 (1997).
• [8] ED. Anger, C.-Y. Lee and Martin-Vega L.A., "Single-machine", Research Report pp. 86-16, Department of trial and System Engineering, University of Florida, Florida, 1986.
• [9] T.C.E. Cheng, "Optimal common due-date with limited completion times deviation", Computers and Operations Research 15, 91-96 (1988).
• [10] C.-Y. Lee, "Earliness-tardiness scheduling problems with constant size of due window", Research Report pp. 91-17, Department of Industrial and System Engineering, University of Florida, Florida, 1991.
• [11] F.-J. Kramer and C.-Y. Lee, "Common due-window scheduling", Production and Operations Management 2, 262-275 (1993).
• [12] J.A. Ventura and M.X. Weng, "Single machine scheduling with a common delivery window", J. Operational Research Society 47, 424-434 (1995).
• [13] M.X. Weng and J.A. Ventura, "Scheduling about a large common due-date with tolerance to minimize mean absolute deviation of completion times", Naval Research Logistics 41, 843-851 (1994).
• [14] M.X. Weng and J.A. Ventura, "Single-machine earliness-tardiness scheduling about a common due date with tolerances", Int. J. Production Economics 42, 217-227 (1996).
• [15] S.D. Liman and S. Ramaswamy, "Earliness/tardiness scheduling problems with a common delivery window", Operations Research Letters 15, 195-203 (1994).
• [16] A. Lann and G. Mosheiov, "Single machine scheduling to minimize the number of early and early jobs", Computers and Operations Research 23, 769-781 (1996).
• [17] A. Lann and G. Mosheiov, "A note on the maximum number of on-time jobs on parallel identical processors", Computers & Operations Research 30, 1745-1749 (2003).
• [18] C. Koulamas, "Single-machine scheduling with time windows and earliness/tardiness penalties", Eur. J. Operational Research 91, 190-202 (1996).
• [19] M. Azizoglu and S. Webster, "Scheduling about an unrestricted common due window with arbitrary earliness/tardiness penalty rates", IIE Transactions 29, 1001-1006 (1997).
• [20] Y. Wu and D.W Wang, "Optimal single-machine scheduling about a common due window with earliness/tardiness and additional penalties", Int. J. Systems Science 30, 1279-1284 (1999).
• [21] RJ. Unn, B. Yen, and W Zhang, "Just-in-time scheduling with machining economics for single-machine turning process", J. Manufacturing Sptems 19, 219-228 (2000).
• [22] W.K. Yeung, C. Oguz, and T.C.E. Cheng, "Minimizing weighted number of early and tardy jobs with a common due window involving location penalty", Annals of Operations Research 108, 33-54 (2001).
• [23] W.S. Yoo and LA. Martin-Vega, "Scheduling single-machine problems for on-time delivery", Computers and Industrial Engineering 39, 371-392 (2001).
• [24] Z.-L Chen and C.-Y. Lee, "Parallel machine scheduling with a common due window", Eur. J. Operational Research 136, 512-527 (2002).
• [25] D. Biskup and M. Feldmann, "On scheduling around large restrictive common due windows", Eur. J. Operational Research 162, 740-761 (2005).
• [26] M. Wodecki, "A block approach to earliness-tardiness scheduling problems", Int. J. Advanced Manufacturing Technology, (to be published).
• [27] A. Janiak and M. Marek, "Single machine scheduling problem with optimal due interval assignment", Lecture Notes of Silesia University of Technology, Automation 129, 145-155 (2000), (in Polish).
• [28] A. Janiak and M. Marek, "Multi-machine scheduling problem with optimal due interval assignment subject to generalized sum type criterion", Operations Research Proc., 207-212 (2002).
• [29] F.-J. Kramer and C.-Y. Lee, "Due window scheduling for parallel machine", Mathematical and Computer Modeling 20, 69-89 (1994).
• [30] S.D. Liman, S.S. Panwalkar and S. Thongmee, "Determination of common due window location in a single machine scheduling problem", Eur. J. Operational Research 93, 68-74 (1996).
• [31] S.D. Liman, S.S. Panwalkar and S. Thongmee, "Common due window size and location determination in a single machine scheduling problem", J. Operational Research Society 49, 1007-1010 (1998).
• [32] G. Mosheiov, A. Sarig, "A multi-criteria scheduling with due window assignment problem", Mathematical and Computer Modeling, (to be published).
• [33] W.K. Yeung, C. Oguz, T.C.E. Cheng, "Single-machine scheduling with a common due window", Computers and Operations Research 28, 157-175 (2001).
• [34] G. Mosheiov, "A due-window determination in minmax scheduling problems", INFOR 39, 107-123 (2001).
• [35] A. Janiak and M. Marek, "Optimal assignment of due intervals in some single machine scheduling problems", Lecture Notes of Mining and Metallurgical Academy, Automation 5 (1-2), 269-276 (2001), (in Polish).
• [36] A. Janiak and M. Marek, "Scheduling problems with optimal due interval assignment subject to some generalized criteria", Operations Research Proc., 142-147 (2003).
• [37] R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan, "Optimization and approximation in deterministic sequencing and scheduling: a survey", Ann. Discrete Math. 5, 287-326 (1979).
• [38] H.G. Kahlbacher, "Scheduling with monotonous earliness and tardiness penalties", Eur. J. Operational Research 64, 258277 (1993).