DENİZ HELİKOPTER PİLOTLARI İÇİN İŞ YÜKÜNE BAĞLI KAYNAK KISITLI BİR ÇİZELGELEME PROBLEMİ

Abstract

Bu çalışmada; az çeşit yüksek sayıdaki (yüksek multiplisite) işlerin, organizasyona özgü çalışma düzeni ve kısıtlar eşliğinde farklı bir çizelge yapısı altında tek makinede çizelgelenmesini amaçlayan, gerçek yaşam probleminden kurgulanan bir problem ele alınmıştır. Gündüz ve gece olarak ikiye ayrılan çizelge yapısında, işlerin yapıldığı periyoda göre operatör ek kaynağının tüketilmesi ve çizelgelenmesi açısından farklı kısıtlar dikkate alınmaktadır. Gece periyodunda yapılan işler öncesi ve sonrasında operatöre yönelik özel dinlenme süreleri kısıtları bulunmakta, gece periyodunda yapılan işlerin hem süre hem de sayı olarak gündüz periyodundaki iş çizelgelemesine etkileri bulunmaktadır. Ayrıca, operatörün günlük iş yükü normal ve ağır olarak iki kategoriye ayrılmaktadır. Ardışık günlerde ağır kategori iş yükü oluştuğunda özel dinlenme sürelerinin çizelgelenmesi gerekmektedir. Problemin tam sayılı programlama modeli sunulmuştur. Açgözlü kurucu sezgisel algoritmalar ile kısa sürede elde edilen uygun çözümler hem üst sınır hem de sıcak başlangıç olarak tam çözüm yaklaşımında kullanılmıştır. Son olarak, çözüm yaklaşımlarının etkinliği farklı büyüklükteki örnek test problemleri kullanılarak karşılaştırılmış ve değerlendirilmiştir.

Keywords

• Çizelgeleme
• Ek Kaynaklar
• Yüksek Multiplisite
• Tam Sayılı Programlama
• Açgözlü Kurucu Sezgisel

A WORKLOAD DEPENDENT RESOURCE CONSTRAINED SCHEDULING PROBLEM FOR NAVY HELICOPTER PILOTS

Abstract

In this paper, we consider a problem inspired by a real-life problem, which aims to schedule high multiplicity jobs on a single machine by taking into account the organization-specific constraints in a different schedule structure. The schedule is daily with daytime and nighttime periods. The operator is considered as an additional resource that varies in terms of consumption and scheduling depending on the period. There are specific rest periods before and after night-period jobs, and night-period jobs affect both the daily working time and number of the jobs in the daytime- period. In addition, the operator's daily workload is divided into two categories: normal and heavy. If the workload is heavy on consecutive days, specific rest periods must be scheduled. The integer programming model of the problem is presented. The feasible solutions obtained in a short time with greedy constructive heuristic algorithms are used in the exact solution approach as both upper bound and warm-start point. Finally, the effectiveness of the solution approaches is compared and evaluated through numerical experiments carried out for a variety of problem instances of different sizes.

Keywords

• Scheduling
• Additional Resources
• High-Multiplicity
• Integer Programming
• Greedy Constructive Heuristic

References

1. Artigues, C., Demassey, S. & Neron, E. (2008). Resource Constrained Project Scheduling: Models, Algorithms, Extensions and Applications. France, John Wiley & Sons.
2. Barnhart, C., Cohn, A.M., Johnson, E.L., Klabjan, D., Nemhauser, G.L. & Vance, P.H. (2003). Airline Crew Scheduling. In: Hall, R.W. (eds) Handbook of Transportation Science. International Series in Operations Research & Management Science, Vol 56. Springer, Boston, MA. doi:10.1007/0-306-48058-1_14.
3. Bergh, J.V., Beliën, J., Bruecker P., Demeulemeester, E. & Boeck, L. (2013). “Personnel scheduling: A literature review”. European Journal of Operational Research, Vol. 226, pp. 367–385. doi:10.1016/j.ejor.2012.11.029.
4. Brucker, P., Drexl, A., Möhring, R., Neumann, K. & Pesch, E. (1999). “Resource-constrained project scheduling: Notation, classification, models, and methods”. European Journal of Operational Research, Vol. 112, pp. 3-41. doi:10.1016/S0377-2217(98)00204-5.
5. Brucker, P., Qu, R., & Burke, E. (2011). “Personnel scheduling: Models and complexity”. European Journal of Operational Research, Vol. 210, pp. 467-473. doi:10.1016/j.ejor.2010.11.017.
6. Burke, E. K., De Causmaecker, P., Berghe, G. V. & Van Landeghem, H. (2004). “The state of the art of nurse rostering”. Journal of Scheduling, Vol. 7, pp. 441-499. doi: 10.1023/B:JOSH.0000046076.75950.0b.
7. Dantzig, G.B. (1954). “Letter to the Editor---A Comment on Edie’s ‘Traffic Delays at Toll Booths’”. Journal of the Operations Research Society of America, Vol. 2, No. 3, pp. 339-341. doi:10.1287/opre.2.3.339.
8. Ernst, A.T., Jiang, H., Krishnamoorthy, M. & Sier, D. (2004). “Staff scheduling and rostering: a review of applications, methods and models”. European Journal of Operational Research, Vol. 153, pp. 3-27.

