Kaynak Maliyetli Dönemsel Rezervasyon Çizelgeleme: Bir Matematiksel Modelleme Yaklaşımı

Abstract

Bu çalışmada, rezervasyon çizelgeleme ortamlarında eş zamanlı kapasite planlama ve çizelgeleme için yeni bir optimizasyon problemi önerilmiştir. Problem seyahat acentelerinin otel ve koltuk rezervasyonları veya sağlık turizminde operasyon ve tedavi rezervasyonları gibi dönemsel/sezonluk rezervasyon gerektiren pek çok sistemin optimizasyonu açısından önemlidir. Önerilen problemde işlenen rezervasyonlardan elde edilen net kârın maksimize edilmesi amaçlamaktadır. Kapasite ve çizelgeleme kararlarını içeren bu çizelgeleme problem hizmet endüstrisinde geniş uygulama alanına sahiptir ve bilgimiz dahilinde daha önce incelenmemiştir. Çalışmamızda optimal çözümler için bir tamsayı programlama modeli geliştirilmiş ve kapsamlı sayısal deneylerle farklı senaryolar altında model performansı ölçümlenmiştir. Deney sonuçları analiz edilerek yönetimsel etkileri tartışılmıştır.

Keywords

• Optimizasyon
• Çizelgeleme
• Tamsayılı Programlama
• Rezervasyon Çizelgeleme
• Zaman Aralıkları
• Kapasite Planlama

Seasonal Reservation Scheduling with Resource Costs: A Mathematical Modeling Approach

Abstract

In this study, a novel optimization problem for simultaneous capacity planning and scheduling in reservation scheduling environments is proposed. The problem is important for seasonal reservation systems such as hotel or seat reservations of travel agencies, or operation and treatment reservations in health tourism. The objective of the problem is to maximize the net profit gained from the processed reservations. To the best of our knowledge, the problem was not previously studied. An integer programming model is developed for exact solutions and extensive computational experimentation reveals model performance under different scenarios. The results are analyzed, and managerial implications are discussed.

Keywords

• Optimization
• Scheduling
• Integer Programming
• Reservation Scheduling
• Time Windows
• Capacity Planning

References

1. Arkin, A.M., & Silverberg, E.L. (1987). Scheduling Jobs with Fixed Start and End Times. Discrete Applied Mathematics, 18(1), 1–8.
2. Azizoglu, M., & Bekki, B. (2008). Operational fixed interval scheduling problem on uniform parallel machines. International Journal of Production Economics, 112(2), 756–768.
3. Bard, J.F., & Rojanasoonthon, S. (2006). A Branch-and-Price Algorithm for Parallel Machine Scheduling with Time Windows and Job Priorities. Naval Research Logistics, 53(1), 24–44.
4. Barshan, M., Moens, H., Famaey, J., & De Turck, F. (2016). Deadline-aware advance reservation scheduling algorithms for media production networks. Computer Communications, 77(1), 26–40.
5. Eliiyi, D.T. (2013). Integrating tactical and operational decisions in fixed job scheduling. Engineering Optimization, 45(12), 1449–1467.
6. Eliiyi, D.T., & Azizoglu, M. (2009). A Fixed Job Scheduling Problem with Machine-Dependent Job Weights. International Journal of Production Research, 47(9), 2231–2256.
7. Eliiyi, D.T., & Azizoglu, M. (2011). Heuristics for operational fixed job scheduling problems with working and spread time constraints. International Journal of Production Economics, 132(1), 107–121.
8. Eliiyi, D.T., Korkmaz, A.G., & Cicek, A.E. (2009). Operational Variable Job Scheduling with Eligibility Constraints: A Randomized Constraint-Graph-Based Approach. Technological and Economic Development of Economy, 15(2), 245–266.

9. Faigle, U., Kern, W., & Nawijn, W.M. (1999). A greedy online algorithm for the k-track assignment problem. Journal of Algorithms, 31(1), 196–210.
10. Fischetti, M., Martello, S., & Toth, P. (1987). The fixed job schedule problem with spread-time constraints. Operations Research, 35(6), 849–858.
11. Fischetti, M., Martello, S., & Toth, P. (1989). The Fixed Job Schedule Problem with Working-Time Constraints. Operations Research, 37(3), 395–403.
12. Fischetti, M., Martello, S., & Toth, P. (1992). Approximation Algorithms for Fixed Job Schedule Problems. Operations Research, 40(S1), S96–S108.
13. Gabrel, V. (1995). Scheduling jobs within time windows on identical parallel machines. European Journal of Operational Research, 83(2), 320–329.
14. Garcia, J.M., & Lozano, S. (2005). Production and delivery scheduling problem with time windows. Computers & Industrial Engineering, 48(4), 733–742.
15. Gertsbakh, I., & Stern, H.I. (1978). Minimal resources for fixed and variable job schedules. Operations Research, 26(1), 68–85.
16. Kolen, A.J.W., & Kroon, L.G. (1991). On the Computational Complexity of (Maximum) Class Scheduling. European Journal of Operational Research, 54(1), 23–38.
17. Kolen, A.J.W., & Kroon, L.G. (1992). License Class Design: Complexity and Algorithms. European Journal of Operational Research, 63(3), 432–444.
18. Kolen, A.J.W., & Kroon, L.G. (1993). On the Computational Complexity of (Maximum) Shift Class Scheduling. European Journal of Operational Research, 64(1), 138–151.
19. Kolen, A.J.W., Lenstra, J.K., Papadimitriou, C.H., & Spieksma, F.C.R. (2007). Interval scheduling: A survey. Naval Research Logistics, 54(5), 530–543.
20. Kovalyov, M.Y., Ng, C.T., & Cheng, T.C.E. (2007). Fixed interval scheduling: Models, applications, computational complexity and algorithms. European Journal of Operational Research, 178(2), 331–342.
21. Kroon, L.G. (1990). Job scheduling and capacity planning in aircraft maintenance, Ph.D. Thesis, Rotterdam School of Management, Erasmus University, The Netherlands.
22. Rojanasoonthon, S., Bard, J.F., & Reddy, S.D. (2003). Algorithms for parallel machine scheduling: a case study of the tracking and data relay satellite system. Journal of the Operational Research Society, 54(8), 806–821.
23. Rojanasoonthon, S., & Bard, J.F. (2005). A GRASP for parallel machine scheduling with time windows. INFORMS Journal on Computing, 17(1), 32–51.
24. Spieksma, F.C.R. (1999). On the approximability of an interval scheduling problem. Journal of Scheduling, 2(5), 215–227.
25. Steiger, C., Walder, H. & Platzner, M. (2004). Operating systems for reconfigurable embedded platforms: online scheduling of real-time tasks. IEEE Transactions on Computers, 53(11), 1393–1407.
26. Wolfe, W.J., & S.E. Sorensen (2000). Three scheduling algorithms applied to the earth observing systems domain. Management Science, 46(1), 148–168.
27. Yu, G., & Jacobson, S.H. (2020). Primal-dual analysis for online interval scheduling problems. Journal of Global Optimization, 77, 575–602.