Mevsimsel Rezervasyon Sistemlerinde Kaynak Planlama ve Çizelgeleme İçin Etkin Çözüm Algoritmaları

Year 2025, Volume: 59 Issue: 1, 115 - 132, 22.01.2025

Uğur Eliiyi

https://doi.org/10.51551/verimlilik.1521438

Abstract

Amaç: Bu çalışmada, rezervasyon sistemlerinde eş zamanlı kapasite planlama ve çizelgeleme kararlarını optimize eden bir problem için etkin çözüm algoritmaları önerilmektedir. Problem özellikle turizmde otel veya koltuk rezervasyonları, sağlık sistemlerinde operasyon ve tedavi rezervasyonları ya da liman lojistik operasyonları gibi randevu/rezervasyon ile çalışan sistemler için önemlidir.
Yöntem: İncelenen optimizasyon problemi, işleme alınan rezervasyonlara ait net getirinin maksimize edilmesi amacıyla, çizelgeleme ve dinamik kapasite belirleme kararlarının eş zamanlı olarak verilmesini içermektedir. Problemin yapısal özelliklerini kullanan rastgele bir inşa edici sezgisel yöntem ile etkili iyileştirme algoritmaları önerilmiştir. Algoritma performansını test etmek amacıyla kapsamlı hesaplamalı deneyler gerçekleştirilmiştir.
Bulgular: Geliştirilen yaklaşım hem çözüm kalitesi hem de zaman açısından mükemmel performans göstermektedir. Sezgisel yöntem 200 rezervasyona kadar CPLEX'e göre çözüm süresi ve kalitesi açısından üstündür. Algoritmanın performansı, problemin büyüklüğü ile değişmemektedir.
Özgünlük: Bu çalışma, bu önemli problem için sezgisel çözümler öneren ilk çalışmadır. Kaynak kullanımı ve çizelgelemenin optimizasyonu yoluyla birçok sektörde önemli sosyal ve ekonomik katkılar elde edilebilir. Geliştirilen hızlı ve etkili problem çözme teknikleri ileri araştırmaların önünü açacaktır.

Keywords

Zaman Pencereli Çizelgeleme, Kapasite Planlama, Rezervasyon Sistemleri, Optimizasyon

Efficient Solution Algorithms for Resource Planning and Scheduling in Seasonal Reservation Systems

Abstract

Purpose: In this study, efficient solution algorithms are proposed for a problem which simultaneously optimizes capacity planning and scheduling decisions in reservation systems. The problem is especially important for systems involving appointments/reservations, such as hotel or seat reservations in tourism, operation and treatment reservations in healthcare systems, or port logistics operations.
Methodology: The optimization problem studied involves concurrent decisions of scheduling and dynamic capacity determination, with an objective of maximizing the net return gained from the served appointments. A randomized constructive heuristic exploiting problem’s structural characteristics is proposed together with effective improvement procedures. Extensive computational experimentation is conducted in order to test algorithm performance.
Findings: The developed approach performs excellently in both solution quality and time. With up to 200 reservations, the heuristic technique outperforms CPLEX in terms of solution time and quality. The algorithm's performance remains unchanged as the size of the problem increases.
Originality: This study presents the first heuristic approach to solving this significant problem. Through optimization of resource utilization and scheduling, substantial positive social and economic impact on a number of business sectors can be obtained. The efficient problem-solving techniques developed will pave the way for future research.

Keywords

Scheduling with Time Windows, Capacity Planning, Reservation Systems, Optimization

References

