A Literature Survey for Earliness/Tardiness Scheduling Problems with Learning Effect

Abstract

When a task or work is done continuously, there will be an experience so following times needs of required resources (manpower, materials, etc.) will be reduced. This learning curve described first by Wright. Wright determined how workmanship costs decreased while proceed plain increasing. This investigations correctness found consistent by plain producers. Learning effect is an effect that, works can be done in shorter time in the rate of repeat of work with repeating same or similar works in production process. Nowadays classical production systems adapted more acceptable systems with new approaches. Just in time production system (JIT) philosophy is one of the most important production system philosophies. JIT which is known production without stock stands on using all product resources optimum. Minimization problem of Earliness/Tardiness finishing penalty, which we can describe Just in time scheduling, appeared by inspired from JIT philosophy. In this study, there is literature survey which directed to earliness/tardiness performance criteria and learning effect processing in scheduling and as a result of this it is obtained some establishing for literature.

Keywords

• Scheduling, Earliness/Tardiness, Learning effect, Literature survey.

Öğrenme Etkili Erken/Geç Tamamlanma Çizelgeleme Problemleri İçin bir Literatür Araştırması

Öz

Bir görev veya iş sürekli yapıldığı takdirde belirli bir alışkanlık ve öğrenme olur ve ilerleyen zamanlarda bu işi tamamlamak için gerekli kaynaklara olan (işgücü, malzeme, vb.) ihtiyaç azalır. Bu "Öğrenme Eğrisi" ile ilk kez Wright tarafından tanımlanmıştır. Wright uçakların üretiminde üretilen uçak sayısı artarken direk işçilik maliyetlerinde nasıl bir azalma olduğunu tespit etmiştir. Bu gözlemin doğruluğu uçak üreticileri tarafından da tutarlı bulunmuştur. "Öğrenme Etkisi" ise; aynı veya benzer işlerin tekrarlanmasıyla üretim sürecinde işlerin tekrar sayısı nispetinde daha kısa sürede yapılmasını ifade eden etkidir. Günümüzde klasik üretim sistemlerine yeni yaklaşımlarla çağın gereklerine daha uygun sistemler uyarlanmıştır. Tam Zamanında Üretim Sistemi (TZÜ) felsefesi de en önemli modern üretim felsefelerinden biridir. Stoksuz üretim veya "0" envanter gibi isimlerle de bilinen TZÜ, tüm üretim kaynaklarının optimum kullanımı ilkesine dayanır. Tam zamanında çizelgeleme olarak ta nitelendirebileceğimiz Erken(Earliness)/Geç(Tardiness) tamamlanma cezalarının minimizasyonu problemi TZÜ felsefesinden esinlenerek ortaya çıkmıştır. Bu çalışmada çizelgelemede erken/geç tamamlanma performans kriteri ve öğrenme etkili işleme özelliğinin dikkate alındığı yayınlara yönelik literatür taraması ve sonucunda literatüre yönelik bazı tespitler yapılmıştır.

Anahtar Kelimeler

• Çizelgeleme, E/G tamamlanma, Öğrenme etkisi, Literatür tarama.

Kaynakça

1. Abdul-Razaq, T. and Potts, C. 1988. Dynamic programming state-space relaxation for single-machine scheduling, Journal of Operational Research Society. (39), 141-152.
2. Acar, N. 2002. Tam Zamanında Üretim, MPM Yayınları No: 542. Ankara.
3. Adamopoulos, G.I. and Pappis, C.S. 1998. Scheduling under a common due date on parallel unrelated machines, European Journal of Operational Research. (105), 495-501.
4. Alidaee, B., Kochenberger, G.A. and Ahmadian, A. 1994. Minimization total absolute flow time deviation in single and multiple machine scheduling, The Journal of the Operational Research Society, 45 (9), 1077-1087.
5. Allahverdi, A., Gupta, J.N.D. and Aldowaisan, T. 1999. A review of scheduling research involving setup consideration, OMEGA. (27), 219-239.
6. Bachman, A. and Janiak, A. 2004. Scheduling Jobs with Position-Dependent Processing Times, Journal of the Operational Research Society. (55), 257-264.
7. Bagchi, U., Sullivan, R. S. and Chang, Y.L. 1987a. Minimizing mean squared deviation of completion times about a common due date, Management Science. (33), 894-906.
8. Bagchi, U., Chang, Y.L. and Sullivan, R.S. 1987b. Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date, Naval Research Logistics. (34), 739-751.

