Analyzing constraints influence in the design of rotating crew schedules

ESCO 2016. 5th European Seminar on Computing (Pilsen, Czech Republic, June 5-10, 2016) Analyzing constraints influence in the design of rotating crew schedules. R. M. Falc´on1([email protected]), E. Barrena2, D. Canca1, G. Laporte3 1University of Seville, 2University of Granada, 3HEC Montreal D D D D D R R E E R R N N N R R E E E E E R R R R R D D N N N N R R R Abstract. The rotating crew scheduling problem can be modeled as an optimization problem in which there are several constraints regarding the shifts of the workers and one commonly used objective function is to balance the number of hours per week for every worker. Often, managers prefer to be presented with an array of solutions from which they can make a selection, and there are constraints which reduce the feasibility space more than others. Our aim is to provide the set of all solutions rather than a unique optimal solution as well as to analyze the effect of the constraints in this solution set. For that aim, we follow an algebraic computational approach that solves both days off and shift assignment problems related to the design of rotating schedules. Specifically, we determine a set of Boolean polynomials whose zeros can be uniquely identified with the set of rotating schedules related to a given workload matrix and with the constraints imposed to them. Introduction. •Shift: Team of employees who work for a specific period of time: Day (D), Evening (E), Night (N), Rest (R). •s: Number of shifts (including Rest). •Schedule: Timetable which shows the distribution of shifts. •Scheduling: Process of creating a schedule by minimizing costs and maximizing employee satisfaction. –It has to be carefully designed in services available 24/7. •Rotating Schedule:n×7 schedule whose (i, j) entry corresponds to the shift or rest period initially assigned to the ith team, the jth day of the first week of work. •Workload matrix:s×7 array whose (i, j) entry determines how many times the ith shift has to be assigned the jth day of the week. W=(wij)=     1111111 1111111 1111111 2222222      Several constraints are necessary to preserve equal opportunities among workers and to prevent health risks [Laporte, 1999, 2004]. C.1) Schedules should contain as many full weekends off as possible. C.2) Weekends off should be well spaced out in the cycle. C.3) A shift change can only occur after at least one day off. C.4) The number of consecutive work days must not exceed 6 days and must not be less than 2. C.5) The number of consecutive rest days must not exceed 6 days and must not be less than 2. C.6) In consecutive days, forward rotations (day, evening, night) are generally preferred to backward rotations (day, night, evening). D D D D D R R E E R R N N N R R E E E E E R R R R R D D N N N N R R R → 1 1 1 1 1 4 4 2 2 4 4 3 3 3 4 4 2 2 2 2 2 4 4 4 4 4 1 1 3 3 3 3 4 4 4 Methods to design rotating schedules: •Manual approach. •Integer programming. •Heuristic procedures. •Network flows. Advantages: •Find the optimal rotating schedule by minimizing costs and maximizing employee satisfaction. Disadvantages: •Do not determine all the possible rotating schedules. •Do not analyze the influence of each kind of constraint on the set of feasible solutions, that is, to deal with the number of rotating schedules which are eliminated or incorporated every time that we add or remove a specific condition. Boolean polynomials related to rotating schedules. •RSW: Set of rotating schedules of sshift works and tteam works, which have W= (wij)as workload matrix. •[s]={1,...,s}: Set of shift works of RSWin forward rotation order. The sth shift correspond to rest periods). •RSW≡Set of t×7 arrays R= (rij) on [s] such that, given i∈[s] and j∈[7], the jth column of Rcontains wij times the symbol i. W=     1111111 1111111 1111111 2222222      →R≡ 1 1 1 1 1 4 4 2 2 4 4 3 3 3 4 4 2 2 2 2 2 4 4 4 4 4 1 1 3 3 3 3 4 4 4 It is interesting to impose some of the entries of the rotating schedule. C.2 ⇒Full weekends off well spaced.      W= (wij) E= (eij) →R= (rij)∈RSW,E Variables of the Polynomial Method: xijk =(1,if rij =k, 0,otherwise. i∈[t]j∈[7] k∈[s] Theorem The set RSW,E can be identified with the set of zeros of the following zerodimensional ideal of Q[x111,...,xt7s]. IW,E = h1−xijeij :i∈[t], j ∈[7], eij ∈[s]i+ hxijk :i∈[t], j ∈[7], eij ∈[s], k ∈[s]\ {eij} i + hxijk·1−xijk:i∈[t], j ∈[7], k ∈[s], eij = 0i+ h1−Pk∈[s]xijk :i∈[t], j ∈[7], eij = 0 i+ hxijk :i∈[t], j ∈[7], k ∈[s], wkj = 0 i+ hwkj −Pi∈[t]xijk :j∈[7], k ∈[s], wkj 6= 0 i. Moreover, |RSW,E|= dimQ(Q[x111,...,xt7s]/IW,E) . Implementation of the method in Singular. Examples. [Laporte, 1999] W1=    0011111 0011100 0002222 4420011     W2=    0011111 0011100 0002222 5531122     According to Constraints C.1 and C.2, we impose: E1=    0000000 0000044 0000000 0000000     E2=      0000000 0000044 0000000 0000044 0000000       Constraints |RSW1,E1|r.t. (sec) |RSW2,E2|r.t. (sec) C.3 C.4 C.5 C.6 15,552 0 648,000 0 x3 0 360 97 x36 0 216 8 x15,552 0 145,152 650 x81 0 * * x x 3 1 42 4 x x 3 1 62 14 x x 3 1 360 93 x x 36 1 48 7 x x 9 1 108 27 x x 81 1 * * xxx 3 1 10 3 x x x 3 1 42 6 x x x 3 1 62 15 xxx 9 1 30 8 xxxx 3 1 10 5 Table 1: Distribution of rotating schedules. References. •N. Alon, Combinatorial Nullstellensatz, Recent trends in combinatorics (M´atrah´aza, 1995). Combin. Probab. Comput. 8 (1999) no. 1–2, 7–29. •D. A. Cox, J. B. Little and D. O’Shea, Using Algebraic Geometry, Springer-Verlag, New York, 1998. •W. Decker, G.-M. Greuel, G. Pfister and H. Sch¨onemann, Singular 4-0-2. A computer algebra system for polynomial computations, 2016. http://www.singular.uni-kl.de. •R. M. Falc´on, E. Barrena, D. Canca and G. Laporte, http://personal.us.es/raufalgan/LS/crew.lib. •R. M. Falc´on, E. Barrena, D. Canca and G. Laporte, Counting and enumerating feasible rotating schedules by means of Gr¨obner bases, Math. Comput. Simul. 125 (2016), 139-151. •G. Laporte, The art and science of designing rotating schedules, Journal of the Operational Research Society 50 (1999) no. 10, 1011–1017. •G. Laporte and G. Pesant, A general multi-shift scheduling system, Journal of the Operational Research Society 55 (2004) no. 11, 1208–1217.