• Azizoglu, M. and Bekki, B. (2008). “Operational Fixed Interval Scheduling Problem on Uniform Parallel Machines”, International Journal of Production Economics, 112(2), 756-768. https://doi.org/10.1016/j.ijpe.2007.06.004
• Bard, J.F. and 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. https://doi.org/10.1002/nav.20118
• Barshan, M., Moens, H., Famaey, J. and De Turck, F. (2016). “Deadline-Aware Advance Reservation Scheduling Algorithms for Media Production Networks”, Computer Communications, 77(1), 26–40.
• Eliiyi, D.T. and Azizoglu, M. (2009). “A Fixed Job Scheduling Problem with Machine-Dependent Job Weights”, International Journal of Production Research, 47(9), 2231-2256. https://doi.org/10.1080/00207540701499499
• Eliiyi, D.T. and 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. https://doi.org/10.1016/j.ijpe.2011.03.018
• Eliiyi, D.T., Korkmaz, A.G. and Çiçek, 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. https://doi.org/10.3846/1392-8619.2009.15.245-266
• Eliiyi, U. (2021). “Seasonal Reservation Scheduling with Resource Costs: A Mathematical Modeling Approach”, İzmir İktisat Dergisi, 36(2), 409-422. https://doi.org/10.24988/ije.202136211
• Faigle, U., Kern, W. and Nawijn, W.M. (1999). “A Greedy Online Algorithm for the k-track Assignment Problem”, Journal of Algorithms, 31(1), 196-210. https://doi.org/10.1006/jagm.1998.1001
• Fischetti, M., Martello, S. and Toth, P. (1987). “The Fixed Job Schedule Problem with Spread-Time Constraints”, Operations Research, 35(6), 849-858. https://doi.org/10.1287/opre.35.6.849
• Fischetti, M., Martello, S. and Toth, P. (1989). “The Fixed Job Schedule Problem with Working-Time Constraints”, Operations Research, 37(3), 395-403. https://doi.org/10.1287/opre.37.3.395
• Fischetti, M., Martello, S. and Toth, P. (1992). “Approximation Algorithms for Fixed Job Schedule Problems”, Operations Research, 40(S1), 96-108. https://doi.org/10.1287/opre.40.1.S96
• Gabrel, V. (1995). “Scheduling Jobs within Time Windows on Identical Parallel Machines”, European Journal of Operational Research, 83(2), 320-329. https://doi.org/10.1016/0377-2217(95)00010-N
• Garcia, J.M. and Lozano, S. (2005). “Production and Delivery Scheduling Problem with Time Windows”, Computers & Industrial Engineering, 48(4), 733-742. https://doi.org/10.1016/j.cie.2004.12.004
• Gertsbakh, I. and Stern, H.I. (1978). “Minimal Resources for Fixed and Variable Job Schedules”, Operations Research, 26(1), 68-85. https://doi.org/10.1287/opre.26.1.68
• Kolen, A.J.W. and Kroon, L.G. (1991). “On the Computational Complexity of (Maximum) Class Scheduling”, European Journal of Operational Research, 54(1), 23-38. https://doi.org/10.1016/0377-2217(91)90320-U
• Kolen, A.J.W. and Kroon, L.G. (1992). “License Class Design: Complexity and Algorithms”, European Journal of Operational Research, 63(3), 432-444. https://doi.org/10.1016/0377-2217(92)90160-B
• Kolen, A.J.W. and Kroon, L.G. (1993). “On the Computational Complexity of (Maximum) Shift Class Scheduling”, European Journal of Operational Research, 64(1), 138-151. https://doi.org/10.1016/0377-2217(93)90014-E
• Kolen, A.J.W., Lenstra, J.K., Papadimitriou, C.H. and Spieksma, F.C.R. (2007). “Interval Scheduling: A Survey”, Naval Research Logistics, 54(5), 530-543. https://doi.org/10.1002/nav.20231
• Kovalyov, M.Y., Ng, C.T. and Cheng, T.C.E. (2007). “Fixed Interval Scheduling: Models, Applications, Computational Complexity and Algorithms”, European Journal of Operational Research, 178(2), 331-342.
• Rojanasoonthon, S., Bard, J.F. and 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.
• Rojanasoonthon, S. and Bard, J.F. (2005). “A GRASP for Parallel Machine Scheduling with Time Windows”, INFORMS Journal on Computing, 17(1), 32-51. https://doi.org/10.1287/ijoc.1030.0048
• Spieksma, F.C.R. (1999). “On the Approximability of An Interval Scheduling Problem”, Journal of Scheduling, 2(5), 215-227. https://doi.org/10.1002/(SICI)1099-1425(199909/10)2:5%3C215::AID-JOS27%3E3.0.CO;2-Y
• Steiger, C., Walder, H. and Platzner, M. (2004). “Operating Systems for Reconfigurable Embedded Platforms: Online Scheduling of Real-Time Tasks”, IEEE Transactions on Computers, 53(11), 1393–1407. https://doi.org/10.1109/TC.2004.99
• Wolfe, W.J. and Sorensen, S.E. (2000). “Three Scheduling Algorithms Applied to the Earth Observing Systems Domain”, Management Science, 46(1), 148-168. https://doi.org/10.1287/mnsc.46.1.148.15134
• Yu, G. and Jacobson, S.H. (2020). “Primal-Dual Analysis for Online Interval Scheduling Problems”, Journal of Global Optimization, 77, 575–602. https://doi.org/10.1007/s10898-020-00880-5