9. Bagchi, U. 1987. Due date or deadline assignment to multi-job orders to minimize total penalty in the one machine scheduling problem, Presented at the ORSA/TIMS Joint National Conference, St. Louis, 210-218.
10. Baker, K.R. and Scudder, G.D. 1990. Sequencing with earliness and tardiness penalties: A review, Operations Research. 38 (1), 22-36.
11. Baker, K.R. 1997. Elements of sequencing and scheduling, Dartmounth College, Hanover.
12. Bank, J. and Werner, F. 2001. Heuristics algorithms for unrelated parallel machine scheduling with a common due date, release dates and linear earliness tardiness penalties, Mathematical and Computer Modelling. (33), 363-383.
13. Bauman, J. and Jozefowska, J. 2006. Minimizing the earliness-tardiness costs on a single machine, Computers and Operations Research. (33), 32193230.
14. Biskup, D. 1999. Single-Machine Scheduling with Learning Considerations, European Journal of Operational Research. (115), 173-178.
15. Biskup, D. and Cheng, T.C.E. 1999. Multiple-Machine Scheduling with Earliness Tardiness And Completion Time Penalties, Computer&Operations Research. 26 (1), 45-57.
16. Biskup, D. and Feldmann, M. 2001. Benchmarks for scheduling on single/machine against restrictive and unrestrictive common due date, Computers&Operation Research. 28 (8), 787-801.
17. Biskup, D. and Simons, D. 2004. Common Due Date Scheduling with Autonomous and Induced Learning, European Journal of Operational Research. (159), 606–616.
18. Biskup, D. 2008. A State-of-the-Art Review on Scheduling with Learning Effects, European Journal Of Operational Research. (188), 315-329.
19. Celso, M.H., Debora, P.R. and Andre, B.M. 2005. Minimizing Earliness And Tardiness Penalties in A Single-Machine Problem with A Common Due Date, European Journal of Operational Research. (160), 190–201.
20. Chang, S.S. and Joo, U.G. 1992. A single machine scheduling problem with earliness/tardiness and starting time penalties under a common due date, Computers&Operations Research. 19 (8), 753766.
21. Chen, Z.L. 1997. Scheduling with batch setup times and earliness-tardiness penalties, European Journal of Operational Research. (96), 518-537.
22. Chen, P., Wu, C.C. and Lee, W.C. 2006. A Bi-Criteria TwoMachine Flowshop Scheduling Problem with A Learning Effect, Journal of The Operational Research Society. (57), 1113-1125.
23. Cheng, T. 1988. Optimal common due date with limited completion time deviation, Computers&Operations Research. 15 (2), 91-96.
24. Cheng, T.C.E. 1989. A heuristic for common due date assignment and job scheduling on Parallel Machines, Journal of Operational Research Society. (40), 1129-1135.
25. Cheng, T.C.E. and Chen, Z.L. 1994. Parallel machine scheduling problems with earliness and tardiness penalties, The Journal of the Operational Research Society. 45 (6), 685-695.
26. Cheng, T.C.E. and Wang, G. 2000. Single Machine Scheduling with Learning Effect Considerations, Annals Of Operations Research. (98), 273-290.
27. Cochran, E.B. 1960. New Concepts of The Learning Curve, The Journal of Industrial Engineering. (11), 317–327.
28. Coleman, B.J. 1992. A simple model for optimizing the single machine early/tardy problem with sequence-dependent setups, Production and Operation Management. (1), 225-228.
29. Conway R.W. and Schultz A. 1959. The Manufacturing Progress Function, The Journal of Industrial Engineering. (10), 39–54.
30. Day, G.S. and Montgomery, D.B. 1983. Diagnosing The Experience Curve, Journal of Marketing. (47), 44–58.
31. De, P., Ghosh, J.B. and Wells, C.E. 1989. A note on the minimization of mean squared deviation of completion times about a common due date, Management Science. (35), 1143-1147.
32. Du, J. and Leung, Y.T. 1990. Minimizing Total Tardiness on One Machine is NP-hard, Mathematics of Operations Research. (15), 483-495.
33. Eilon, S. and Chowdhury, I. 1977. Minimizing waiting time variance in the single machine problem, Management Science. (23), 567-575.
34. Emmons, H. 1987. Scheduling to a common due date on parallel uniform processors, Naval Research Logistics. (34), 803-810.
35. Eren, T. 2004. Çok Ölçütlü Akış Tipi Çizelgeleme Problemleri İçin Çözüm Yaklaşımları, Doktora Tezi, Gazi Ünv. Ankara.
36. Eren, T. ve Güner, E. 2004. Öğrenme Etkili Akış Tipi Çizelgelemede Ortalama Akış Zamanının En Küçüklenmesi, Gazi Ünv. Müh. Mim. Fak. Dergisi. (19), 119-124.
37. Eren, T. and Guner, E. 2007. Minimizing Total Tardiness in A Scheduling Problem with A Learning Effect, Applied Mathematical Modelling. (31), 1351-1361.
38. Feldman, M. and Biskup, D. 2003. Single-Machine Scheduling For Minimizing Earliness And Tardiness Penalties by Meta-Heuristic Approaches, Computer And Industrial Engineering. (44), 307323.
39. French, S. 1982. Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop, Ellis Horwood Ltd., England.
40. Fry, T.D. 1987. Armstrong R.D. and Blackstone J.H., Minimizing weighted absolute deviation in single machine scheduling, IIE Transactions. (19), 445450.
41. Garey, M.R., Tarjan, R.E. and Wilfong, G.T. 1988. One processor scheduling with symmetric earliness and tardiness penalties, Mathematics of Operations Research. (13), 330-348.
42. Ghemawat, P. 1985. Building Strategy on The Experience Curve–A Venerable Management Tool Remains Valuable – In The Right Circumstances, Harvard Business Review, 63 II, 143–149.
43. Gordon, V., Proth, J.M. and Chu, C. 2001. A survey of the state-of-the-art of common due date assignment and scheduling research, European Journal of Operational Research. (139), 1-25.
44. Gupta, S. and Sen, T. 1983. Minimizing a quadratic function of job lateness on a single machine, Engineering Costs Production Economics. (7), 181194.
45. Hall, N.G. 1986. Single and multi-processor models for minimizing completion time variance, Naval Research Logistics Quarterly. (33), 49-54.
46. Hall, N.G. and Posner, M.E. 1991. Earliness-Tardiness Scheduling Problems, I: Weighted deviation of completion times about a common due date, Operation Research. (39), 836-846.
47. Hall, N.G., Kubiak, W. and Sethi, S.P. 1991. Earlinesstardiness scheduling problems, I: Weighted deviation of completion times about a restrictive common due date, Operations Research. 39 (5), 847-856.
48. Heizer, J. and Render, B. 2001. Operations Management (6. Edition), Prentice Hall, New Jersey.
49. Hendel, Y. and Sourd, F. 2007. An improved earlinesstardiness timing algorithm, Computers and Operations Research. 34 (10), 2931-2938.
50. Hino, C.S., Ronconi, D.P. and Mendes, A.B. 2005. Minimizing earliness and tardiness penalties in a single-machine problem with a common due date, European Journal of Operational Research. (160), 190-201.
51. Kanet, J.J. 1981a. Minimizing variation of flow time in single machine systems, Management Science. (27), 1453-1459.
52. Kanet, J.J. 1981b. Minimizing the average deviation of job completion times about a common date, Naval Research Logistics Quarterly. (28), 643-651.
53. Kellegöz, T. 2006., Toplam Geç Bitirme Zamanının En Küçüklenmesi Performans Ölçütlü Permütasyon Akış Tipi Çizelgeleme Problemlerinin Çözümünde Genetik Algoritma Yaklaşımı, Yüksek Lisans Tezi, Kırıkkale Üniv., Kırıkkale.
54. Keyser, T.K. and Sarper H. 1991. A heuristic solution of the E/G problem with waiting costs and non-zero release times, Computers & Industrial Engineering. (21), 297-301.
55. Koulamas, C. 1996. Single machine scheduling with time windows and earliness/tardiness penalties, European Journal of Operational Research. (91), 190-202.
56. Koulamas, C. and Kyparisis, G.J. 2007. Single-Machine And Two Machine Flowshop Scheduling with General Learning Function, European Journal of Operational Research. (178), 402–407.
57. Kuo, W.H. and Yang, D.L. 2006a. Minimizing The Total Completion Time in A Single-Machine Scheduling Problem with A Time-Dependent Learning Effect, European Journal of Operational Research. (174), 1184–1190.
58. Kuo, W.H. and Yang, D.L. 2006b. Single-Machine Group Scheduling with A Time-Dependent Learning Effect, Computers&Operations Research. 33 (8), 2099-2112.
59. Kuo, W.H. and Yang, D.L. 2006c. Minimizing The Makespan In A Single Machine Scheduling Problem with A Time-Based Learning Effect, Information Processing Letters. (97), 64–67.
60. Kuo, W.H. and Yang, D.L. 2007. Single machine scheduling with past-sequence-dependent setup times and learning effects, Information Processing Letters. (102), 22-26.
61. Lapre´, M.A. 2000. Mukkherjee A.S. and Van Wassenhove L.N., Behind the Learning Curve: Linking Learning Activities to Waste Reduction, Management Science. (46), 597–611.
62. 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.
63. Lee, C.Y. 1991. Danusaputro S. L. And Lin C.S., Minimizing Weighted Number of Tardy Jobs And Weighted Earliness–Tardiness Penalties About A Common Due Date, Computers And Operations Research. (18), 379–389.
64. Lee, W.C., Wu, C.C. and Sung, H.J. 2004. A Bi-Criterion Single-Machine Scheduling Problem with Learning Considerations, Acta Informatica. (40), 303315.
65. Lee, W.C. and Wu, C.C. 2004. Minimizing Total Completion Time in A Two–Machine Flowshop with A Learning Effect, International Journal of Production. (88), 85-93.
66. Leung, J.Y.T. 2002. A dual criteria sequencing problem with earliness and tardiness penalties, Naval Research Logistics. (49), 422-431.
67. Liao, C.J. and Cheng, C.C. 2007. A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date, Computer&Industrial Engineering. (52), 404-413.
68. Liman, S.D. and Ramaswamy, S. 1994. Earliness-tardiness scheduling problems with a common delivery window, Operations Research Letters. (15), 195-203.
69. Liman, S.D., Panwalkar, S.S. and Thongmee, S. 1996. Determination of common due window location in a single machine scheduling problem, European Journal of Operational Research. (93), 68-74.
70. Lin, B.M.T. 2007. Complexity Results for Single-Machine Scheduling with Positional Learning Effects, Journal of The Operational Research Society. 58 (8), 1099-1102.
71. Mondal, S.A. and Sen, A.K. 2001. Single Machine Weighted Earliness-Tardiness Penalty Problem with A Common Due Date, Computer And Operations Research. (28), 649-669.
72. Mosheiov, G. 2001a. Scheduling problem with learning effect, European Journal Of Operational Research. (132), 687-693.
73. Mosheiov, G. 2001b. Parallel machine scheduling with learning effect, Journal of The Operational Research Society. (52), 1165-1169.
74. Mosheiov, G. and Shadmon, M. 2001. Minmax earliness-tardiness costs with unit processing time jobs, European Journal of Operational Research. (130), 638-652.
75. Mosheiov, G. and Sidney, J.B. 2003. Scheduling with General Job-Dependent Learning Curves, European Journal Of Operational Research. (147), 665670.
76. Mosheiov, G. and Sidney, J.B. 2005. Note on Scheduling with General Learning Curves to Minimize Number of Tardy Jobs, Journal of The Operational Research Society, 56 (1), 110-112.
77. Öğe, M., 2001. Tam Zamanında (JIT) Sistemi ve Tekstil Sektöründe Bir Uygulama, Yüksek Lisans Tezi, Marmara Ünv., İstanbul.
78. Panwalkar, S.S., Smith, M.L. and Seidmann, A. 1982. Common due date assignment to minimize total penalty for the one machine scheduling problem, Operations Research, 30, 391-399.
79. Panwalkar, S.S. and Liman, S.D. 2002. Single operation earliness-tardiness scheduling with machine activation cost, IIE Transactions, 34, 509-513.
80. Pinedo, M. 1995. Scheduling: Theory, Algoritms and Systems, Prentice Hall, NewJersey.
81. Pinedo, M. and Chao, X. 1999. Operation Scheduling with Applications in Manufacturing and Services, Mc Graw Hill, NewYork.
82. Rym, M. 2007. Minimizing Total Earliness And Tardiness on A Single machine using a hybrid heuristic, Computer&Operations Research. 34 (10), 31263142.
83. Sakuraba, C.S., Ronconi, D.P. and Sourd, F. 2009. Scheduling in a two-machine flowshop for the minimization of the mean absolute deviation from a common due date, Computers&Operations Research. 36 (1), 60-72.
84. Sarper, H. 1995. Minimizing the sum of absolute deviations about a common due date for the two-machine flow shop problem, Applied Mathematical Modelling. 19 (3), 153-161.
85. Schaller, J.E. and Gupta, J.N.D. 2008. Single machine scheduling with family setups to minimize total earliness and tardiness, European Journal of Operation Research. (187), 1050-1068.
86. Seidmann, A., Panwalkar, S.S. and Smith, M.L. 1981. Optimal assignment of due-dates for a single processor scheduling problem, International Journal of Production Research, 19 (4), 393-399.
87. Shabtay, D. 2008. Due date assignments and scheduling a single machine with a general earliness/ tardiness cost function, Computers&Operation Research. 35 (5), 1539-1545.
88. Soroush, S.M. and Fredendall, L.D. 1994. The stochastic single machine scheduling problem with earliness-tardiness costs, European Journal of Operational Research. (77), 287-302.
89. Sun H. and Wang, G. 2003. Parallel machine earliness and tardiness scheduling with proportional weights, Computers and Operations Research. (30), 801-808.
90. Sundararaghavan, P.S. and Ahmed, M.U. 1984. Minimizing the sum of absolute lateness in single machine and multimachine scheduling”, Naval Research Logistics Quarterly. (31), 325-333.
91. Sundararaghavan, P.S. and Kunnathur, A.S. 1994. Single machine scheduling with start time dependent processing time: Some solvable cases, European Journal of Operational Research. 78 (3), 394-403.
92. Szwarc W. and Mukhopadhyay S.K. 1995. Optimal timing schedules in earliness-tardiness single-machine sequencing, Naval Research Logistics. (42), 1109-1114.
93. Toksarı, M.D. and Güner, E. 2008. Parallel machine earliness/tardiness scheduling problem under the effects of position based learning and linear/ nonlinear deterioration, Computers&Operations Research, Accepted Manuscript.
94. Valente, J.M.S. and Alves, R.A.F.S. 2005. Filtered and recovering beam search algorithms for early/tardy scheduling problem with no idle time, Computers and Industrial Engineering. (48), 363-375.
95. Vani, V. and Raghavachari, M. 1987. Deterministic and random single machine scheduling with variance minimization, Operations Research. (35), 111-120.
96. Venezia, I. 1985. On The Statistical Origins of The Learning Curve, European Journal of Operational Research. (19), 191–200.
97. Ventura J.S., Kim D. and Garriga F. 2005. Single machine earliness-tardiness scheduling with resourcedependent release dates, European Journal of Operational Research. (142), 52-69.
98. Wang, J.B. and Xia, Z.Q. 2005. Flow-shop Scheduling with A Learning Effect, Journal of the Operational Research Society. (56), 1325–1330.
99. Wang, J.B. 2006. A Note on Scheduling Problems with Learning Effects and Deteriorating Jobs, International Journal of Systems Science. (37), 827–833.
100. Wang, X. and Cheng, T.C.E. 2007. Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan, European Journal of Operational Research. (178), 57–70.
101. Wang, J.B. 2007., Single-Machine Scheduling Problems with The Effects of Learning and Deterioration. Omega. (35), 397–402.
102. Wright T.P. 1936. Factors Affecting the Cost of Airplanes, Journal of the Aeronautical Sciences. (3), 122128.
103. Yano, C. A. and Kim, Y. D. 1991. Algorithms for a class of single-machine weighted tardiness and earliness problems, European Journal of Operational Research, 52, 167-178. Yelle, L.E. 1979. The Learning Curve: Historical Review and Comprehensive Survey, Decision Science. (10), 302-328.
104. Zhao, C.L., Zhang, Q.L. and Tang, H.Y. 2004. Machine Scheduling Problems with Learning Effects, Dynamics of Continuous, Discrete and Impulsive Systems, Series A: Mathematical Analysis. (11), 741750.
105. Zhu, Z. and Heady, R.B. 2000. Minimizing the sum of earliness/tardiness in multi-machine scheduling: a mixed integer programming approach, Computers&Industrial Engineering. (38), 297-305.