BUS606: Operations and Supply Chain Management

Creating a staff duty roster is very challenging and also time consuming. Although there is no polynomial known mathematical algorithm that guarantees an optimal solution in a reasonable computation time, it is still possible to generate duty rosters which are better than those produced by a human planner. Scheduling problems occur mostly when events are competing for the same attention, that is, conflicting constraints. The occurrence of conflicts can be stressful and also detrimental to productivity so it is very vital for managers to focus on prevention of these problems and, when they occur, work on minimizing the impact of the disruption. Two common ways to prevent scheduling conflicts are to review the full schedule during and after making changes and also have one person in charge of the schedule. The first method helps to ensure no new conflicts are generated or conflicts are detected early while the second reduces the risk of mistakes due to many people working on the same schedule. In this section, we discuss the approaches taken by several authors to find a solution to generate an effective schedule.

In Staff scheduling and rostering: a review of applications, methods and models, the authors proposed a review of applications used for staff scheduling and rostering problems. They have presented specific applications areas, models, algorithms, and methods used for solving them. In "A simulated annealing approach to the cyclic staff-scheduling problem," a simulated annealing heuristic for use in a continuously operating scheduling environment is presented. Their research is designed to minimize the number of employees required to satisfy forecast demand. From the results, in terms of solution quality, the simulated annealing based method dominates other heuristics and it also exhibits rapid convergence to a low-cost solution.

One example of an NP-hard combinatorial problem is nurse rostering, and addressing scheduling problems can be done by using constraint programming and linear programming techniques. However, we note that, depending on the scenario, heuristics may also be applied for a feasible solution. For example, in "A hybrid tabu search algorithm for the nurse rostering problem," heuristics were necessary to address the issue of nurse rostering in Belgian hospitals. This approach was necessary due to the overconstrained schedules, the need to reduce the time to generate a schedule, and the fact that the cyclic three-shift schedule could not meet the hospital requirements. The Plane algorithm presented is used to determine which nurse can perform particular duties (according to qualification) and also when there are insufficient staff. The Tabu search method which is a local search method used for mathematical optimization for solving combinatorial optimization problems is used in the Plane algorithm. The two algorithms used by Plane are Tabu search and diversification and Tabu search and greedy shuffling. These algorithms are aimed at providing reliable solutions in a short time and providing results that are better from the human point of view, respectively. Results show that better qualities of rosters were provided and the users were more satisfied with the results. While addressing the limitations of the cyclic scheduling for nurses in Belgium, authors in "Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem" investigate the benefit of integrating nurse-specific characteristics into the cyclic scheduling approach. They analyze the extent to which the characteristics should be incorporated and this is compared to the cyclical and flexible acyclical scheduling approaches.

Genetic algorithms are search heuristics used to generate useful solutions as well as optimize and search problems. When implementing genetic algorithms for solving scheduling problems, however, there is a challenge handling the conflict between constraints and objectives which are prevalent in scheduling tasks. One approach to handling this challenge is to use problem specific knowledge, and in "The impact of incorporating nurse-specific characteristics in a cyclical scheduling approach," genetic algorithms were used to address a nurse scheduling problem in a major UK hospital. In "The impact of incorporating nurse-specific characteristics in a cyclical scheduling approach," the research investigates the effect of three types of problem specific knowledge on the scheduling challenge. The results show that the solution provided is fast, robust, and flexible.

The authors in "A branch-and-price approach for integrating nurse and surgery scheduling" also showed how the column generation technique can easily be extended to integrate both nurse and surgery schedules to provide cost savings and reduce schedule generation times. In "A systematic two phase approach for the nurse rostering problem," the nurse rostering problem was partitioned into subproblems and each was solved sequentially using Integer Mathematical Programming (IMP). IMP is a mathematical optimization program which restricts variables to integers. In addition to local optimization techniques, their approach uses two phases where the first phase determines the workload for each nurse for each day of the week and the second phase allocates the daily shifts. Also, Mixed Integer Programing (MIP) is used in "An improved MIP-based approach for a multi-skill workforce scheduling problem" to assign technicians to tasks requiring multilevel skill requirements by repeatedly applying a flexible matching model. This model selects tasks to be completed then forms groups of technicians assigned to a combination of tasks. The MIP model performs very well in the case of rare skills and is capable of revising technician-task allocations. Furthermore, a mathematical model for staff scheduling in a telecommunications center is proposed in "A goal programming model for staff scheduling at a telecommunications center" to replace the manually generated weekly schedule which was generating inefficient and unfair schedules. A zero-one linear goal programming model with the work patterns mathematically formulated as a set of soft constraints was used. The results show the optimal scheduling cycle and also significant increase in efficiency and staff satisfaction.

In "Increasing stability of crew and aircraft schedules," the authors focus on scheduling crew and aircrafts while considering possible disruption. The goals in this case are to reduce slack between flights and reserve resources more intelligently or efficiently. They research into methods of evaluating robust scheduling approaches for aircraft and crew and develop stability indicators based on delay propagation.

Branch and price methods are used for solving integer linear programming and mixed integer linear programming problems which include many variables. The branch and price methods have been applied to scheduling of train drivers in "Personnel scheduling in a complex logistic system: a railway application case". Their approach looks at minimizing the number of duties and maximizing the schedule for outside disruptions. A duty in this case consists of a sequence of trips carried out on a given day by a train driver. An implicit column generation solution approach is used where a dynamic programming algorithm for the pricing-out of columns forms the basis of the heuristic brand and price algorithm. Also, An exact branch-and-price algorithm for workforce scheduling" uses the brand and price models to solve workforce scheduling problems and propose an integer multicommodity network flow formulation to solve the problem.