Scheduling problems with a common due window assignment: a survey

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

Abstrakty

EN

In this article a survey of studies on scheduling problems with a common due window assignment and earliness/tardiness penalty functions is presented. A due window is a generalization of the classical due date and describes a time interval in which a job should be finished. If a job is completed before or after the due window, it incurs an earliness or a tardiness penalty, respectively. In this survey we separately analyse the classical models with job-independent and job-dependent earliness/tardiness penalty functions and some other more complicated models. We describe the computational complexity of the problems and the main features of the approaches developed to solve them. Particular attention is paid to practical applications of the analysed models. As turns out, some complicated models combining classical scheduling problems with, e.g., learning and aging effects have no reasonable practical justification in the literature.

Słowa kluczowe

EN

scheduling; due window assignment; earliness/tardiness; practical example

PL

szeregowanie; wcześniej/później; przykład zastosowania

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2013
• Tom: Vol. 23, no. 1
• Strony: 231--241
• Opis fizyczny: Bibliogr. 52 poz., tab.

Twórcy

autor

Janiak A.

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

autor

Kwiatkowski T.

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

autor

Lichtenstein M.

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

Bibliografia

• [1] Azizoglu, M. and Webster, S. (1997). Scheduling about an unrestricted common due window with arbitrary earliness/tardiness penalty rates, IIE Transactions 29(11): 1001–1006.
• [2] Baker, K.R. and Scudder, G.D. (1990). Sequencing with earliness and tardiness penalties: A review, Operations Research 38(1): 22–36.
• [3] Biskup, D. (1999). Single-machine scheduling with learning considerations, European Journal of Operational Research 115(1): 173–178.
• [4] Chen, P., Wu, C.-C. and Lee, W.-C. (2006). A bi-criteria two-machine flowshop scheduling problem with a learning effect, Journal of the Operational Research Society 57(9): 1113–1125.
• [5] Cheng, T., Yang, S.-J. and Yang, D.-L. (2010). Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity, International Journal of Production Economics 135(1): 154–161, DOI.10.1016/j.ijpe.2010.10.005.
• [6] Dondeti, V.R. and Mohanty, B.B. (1998). Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs, European Journal of Operational Research 105(3): 509–524.
• [7] Garey, M. and Johnson, D. (1978). Strong NP-completeness results:Motivation, examples, and implications, Journal of the ACM 25(3): 499–508.
• [8] Gáspár, P., Szabó, Z and Bokor, J. (2012). LPV design of fault-tolerant control for road vehicles, International Journal of Applied Mathematics and Computer Science 22(1): 173–182, DOI: 10.2478/v10006-012-0013-x.
• [9] Gordon, V., Proth, J.-M. and Chu, C. (2002). A survey of the state-of-the-art of common due date assignment and scheduling research, European Journal of Operational Research 139(1): 1–25.
• [10] Graham, R.L., Lawler, E.L., Lenstra, J.K. and Kan, A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey, in P.L. Hammer, E.L. Johnson and B.H. Korte (Eds.), Annals of Discrete Mathematics, Vol. 5, Elsevier, Amsterdam, pp. 287–326.
• [11] Gunn, T. (1992). Logistics planning, OR/MS Today 19(1): 16–28.
• [12] Hall, N. and Posner, M. (1991). Earliness-tardiness scheduling problems. I:Weighted deviation of completion times about a common due date, Operations Research 39(5): 836–846.
• [13] Janiak, A., Janiak, W. and Marek, M. (2009). Single processor scheduling problems with various models of a due window assignment, Bulletin of the Polish Academy of Sciences: Technical Sciences 57(1): 95–101.
• [14] Janiak, A., Kovalyov, M. and Marek, M. (2007). Soft due window assignment and scheduling on parallel machines, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans 37(5): 614–620.
• [15] Janiak, A., Krysiak, T. and Trela, R. (2011). Scheduling problems with learning and aging effects: A survey, Decision Making in Manufacturing and Services 5(1–2): 19–36.
• [16] Janiak, A. and Marek, M. (2003). Scheduling problems with optimal due interval assignment subject to some generalized criteria, in U. Leopold-Wildburger, F. Rendl and G. Wäscher (Eds.), Operations Research Proceedings 2002, Springer-Verlag, Berlin/Heidelberg, pp. 217–222.
• [17] Janiak, A. and Marek, M. (2004). Property of symmetry for some single processor scheduling problems with due interval assignment, Systems Science 30(2): 97–107.
• [18] Janiak, A. And Winczaszek, M. (2003). An optimal algorithm for a single processor scheduling problem with a common due window, Proceedings of the 9th IEEE International Conference on Methods and Models in Automation and Robotics (MMAR 2003), Międzyzdroje, Poland, pp. 1213–1216.
• [19] Janiak, A. and Winczaszek, M. (2004). Scheduling problem with nonlinear earliness-tardiness penalty functions, in Z. Bubnicki, O. Hryniewicz and J. Weglarz (Eds.), Operation and System Research 2004, Academic Publishing House EXIT, Warsaw, pp. 261–270, (in Polish).
• [20] Janiak, A. and Winczaszek, M. (2005a). Optimal algorithm for parallel processor scheduling problem with due window assignment, Proceedings of the 11th IEEE International Conference on Methods and Models in Automation and Robotics, Międzyzdroje, Poland, pp. 1085–1089.
• [21] Janiak, A. and Winczaszek, M. (2005b). A single processor scheduling problem with a common due window assignment, in H. Fleuren, D. den Hertog and P. Kort (Eds.), Operations Research, Springer-Verlag, Berlin, pp. 213–220.
• [22] Janiak, A. and Winczaszek, M. (2006). Common due window assignment in parallel processor scheduling problem with nonlinear penalty functions, in R. Wyrzykowski, I. Dongarra, N. Meyer and J. Waśniewski (Eds.), Parallel Processing and Applied Mathematics, Springer-Verlag, Berlin, pp. 132–139.
• [23] Kołodziej, J. and Xhafa, F. (2011). Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids, International Journal of AppliedMathematics and Computer Science 21(2): 243–257, DOI: 10.2478/v10006-011-0018-x.
• [24] Koulamas, C. (1996). Single-machine scheduling with time windows and earliness/tardiness penalties, European Journal of Operational Research 91(1): 190–202.
• [25] Kramer, F.-J. and Lee, C.-Y. (1993). Common due-window scheduling, Production and Operations Management 2(4): 262–275.
• [26] Lauff, V. and Werner, F. (2004). Scheduling with common due date, earliness and tardiness penalties for multimachine problems: A survey, Mathematical and Computer Modelling 40(5–6): 637–655.
• [27] Lee, C. (1991). Earliness-tardiness scheduling problems with constant size of due date window, Research Report No. 91-17, Vol. 4, Industrial and Systems Engineering Department, University of Florida, Gainesville, FL, pp. 262–275.
• [28] Liman, S.D., Panwalkar, S.S. and Thongmee, S. (1997). A single machine scheduling problem with common due window and controllable processing times, Annals of Operations Research 70: 145–154.
• [29] Liman, S.D., Panwalkar, S.S. and Thongmee, S. (1998). Common due window size and location determination in a single machine scheduling problem, Journal of the Operational Research Society 49(9): 1007–1010.
• [30] Limana, S. and Ramaswamy, S. (1994). Earliness-tardiness scheduling problems with a common delivery window, Operations Research Letters 15(4): 195–203.
• [31] Meilijson, I. and Tamir, A. (1984). Minimizing flow time on parallel identical processors with variable unit processing time, Operations Research 32(2): 440–448.
• [32] Mosheiov, G. (2001). A due-window determination in minmax scheduling problems, INFOR 39(1): 107–123.
• [33] Mosheiov, G. and Oron, D. (2004). Due-window assignment with unit processing-time jobs, Naval Research Logistics 51(7): 1005–1017.
• [34] Mosheiov, G. and Sarig, A. (2008). A due-window assignment problem with position-dependent processing times, Journal of the Operational Research Society 59(7): 997–1003.
• [35] Mosheiov, G. and Sarig, A. (2009a). Minmax scheduling problems with a common due-window, Computers & Operations Research 36(6): 1886–1892.
• [36] Mosheiov, G. and Sarig, A. (2009b). Scheduling a maintenance activity and due-window assignment on a single machine, Computers & Operations Research 36(9): 2541–2545.
• [37] Mosheiov, G. and Sarig, A. (2010). Scheduling with a common due-window: Polynomially solvable cases, Information Sciences 180(8): 1492–1505.
• [38] Mosheiov, G. and Sarig, A. (2011). A note: A due-window assignment problem on parallel identical machines, Journal of the Operational Research Society 62(1): 238–241.
• [39] Wang, J-B., and Xia, Z.-Q. (2005). Flow-shop scheduling with a learning effect, Journal of the Operational Research Society 56(11): 1325–1330.
• [40] Wang, J.-B. (2006). A note on scheduling problems with learning effect and deteriorating jobs, International Journal of Systems Science 37(12): 827–833.
• [41] Wang, J.-B. and Wang, C. (2011). Single-machine due-window assignment problem with learning effect and deteriorating jobs, Applied Mathematical Modelling 35(8): 4017–4022.
• [42] Weng, M. and Ventura, J. (1996). A note on common due window scheduling, Production and Operations Management 5(2): 194–200.
• [43] Winczaszek,M. (2006). Selected Scheduling Problems with Due Window Assignment, Ph.D. thesis, Wrocław University of Technology, Wrocław, (in Polish).
• [44] Wright, T.P. (1936). Factors affecting the cost of airplanes, Journal of Aeronautical Science 3(2): 122–128.
• [45] Wu, C.-C. (2005). A makespan study of the two-machine flowshop scheduling problem with a learning effect, Journal of Statistics and Management Systems 8(1): 13–25.
• [46] Wu, Y. and Lai, K. (2007). A production scheduling strategy with a common due window, Computers & Industrial Engineering 53(2): 215–221.
• [47] Wu, Y. and Wang, D. (1999). Optimal single-machine scheduling about a common due window with earliness/tardiness and additional penalties, International Journal of Systems Sciences 30(12): 1279–1284.
• [48] Yang, S.-J. (2010). Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration, Applied Mathematics and Computation 217(7): 3321–3329.
• [49] Yang, S.-J., Yang, D.-L. and Cheng, T. (2010). Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance, Computers & Operations Research 37(8): 1510–1514.
• [50] Yeung, W., Oguz, C. and Cheng, T. (2001a). Minimizing weighted number of early and tardy jobs with a common due window involving location penalty, Annals of Operations Research 108(1–4): 33–54.
• [51] Yeung, W., Oguz, C. and Cheng, T. (2001b). Single-machine scheduling with a common due window, Computers & Operations Research 28(2): 157–175.
• [52] Zhao, C. and Tang, H. (2010). A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity, Computers & Operations Research 39(6): 1300–1303, DOI:10.1016/j.cor.2010.04.006.