Single Machine Scheduling with General Learning Functions: Optimal Solutions

Abstract

In traditional scheduling problems, most literature assumes that the processing time of a job is fixed. However, there are many situations where the processing time of a job depends on the starting time or the position of the job in a sequence. In such situations, the actual processing time of a job may be less than its normal processing time if it is scheduled later. This phenomenon is known as the ''learning effect''. In this study, we introduce general learning functions into a single-machine scheduling problems. We consider the following objective functions: (i) sum of weighted completion times, (ii) maximum lateness (iii) number of tardy jobs (iv) number of weighted tardy jobs. Non-linear programming models are developed for solving these problems.

Keywords

• Single machine scheduling, Learning functions, Non-linear programming models.

Tek Makineli Çizelgelemede Genel Öğrenme Fonksiyonları: Optimal Çözümler

Öz

Çizelgeleme literatürünün çoğunda işlerin işlem zamanları sabit kabul edilmiştir. Ancak işlerin işlem zamanlarında, başlama zamanı veya pozisyonuna bağlı olarak azalma görülebilmektedir. Bu olgu literatürde öğrenme etkisi olarak bilinmektedir. Bu çalışmada genel öğrenme fonksiyonlu tek makineli çizelgeleme problemleri ele alınacaktır. Ele alınan problemlerin amaç fonksiyonları: (i) toplam ağırlıklı tamamlanma zamanı (ii) maksimum gecikme, (iii) geciken iş sayısı (iv) ağırlıklı geciken iş sayısı şeklindedir. Problemleri çözmek için doğrusal-olmayan programlama modelleri geliştirilmiştir.

Anahtar Kelimeler

• Tek makineli çizelgeleme, Öğrenme fonksiyonları, Doğrusal-olmayan programlama modelleri.

References

1. Biskup, D., “A state-of-the-art review on scheduling with learning effects” European Journal of Operational Research, 188 (2), 315-329, 2008.
2. Biskup, D., “Single-machine scheduling with learning considerations” European Journal of Operational Researc,. 115, 173-178, 1999.
3. Mosheiov, G., “Scheduling problems with a learning effect”, European Journal of Operational Research, 132, 687-693, 2001.
4. Moore, J.M., “An n job, one machine sequencing algorithm for minimizing the number of tardy jobs” Management Science, 15, 102–109, 1968.
5. Mosheiov, G. Sidney, J.B., “Note on scheduling with general learning curves to minimize the number of tardy jobs”, Journal of the Operational Research Society, 56, 110– 112, 2005.
6. Zhao, C.L. Zhang, Q.L. Tang, H.Y., “Machine scheduling problems with learning effects”, Dynamics of Continuous, Discrete and Impulsive Systems, Series A: Mathematical Analysis, 11, 741-750, 2004.
7. Wu, C.C. Lee, W.C. Chen, T., “Heuristic algorithms for solving the maximum lateness scheduling problem with learning considerations”, Computers & Industrial Engineering, 52, 124-132, 2007.
8. Eren, T., “Zamana-bağımlı öğrenme etkili çizelgeleme probleminde maksimum gecikme minimizasyonu: Doğrusal-olmayan programlama modeli”, Gazi Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, 23 (2), 459-465, 2008.

