The Shift Minimization Personnel Task Scheduling Problem: An Effective Lower Bounding Procedure

Öz

This study considers the shift minimization personnel task scheduling problem, which is to assign a set of tasks with fixed start and finish times to a minimum number of workers from a heterogeneous workforce. An effective lower bounding procedure based on solving a new integer programming model of the problem is proposed for the problem. An extensive computational study on benchmark data sets reveals that the proposed lower bounding procedure outperforms those existing in the literature and consistently and rapidly yields high quality lower bounds that are necessary for the decision makers to assess the quality of the obtained schedules. 

Anahtar Kelimeler

• scheduling,integer programming

The Shift Minimization Personnel Task Scheduling Problem: An Effective Lower Bounding Procedure

Öz

Bu çalışmada, başlangıç ve bitiş zamanları belli olan bir grup görevin, türdeş olmayan bir işgücünden en az sayıdaki çalışana atandığı bir vardiya enküçükleyen personel görev çizelgelemesi problemi ele alınmıştır. Bu problem için, problemin yeni bir tamsayılı programlama modelini çözmeye dayalı etkin bir alt sınır yöntemi önerilmiştir. Sayısal sonuçlar, önerilen modelin, literatürde varolan yöntemlerden daha üstün olduğunu ve karar vericilerin elde edilen çizelgelerin kalitelerini değerlendirebilmeleri için gerekli olan yüksek kaliteli alt sınırları tutarlı ve hızlı bir şekilde verdiğini göstermektedir.

 

 

Anahtar Kelimeler

• Çizelgeleme,tamsayılı programlama

Kaynakça

1. Eliiyi, D.T., M. Azizoğlu (2009), “A Fixed Job Scheduling Problem with Machine-Dependent Job Weights”, International Journal of Production Research, 47, 2231–2256.
2. Ernst, A.T., H. Jiang, M. Krishnamoorthy, B. Owens, D. Sier (2004), “An Annotated Bibliography of Personnel Scheduling and Rostering”, Annals of Operations Research, 127, 21–144.
3. Fages, J.G., T. Lapegue (2013), “Filtering Atmostnvalue with Difference Constraints: Application to the Shift Minimisation Personnel Task Scheduling Problem”, Lecture Notes in Computer Science, 8124, 63–79.
4. Gupta, U.L., D.T. Lee, J.T. Leung (1979), “An Optimal Solution for the Channel-Assignment Problem”, IEEE Transactions on Computers, 28, 807–810.
5. Kolen, A.W.J., J.K. Lenstra, C.H. Papadimitriou, F.C.R. Spieksma (2007), “Interval Scheduling: A survey”, Naval Research Logistics, 54, 530–543.
6. Kovalyov, M.Y., C.T. Ng, T.C.E. Cheng (2007), “Fixed Interval Scheduling: Models, Applications, Computational Complexity and Algorithms”, European Journal of Operational Research, 178, 331–342.
7. Krishnamoorthy, M., A.T. Ernst, D. Baatar (2012), “Algorithms for Large Scale Shift Minimisation Personnel Task Scheduling Problems”, European Journal of Operational Research, 219, 34–48.
8. Kroon, L.G., M. Salomon, L.N.V. Wassenhowe (1995), “Exact and Approximation Algorithms for the Operational Fixed Interval Scheduling Problem”, European Journal of Operational Research, 82, 190–205.

9. Kroon, L.G., M. Salomon, L.N.V. Wassenhowe (1997), “Exact and Approximation Algorithms for the Tactical Fixed Interval Scheduling Problem”, Operations Research, 45, 624–638.
10. Lin, S.-W., K.C. Ying (2014), “Minimizing Shifts for Personnel task Scheduling Problems: A three-Phase Algorithm”, European Journal of Operational Research, 237, 323–334.
11. Nemhauser, G.L., L.A. Wolsey (1988), Integer and Combinatorial Optimization, New York: Wiley.
12. Smet, P., G. Vanden Berghe, “A Matheuristic Approach to the Shift Minimization Personnel task Scheduling Problem”, 9th International Conference on the Practice and Theory of Automated Timetabling, 2012, 145–160.
13. Smet, P., T. Wauters, M. Mihaylov, G. Vanden Berghe (2014), “The Shift Minimization Personnel Task Scheduling Problem: A new Hybrid Approach and Computational Insights”, OMEGA, 46, 64–73.