An exact approach for a dynamic workforce scheduling problem

Abstract

Küresel ve ulusal kurallar ve düzenlemeler altında, belirli sayıdaki çalışanı planlı vardiyalara belirli çalışma ve dinlenme saatleri ile tatil gün/günlerine dikkat ederek atamak, teorik ve gerçek dünyadaki en karmaşık planlama konularından biridir ve işgücü planlama özelinde bir konudur. Bu konu, dikkate alınması gereken çok fazla kritere haiz olması nedeniyle, kolay ve basit bir planlama konusu olmasının tam aksine en karmaşık planlama problemleri olan NP-Hard problemlerinden biridir.Bu tezde, gerçek dünyada olabilecek örnek bir işgücü çizelgeleme sorununu ele alarak, işgücü çizelgelemesine ilişkin doğrudan ve dolaylı tüm maliyetlerini en aza indirmeye çalışan bir şirketi inceliyoruz. Belirli iş gücüne ve işle ile ilgili kısıtlamalara uygun olarak minimum maliyet çözümünü belirlemeyi amaçlıyoruz. Bu nedenle, bazı problemlerin örnekleri dâhil olmak üzere literatürdeki çalışmaları inceleyerek, temel karakteristik ve varsayımlarla birlikte problemimizi tanımlıyoruz. Probleme tam sayılı programlama ile kesin bir çözüm öneriyoruz ve bu yöntemin kabul edilebilir sürelerde yüksek kalitede çözümler ürettiğini gözlemliyoruz. Bir saat koşma süresince elde edilen çözümlerin optimum aralığının %19.38 olduğunu görüyoruz.

Taking into account the global and national rules and regulations, assigning a given number of employees to planned shifts while paying attention to required working hours, rest times and off day/days is one of the most complex planning issue both in literature and real world, and this is the concept of workforce planning in particular. This issue is deserved to have an intense concern in real world because there are so many considerations that it is not an easy and simple planning issue; rather, one of the most complex problems, namely a subject of NP-Hard Problems.In this thesis, as a prototype of a possible real world problem in workforce scheduling, we study a company trying to minimize the all the direct and indirect cost related to workforce scheduling. Satisfying the given limited workforce and labor-related constraints, our aim is to determine the minimum cost solution. This is why, reviewing the studies in the literature including with examples of some problems, we define our problem along with the main characteristics and assumptions. We propose a solution approach based on an exact solution of the integer programming formulation of the problem and observe that our solution approach generates high quality solutions in acceptable solution time. The optimality gap of the solutions obtained in one-hour computational time limit is only 19.38%.