9. Eren, T. Güner, E., “Minimizing total tardiness in a scheduling problem with a learning effect”, Applied Mathematical Modelling, 31, 1351-1361, 2007.
10. Eren, T. Güner, E., “A bicriteria scheduling with a learning effect: total completion time and total tardiness” INFOR: Information Systems and Operational Research, 45 (2), 75-81, 2007.
11. Wu, C.C. Lee, W.C., “Single-machine scheduling problems with a learning effect”, Applied Mathematical Modelling, 32, 1191–1197, 2008.
12. Eren, T., “İki ölçütlü zamana-bağımlı öğrenme etkili çizelgeleme problemi”, Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 14(1), 387-394, 2009.
13. Yin, Y. Xu, D. Wang, J., “Single-machine scheduling with a general sum-of-actual-processing-times based and job- position-based learning effect”, Applied Mathematical Modelling, 34, 3623–3630, 2010.
14. Lai, P.J. Lee, W.C., “Single-machine scheduling with general sum-of-processing-time-based and position- based learning effects”, Omega, 39, 467–471, 2011.
15. Lu, Y.Y. Wei, C.M. Wang, J.B., “Several single-machine scheduling problems with general learning effects”, Applied Mathematical Modelling, in press, 2012.
16. Wang, J.B., “Single-machine scheduling problems with the effects of learning and deterioration”, Omega. 35, 397–402, 2007.
17. Wang, X.R., “Single machine scheduling with time- dependent deterioration and exponential learning effect”, Computers & Industrial Engineering, 58, 58–63, 2010.
18. Huang, X. Wang, J.B. Wang, L.Y. Gao, W.J. Wang, J.B., “Single-machine scheduling problems with the effects of learning and deterioration”, Omega, 35, 397–402, 2007.
19. Huang, X. Wang, J.B. Wang, L.Y. Gao, W.J. Wang, X.R., “Single machine scheduling with time-dependent deterioration and exponential learning effect”, Computers & Industrial Engineering, 58, 58–63,2010.
20. Wu, Y.B., “A note on Single machine scheduling with time- dependent deterioration and exponential learning effect’’, Computers & Industrial Engineering, 61, 902–903, 2011.
21. Wu, Y.B. Wang, M.Z. Wang, J.B., “Some single-machine scheduling with both learning and deterioration effects”, Applied Mathematical Modelling, 35, 3731–3736, 2011.
22. Yin, Y. Xu, D., “Some single-machine scheduling problems with general effects of learning and deterioration”, Computers 61, 100–108, 2011. with Applications,
23. Wang, J.B. Hsu, C.J. Yang, D.L. 2012. “Single-machine scheduling with effects of exponential learning and general deterioration”, Applied Mathematical Modelling. In press.
24. Wang, J.B. Li, J.X., “Single machine past-sequence- dependent setup times scheduling with general position- dependent and time-dependent learning effects”, Applied Mathematical Modelling, 35, 1388–1395, 2011.
25. Yin, Y. Xu D. Huang, X., “Erratum to ‘‘Single machine past- sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects’’ [Appl. Math. Modell. 35, 1388–1395”, Applied Mathematical Modelling, 35, 5936–5938, 2011.
26. Lee, W.C., “A note on single-machine scheduling with general learning effect and past-sequence-dependent setup time”, Computers and Mathematics with Applications, 62, 2095–2100, 2011.
27. Bai, J. Wang, M.Z. Wang, J.B., “Single machine scheduling with a general exponential learning effect”, Applied Mathematical Modelling, 36, 829–835, 2012.
28. Eren, T., “Hazırlık ve taşıma zamanlarının öğrenme etkili olduğu tek makineli çizelgeleme problemi: Geciken iş sayısı Engineering Research and Development, 6 (6), 34-36, 2011. International Journal of
29. Eren, T., “Logaritmik toplam işlem zaman tabanlı öğrenme etkili tek makineli çizelgeleme: geciken iş sayısı minimizasyonu”, Nevşehir Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 1, 83-88, 2012.
30. Eren, T., “Zamana-bağımlı öğrenme etkili tek makineli çizelgeleme problemleri”, Sigma Mühendislik ve Fen Bilimleri Dergisi, basımda, 2012.
31. Koulamas, C. Kyparisis, G.J., “Single-machine and two- machine flowshop scheduling with general learning functions”, European Journal of Operational Research, 178, 402–407, 2007.
32. Wang, J.B., “Single-machine scheduling with general learning functions”, Computers and Mathematics with Applications, 56, 1941–1947, 2008.
33. GAMS 22.5, Development Corporation, GAMS– the solver manuals, GAMS user notes, Washington, DC, USA, 2007.