Scheduling problems with a common due window assignment: A survey

Adam Janiak; Tomasz Kwiatkowski; Maciej Lichtenstein

International Journal of Applied Mathematics and Computer Science (2013)

  • Volume: 23, Issue: 1, page 231-241
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Adam Janiak, Tomasz Kwiatkowski, and Maciej Lichtenstein. "Scheduling problems with a common due window assignment: A survey." International Journal of Applied Mathematics and Computer Science 23.1 (2013): 231-241. <http://eudml.org/doc/251295>.

@article{AdamJaniak2013,
abstract = {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.},
author = {Adam Janiak, Tomasz Kwiatkowski, Maciej Lichtenstein},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {scheduling; due window assignment; earliness/tardiness; practical example},
language = {eng},
number = {1},
pages = {231-241},
title = {Scheduling problems with a common due window assignment: A survey},
url = {http://eudml.org/doc/251295},
volume = {23},
year = {2013},
}

TY - JOUR
AU - Adam Janiak
AU - Tomasz Kwiatkowski
AU - Maciej Lichtenstein
TI - Scheduling problems with a common due window assignment: A survey
JO - International Journal of Applied Mathematics and Computer Science
PY - 2013
VL - 23
IS - 1
SP - 231
EP - 241
AB - 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.
LA - eng
KW - scheduling; due window assignment; earliness/tardiness; practical example
UR - http://eudml.org/doc/251295
ER -

References

top
  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. Zbl0699.90052
  3. Biskup, D. (1999). Single-machine scheduling with learning considerations, European Journal of Operational Research 115(1): 173-178. Zbl0946.90025
  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. Zbl1171.90394
  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. Zbl0955.90029
  7. Garey, M. and Johnson, D. (1978). Strong NP-completness results: Motivation, examples, and implications, Journal of the ACM 25(3): 499-508. Zbl0379.68035
  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. Zbl1273.93050
  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. Zbl1009.90054
  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. Zbl0411.90044
  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. Zbl0749.90041
  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. Zbl1245.90031
  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. Zbl1162.90457
  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. Zbl1162.90456
  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. Zbl1182.68028
  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. Zbl1182.68028
  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 Applied Mathematics 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. Zbl0947.90588
  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. Zbl1098.90031
  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. Zbl0890.90104
  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. Zbl1140.90405
  30. Limana, S. and Ramaswamy, S. (1994). Earliness-tardiness scheduling problems with a common delivery window, Operations Research Letters 15(4): 195-203. Zbl0814.90049
  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. Zbl0573.90054
  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. Zbl1055.90036
  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. Zbl1144.90391
  35. Mosheiov, G. and Sarig, A. (2009a). Minmax scheduling problems with a common due-window, Computers & Operations Research 36(6): 1886-1892. Zbl1179.90145
  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. Zbl1179.90146
  37. Mosheiov, G. and Sarig, A. (2010). Scheduling with a common due-window: Polynomially solvable cases, Information Sciences 180(8): 1492-1505. Zbl1182.90047
  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. Zbl1082.90041
  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. Zbl1126.90347
  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. Zbl1221.90050
  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). Zbl1182.68028
  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. Zbl1068.90066
  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. Zbl1049.90513
  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. Zbl1202.90149
  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. Zbl1183.90203
  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. Zbl0993.90044
  51. Yeung, W., Oguz, C. and Cheng, T. (2001b). Single-machine scheduling with a common due window, Computers & Operations Research 28(2): 157-175. Zbl0990.90050
  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. Zbl1251.90209

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.