9. Gafarov, E. R., Lazarev, A. A., & Werner, F. (2011). “Single machine scheduling problems with financial resource constraints: Some complexity results and properties”. Mathematical Social Sciences, Vol. 62(1), pp. 7-13. doi:10.1016/ j.mathsocsci.2011.04.004.
10. Goel, A. (2009). “Vehicle Scheduling and Routing with Drivers’ Working Hours”. Transportation Science, Vol. 43(1), pp. 17-26. doi: 10.1287/trsc.1070.0226.
11. Goel, A. (2010). “Truck driver scheduling in the European Union”. Transportation Science, Vol. 44(4), pp. 429-441. doi:10.1287/trsc.1100.0330.
12. Goel, A., Archetti, C. & Savelsbergh, M. (2012). “Truck driver scheduling in Australia”. Computers & Operations Research, Vol. 39, pp. 1122-1132. doi:10.1016/j.cor.2011.05.021.
13. Goel, A. & Kok, L. (2012). “Truck Driver Scheduling in the United States”. Transportation Science, Vol. 46 (3), pp. 317-326. doi:/10.1287/trsc.1110.0382.
14. Graham, R. L., Lawler, E. E., Lenstra, J. K., & Kan, A. H. G. R. (1979). “Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey”. In Annals of Discrete Mathematics, Vol. 5, pp. 287–326. doi:10.1016/s0167-5060(08)70356-x.
15. Hartmann, S. & Briskorn, D. (2010). “A survey of variants and extensions of the resource-constrained project scheduling problem”. European Journal of Operational Research, Vol. 207 (1), pp. 1-14. doi:10.1016/j.ejor.2009.11.005.
16. Kok, A.L., Meyer, C.M., Kopfer, H.,Schutten, J.M.J. (2010). “A Dynamic Programming Heuristic for the Vehicle Routing Problem with Time Windows and the European Community Social Legislation”. Transportation Science, Vol. 44, Issue 4, pp. 442–454. doi:10.1287/trsc.1100.0331.
17. Özder, E., Özcan, E., & Eren, T. (2020). “A Systematic Literature Review for Personnel Scheduling Problems”. International Journal of Information Technology and Decision Making, Vol. 19, pp. 1695-1735. doi:10.1142/S0219622020300050.
18. Pinedo, M.L. (1995). Scheduling: Theory, Algorithms and Systems. Prentice-Hall, Englewood Cliffs.
19. Pinedo, M.L. (2007). Planning and Scheduling in Manufacturing and Services (Springer Series in Operations Research and Financial Engineering). New York, Springer.
20. Pinedo, M.L. (2022). Scheduling: Theory, Algorithms and Systems (6th ed.). Springer International Publishing. doi:10.1007/978-3-031-05921-6.
21. Portugal, R., Lourenço, H.R. & Paixão, J.P. (2009). “Driver scheduling problem modelling”. Journal of Public Transport, Vol. 1, pp. 103–120. doi:10.1007/ s12469-008-0007-0.
22. Regulation 561/2006. The harmonisation of certain social legislation relating to road transport and amending Council Regulations (EEC) 3821/85 and (EC) 2135/98 and repealing Council Regulation (EEC) 3820/85. European Parliament, Council of the European Union. http://data.europa.eu/eli/reg/2006/561/oj.
23. SHT-6A.50. (2014). Instruction on the Flight, Working and Rest Time of Flight Crew and its Implementation Rules. Directorate General of Civil Aviation. http://web.shgm.gov.tr/doc5/sht6arev06.pdf.
24. US Department of the Navy. (2013). Navy Planning, NWP 5-01. Washington, DC: Headquarters US Navy.
25. Ventura, J.A. & Kim, D. (2003). “Parallel machine scheduling with earliness-tardiness penalties and additional resource constraints”. Computers & Operations Research, Vol. 30, pp. 1945-1958. doi:10.1016/S0305-0548(02)00118-1.