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.
@article{bwmeta1.element.bwnjournal-article-amcv23z1p231bwm,
author = {Adam Janiak and Tomasz Kwiatkowski and Maciej Lichtenstein},
title = {Scheduling problems with a common due window assignment: A survey},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {23},
year = {2013},
pages = {231-241},
zbl = {1305.90213},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv23z1p231bwm}
}
Adam Janiak; Tomasz Kwiatkowski; Maciej Lichtenstein. Scheduling problems with a common due window assignment: A survey. International Journal of Applied Mathematics and Computer Science, Tome 23 (2013) pp. 231-241. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv23z1p231bwm/
[000] 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.
[001] Baker, K.R. and Scudder, G.D. (1990). Sequencing with earliness and tardiness penalties: A review, Operations Research 38(1): 22-36. | Zbl 0699.90052
[002] Biskup, D. (1999). Single-machine scheduling with learning considerations, European Journal of Operational Research 115(1): 173-178. | Zbl 0946.90025
[003] 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. | Zbl 1171.90394
[004] 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.
[005] 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. | Zbl 0955.90029
[006] Garey, M. and Johnson, D. (1978). Strong NP-completness results: Motivation, examples, and implications, Journal of the ACM 25(3): 499-508. | Zbl 0379.68035
[007] 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. | Zbl 1273.93050
[008] 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. | Zbl 1009.90054
[009] 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. | Zbl 0411.90044
[010] Gunn, T. (1992). Logistics planning, OR/MS Today 19(1): 16-28.
[011] 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. | Zbl 0749.90041
[012] 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.
[013] 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.
[014] 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. | Zbl 1245.90031
[015] 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. | Zbl 1162.90457
[016] 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. | Zbl 1162.90456
[017] 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.
[018] 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).
[019] 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.
[020] 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. | Zbl 1182.68028
[021] 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. | Zbl 1182.68028
[022] 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 Applied Mathematics and Computer Science 21(2): 243-257, DOI: 10.2478/v10006-011-0018-x.
[023] Koulamas, C. (1996). Single-machine scheduling with time windows and earliness/tardiness penalties, European Journal of Operational Research 91(1): 190-202. | Zbl 0947.90588
[024] Kramer, F.-J. and Lee, C.-Y. (1993). Common due-window scheduling, Production and Operations Management 2(4): 262-275.
[025] 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. | Zbl 1098.90031
[026] 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.
[027] 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. | Zbl 0890.90104
[028] 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. | Zbl 1140.90405
[029] Limana, S. and Ramaswamy, S. (1994). Earliness-tardiness scheduling problems with a common delivery window, Operations Research Letters 15(4): 195-203. | Zbl 0814.90049
[030] Meilijson, I. and Tamir, A. (1984). Minimizing flow time on parallel identical processors with variable unit processing time, Operations Research 32(2): 440-448. | Zbl 0573.90054
[031] Mosheiov, G. (2001). A due-window determination in minmax scheduling problems, INFOR 39(1): 107-123.
[032] Mosheiov, G. and Oron, D. (2004). Due-window assignment with unit processing-time jobs, Naval Research Logistics 51(7): 1005-1017. | Zbl 1055.90036
[033] 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. | Zbl 1144.90391
[034] Mosheiov, G. and Sarig, A. (2009a). Minmax scheduling problems with a common due-window, Computers & Operations Research 36(6): 1886-1892. | Zbl 1179.90145
[035] 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. | Zbl 1179.90146
[036] Mosheiov, G. and Sarig, A. (2010). Scheduling with a common due-window: Polynomially solvable cases, Information Sciences 180(8): 1492-1505. | Zbl 1182.90047
[037] 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.
[038] 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. | Zbl 1082.90041
[039] Wang, J.-B. (2006). A note on scheduling problems with learning effect and deteriorating jobs, International Journal of Systems Science 37(12): 827-833. | Zbl 1126.90347
[040] 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. | Zbl 1221.90050
[041] Weng, M. and Ventura, J. (1996). A note on common due window scheduling, Production and Operations Management 5(2): 194-200.
[042] Winczaszek, M. (2006). Selected Scheduling Problems with Due Window Assignment, Ph.D. thesis, Wrocław University of Technology, Wrocław, (in Polish). | Zbl 1182.68028
[043] Wright, T.P. (1936). Factors affecting the cost of airplanes, Journal of Aeronautical Science 3(2): 122-128.
[044] 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. | Zbl 1068.90066
[045] Wu, Y. and Lai, K. (2007). A production scheduling strategy with a common due window, Computers & Industrial Engineering 53(2): 215-221.
[046] 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. | Zbl 1049.90513
[047] 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. | Zbl 1202.90149
[048] 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. | Zbl 1183.90203
[049] 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. | Zbl 0993.90044
[050] Yeung, W., Oguz, C. and Cheng, T. (2001b). Single-machine scheduling with a common due window, Computers & Operations Research 28(2): 157-175. | Zbl 0990.90050
[051] 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. | Zbl 1251.90209