International O.R.
Sobering Thought:
Can IP Solve Liquor Store Scheduling Woes?
In the province of Quebec, where myriad union rules turn a seemingly simple employee scheduling problem into a logistical nightmare that perhaps only an operations researcher can appreciate, the answer is yes.
By Bernard Gendron
The SAQ (in French, Société des alcools du Québec) is a public corporation of the province of Quebec responsible for distributing and selling alcohol-based products in its territory through a large network of more than 400 stores and warehouses. The SAQ operates different types of stores: some stores offer a large selection of products (for instance, those located in densely populated areas), while others have a limited selection (for example, those located near restaurants where customers can bring their own wine). The stores have various hours of operation depending on the day, but also on their type and location. They open between 9:30 a.m. and noon, and close between 5 p.m. and 10 p.m. The warehouses operate overnight.
Every week, the SAQ has to schedule more than 3,000 employees. Until 2002, it handled this process manually, incurring estimated annual salary expenses of almost $1 million (all dollar amounts are in Canadian dollars). Using the manual process, schedulers made many errors because they were unable to produce solutions that respected all the complex rules of the union agreement. The company estimates it paid approximately $300,000 each year to deal with the complaints employees filed. After carefully examining the available computer-based workforce scheduling products, the company realized that none of them could handle its union agreement rules properly.
In March 2000, the SAQ asked me to develop a solution engine that would interact with a Web-based database system developed in-house to produce the schedules the SAQ needed. I chose integer programming (IP) as the methodology of choice and implemented it using a state-of-the-art IP software package (ILOG CPLEX). This choice allowed me to develop a robust program that produces optimal schedules — that is, schedules that strictly adhere to all union agreement rules.
Although it often happens that complex personnel scheduling problems cannot be dealt with using compact IP formulations (most notably in the airline industry), this problem is quite different from many scheduling problems in that it decomposes by employee. The union agreement imposes a sequential assignment: The SAQ must assign the most senior employee the best schedule, then, using the remaining shifts, it must assign the best schedule to the second most senior employee, and so on. This sequential process is guaranteed to produce a feasible schedule, as there are always enough employees on the availability list to fill the requirements of all the stores (thus, there is no need to backtrack on prior schedules). In spite of this interesting feature, formulating the problem for each employee is challenging, as we see next.
Problem Description
The interested reader might consult the forthcoming paper in Interfaces for a full description of the problem and its formulation as an IP model. Here we'll provide a brief idea of the complexity of the problem by its most salient features.
The problem is to generate a weekly schedule per employee, given the following constraints:
- the employee cannot work more than 10 hours per day, and not more than 38 hours over the whole week;
- a week starts on a Sunday and ends on the next Saturday;
- the union agreement specifies that the schedule be generated a day at a time, starting from the end of the week (Saturday) and going backward until Sunday. This rule is called the backward-assignment rule;
- the objective is to maximize the number of hours the employee works on each day, by taking into account the shifts to be assigned and the availabilities the employee expresses.
Thus, the SAQ produces a weekly schedule for each employee by assigning a schedule for each day, starting from the end of the week and going backward to its beginning. The rationale behind the backward-assignment rule is to push the days off towards the beginning of the week (Sunday and Monday) and ideally to grant (the most senior) employees an additional day off (Tuesday). If it did not follow this rule, which maximizes the number of work hours on each day but not over the whole week, the SAQ could produce schedules that contain more work hours over the whole week. I was not allowed to modify this rule, since my solution method had to strictly adhere to all union agreement rules.
Each day is divided into 15-minute periods. I call a set of consecutive time periods an interval and an interval worked entirely by the employee a work interval. The union agreement specifies that each work interval must consist of at least three hours. Although most workers are available only during the daytime to work in stores, some workers also work overnight in warehouses. Typically, an employee working at night should not work during the preceding or following day. The rest rule requires at least eight hours of rest after and before an overnight work interval.
The employee must take a one-hour lunch break at noon, if the work interval entirely contains the interval 10:30 a.m. to 3:30 p.m. This is the lunch-break rule (similar rules apply for dinner, defined by the interval 3:30 p.m. to 8:30 p.m., and for overnight shifts). Since the employee is not paid for this one-hour break, it is not counted as a work hour. This rule is easy to implement on its own, but not when it is coupled to another rule that allows shifts to be split between two employees.
The split-shift rule allows the SAQ to break splitable shifts into two parts: the piece, which is assigned to the employee under consideration, and the residual, which subsequently will be assigned to another employee. Given that each work interval must contain at least three hours, splitable shifts must consist of at least six hours, so that both the piece and the residual have at least three work hours. The split-shift rule was designed to help the SAQ to create schedules that come close to reaching the daily limit on work hours. For example, if an employee has a guaranteed shift from 9 a.m. to 4 p.m. (six work hours), and there is a splitable shift from noon to 7 p.m. (creating a shift of seven work hours), the piece from 4 p.m. to 7 p.m. should be assigned to that employee, leaving nine work hours and a residual from noon to 4 p.m.
The employees and the union appreciate the advantages the split-shift rule provides; it is, however, a nightmare for management. It also makes the scheduling problem very complex to formulate and solve. It is a challenge to accurately model the split-shift rule on its own; combining it with the lunch-break rule creates unpleasant interactions. First, in coupling the two rules, one must manage the residuals to keep track of the work hours. The principle is simple: if the employee is assigned a work interval of p work hours, created by splitting some shifts whose total number of work hours is n, then the residuals should not total more than n-p work hours. This way, the employer pays for no more work hours than required. Although simple in principle, this rule is not so easy to manage in practice; in some cases the scheduler must adjust the residual to satisfy it.
For example, assume it can assign only one shift, from 10:30 a.m. to 8:30 p.m., for a total of eight work hours (lunch and dinner breaks are imposed). The employee being scheduled is available only from 10:30 a.m. to 4 p.m.; by splitting the shift, the scheduler assigns 4.5 work hours to that employee (plus the lunch break). The residual cannot start at 4 p.m., because the resulting shift would contain 4.5 work hours (with no dinner break allowed because the work interval would not contain the interval 3:30 p.m. to 8:30 p.m.). The piece and the residual would then sum up to nine work hours, which would exceed the total of eight work hours for the original splitable shift. We thus have to remove one hour from the residual, creating a new shift from 5 p.m. to 8:30 p.m. Such cases affect the mathematical formulation of the problem, since the model must ensure that residuals always contain at least three hours.
Apart from managing the residuals, the SAQ must manage another complex situation created by the interaction of the split-shift rule and the lunch-break rule. As a simple example, suppose that an employee is available from 10:30 a.m. to 4 p.m., and that the scheduler can assign only one shift, which starts at 10:30 a.m. and ends at 7:30 p.m., to that employee. Normally, it would split the shift at 4 p.m. and assign 4.5 work hours (from 10:30 a.m. to 4 p.m., minus a one-hour lunch break) to the employee. But there is a "better schedule," which consists of splitting the shift at 3:15 p.m. and assigning 4.75 work hours to the employee (10:30 a.m. to 3:15 p.m. with no lunch break because the work hours do not entirely cover the interval 10:30 a.m. to 3:30 p.m.). The model has to forbid this type of split, called an opportunistic split.
Although the objective is to maximize the number of work hours, the model must include a penalty to capture the existence of at least one discontinuity in the schedule (a discontinuity is created when the employee is scheduled for two disjoint work intervals). To discriminate between two equivalent schedules, the SAQ defined seven additional secondary objectives.
Implementation
I programmed a C++ code that interacts with the Web-based database system the SAQ developed to acquire and store data on its employees. The SAQ system creates three data files representing: 1) the shifts each employee can work, 2) each employee's availabilities and preferences, and 3) a list of parameters (daily and weekly limits on the number of work hours, a limit on discontinuities, and so forth), which are fixed and identical for all employees. The third data file helps the SAQ to analyze the impact of changes in the values of the parameters, and to adapt the program when some values change. The C++ code implements the mathematical model using ILOG Concert Technology and then solves the IP formulation with ILOG CPLEX. I calibrated the parameters of CPLEX to optimize performance. I observed one striking example of the effect of fine-tuning CPLEX parameters when the time CPLEX (version 7.1) took to solve a particular instance dropped from 20 minutes to 20 seconds.
The SAQ obtains most schedules very quickly (a few minutes at most). However, for some senior employees working in large subdivisions with many stores, the IP models for the end of the week (Friday and Saturday) can take hours to solve. Usually, the number of splitable shifts is a good indicator of the difficulty of the problems; typically, if one day contains more than 10 splitable shifts, the resulting model will be very hard to solve. In order to produce the schedule on time every week, the SAQ has acquired two CPLEX licenses and has implemented a simple queueing system that ensures that it solves only one of these difficult instances at a time.
Typically, the store managers enter data for the coming week on Wednesday nights, and the SAQ sends schedules to the employees on Thursdays (sometimes, on Friday mornings). Three employees dedicate part of their time to the project. A computer analyst maintains the database and interface system and updates the CPLEX versions. An employee from the human resources department and a representative of the union ensure that schedules respect all rules of the union agreement and answer the store managers' and the employees' questions about the schedules the system produces.
My early developments in the project, which began in March 2000, focused on modeling the splitable shifts. I produced a first release of the C++ code in May 2000. I then discovered several difficulties related to the interaction of split shifts and unpaid breaks; I fixed these problems in the following months. After 13 releases that required multiple bug fixes, I released version 1.0 in December 2000: the format of the data files was very close to the actual existing format, and it implemented most rules. Between December 2000 and July 2001, I produced 11 other releases and then developed version 3.0; it included several rules that were not in the previous versions. After 12 other minor releases, I produced version 4.0 in August 2002; it allows users to stop the execution for an employee after some time and to restart it later using the schedule generated so far for that employee. This feature is used by the queueing system developed by the SAQ to make sure that no single employee becomes a bottleneck to the whole scheduling process. That same month, I released version 5.0, which is compatible with CPLEX version 8.0. The SAQ also implemented the system in all the stores in the province of Quebec during the summer of 2002. Prior to that, the SAQ gradually tested the system on a limited set of stores. The current version is 6.1, released in March 2005.
Impact on the Organization
The project has contributed in many ways to increasing the SAQ's efficiency by reducing its scheduling costs and by improving its management of human resources. By replacing manual scheduling, the automated process saves an estimated $750,000 or more annually (about 80 percent of the total prior salary expenses). In addition, because the program produces accurate schedules that respect all the rules of the union agreement, employees make very few complaints. This reduction in complaints translates into annual savings estimated at about $250,000 — 90 percent of the total prior expenses related to employees' complaints. Overall, the SAQ estimates that the automated scheduling program saves more than $1 million annually. Since developing the new scheduling system cost about $1.3 million, the payback period was less than two years.
In the stores, the system has greatly simplified the work of the managers and union representatives by eliminating paperwork, by simplifying the management of data and by reducing the overall time dedicated to scheduling. In addition, the system interprets the union agreement rules in a uniform way in all stores across the province, which has eliminated many of the complaints from union representatives that they made prior to its implementation.
From its beginning, the project involved all the people concerned: store managers, union representatives and human resources personnel. These three groups have worked together to reach consensus and help the consultants in their quest for successful implementation and results. The project enhanced working relationships all across the organization: between the employees and the managers in the stores, and between the union and the human resources department.
|
|
Bernard Gendron is a professor in the Department of Computer Science and Operations Research at the University of Montreal.
OR/MS Today copyright © 2005 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Rd., Suite 220, Marietta, GA 30060 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com
Web Site © Copyright 2005 by Lionheart Publishing, Inc. All rights reserved.