یک ارزیابی تطبیقی ​​مدل سازی برای بررسی مشکل برنامه ریزی شیفت کار

The labor shift scheduling problem has traditionally been formulated using the set covering approach proposed by Dantzig, G.B. [1954. Operations Research 2 (3), 339–341]. The size of the resulting integer model with this approach, however, has been found to be very large to solve optimally in most practical applications. Recently, Bechtold, S.E., Jacobs, L.W. [1990. Management Science 36 (11), 1339–1351] proposed a new integer programming formulation requiring significantly smaller number of variables and nonzeros in the A-matrix than the equivalent set covering formulation. However, due to its assumptions, this approach has remained limited to the special cases of the shift scheduling problem. In Aykin, T. [1996. Management Science 42, 591–603], we presented another implicit modeling approach that is applicable to the general problem without any of the limitations of Bechtold and Jacobs (loc. cit.). This approach also requires substantially smaller number of variables and nonzeros in the A-matrix than the equivalent set covering formulation. In this paper, we relax the assumptions of Bechtold and Jacobs (loc. cit.) and present a generalized version of it. The extended formulation of Bechtold and Jacobs, although requiring smaller number of variables, has more constraints, more nonzeros in the A-matrix, and significantly higher density than the formulation of Aykin (loc. cit.). We compare these modeling approaches through solving (optimally) 220 problems involving as many as 32 928 shift variations. Our computational results show that the time needed to locate an optimal shift schedule and the percentage of the problems solved optimally with Aykin's formulation are substantially better than those with the formulation of Bechtold and Jacobs.

One of the critical tasks the manager of a service system faces daily is the effective scheduling of its manpower. In most service systems, demand for services changes during the course of an operating day. In order to develop a shift schedule, demand needs to be forecasted and converted (usually with the help of queuing models) into labor requirements needed to maintain a desired service level during the course of an operating day. Employees are then assigned to various shifts specified by their start times, lengths, number and timing of relief and lunch breaks to meet these requirements. While understaffing will lower total labor cost, it will result in deterioration of the service quality and longer waiting times, and consequently, higher total cost. Overstaffing, on the other hand, will improve the service quality but will result in underutilization and excessive labor costs. Therefore, it is important for a service organization to schedule its manpower in an efficient manner to minimize labor costs while providing the desired service level. The shift scheduling problem involves determining the number of employees to be assigned to various shifts and the timing of their breaks within the limits allowed by legal, union, and company requirements. To improve manpower utilization and lower labor costs, flexibility in shift types, start times, length, number and duration of breaks is provided. Flexibility in scheduling relief and lunch breaks for a given shift is provided with break windows specifying the time intervals within which employees assigned to that shift must start and complete their breaks. Since its introduction by Edie (1954), this problem has attracted considerable attention in the literature. Both heuristic and integer programming based approaches have been proposed. The integer programming based approaches have traditionally been based on the set covering formulation proposed by Dantzig (1954). For nearly four decades, this was the only modeling approach available for the general problem. Although the set covering formulation has been studied extensively, it is not a practical approach to solve this problem optimally. The set covering approach treats every possible shift type, shift start time, and break placement combination as a separate shift and requires a separate integer variable for it. As a result, the size of the integer model increases very rapidly with the number of shift types, shift start times, breaks, and break window sizes, making it impractical to analyze with the available integer programming tools. Recently, two new modeling approaches have been developed by Bechtold and Jacobs (1990), and Aykin (1996). Both studies model break placements implicitly to reduce the size of the integer model. The objective of this study is to comparatively evaluate these two modeling approaches to the general shift scheduling problem in a variety of problem situations. For this purpose, we first relax a number of assumptions made in Bechtold and Jacobs (1990) and present a generalized version of their formulation that was used in the computational experiments reported. The modeling approaches are compared using a set of 220 test problems involving as many as 32 928 shift variations. The problem set considered in this study include, to the best of our knowledge, the largest shift scheduling problems solved optimally in the literature. Our results show that the formulation given in Aykin (1996) requires more variables than the formulation of Bechtold and Jacobs but substantially less than the set covering model. The number of constraints, number of nonzeros and the density of the A-matrix with the approach given in Aykin (1996) are, however, substantially smaller than those for the formulation given in Bechtold and Jacobs, and the set covering model. More importantly, our results show that the time needed to locate an optimal shift schedule and the percentage of the problems solved optimally with Aykin's formulation are substantially better than those with the formulation of Bechtold and Jacobs; while no optimal solution could be found in 32 (14.5%) problems with the formulation of Bechtold and Jacobs, only 2 problems remained unsolved with the formulation of Aykin. The average IP solution time for the problems solved by both modeling approaches was 331.36 seconds with the formulation of Bechtold and Jacobs, and 113.04 seconds (about 66% less) with the formulation of Aykin. The fact that these results were obtained with a problem set including the largest shift scheduling problems solved optimally in the literature using an off-the-shelf integer programming software (LINDO) is very encouraging in terms of the practical applications of implicit formulations in service systems. The remainder of the paper is organized as follows. In Section 2, we introduce the set covering formulation, extend the formulation given in Bechtold and Jacobs into the scheduling environments involving 24-hour continuous operations, multiple relief/lunch breaks, and multiple disjoint break windows, and present the formulation given in Aykin (1996). Computational results obtained with 220 test problems are presented in Section 3. Finally, in Section 4, we summarize our results.