An Implicit Tour Scheduling Model with Applications in Healthcare

Motivated by difficult staff scheduling problems arising in healthcare institutions, we have developed an implicit tour scheduling model which includes full and part-time tour types as well as intra-tour start time flexibility. Potential benefits of intra-tour start time flexibility are demonstrated through a computational experiment. The model has been embedded in a decision support system at a large tertiary care hospital and has been used in numerous studies to help estimate staffing needs and to analyze the impact of scheduling policies and practices.     

Using Benders Decomposition to Implicitly Model Tour Scheduling

This paper introduces a new integrated model for the combined days-off and shift scheduling problem (the tour scheduling problem). This model generalizes the forward and backward constraints, previously introduced by Bechtold and Jacobs for the shift scheduling problem, to the tour scheduling problem. This results in a general and compact formulation that can handle several types of scheduling flexibility. We also provide a new proof of the correctness of forward and backward constraints based on Benders decomposition. The latter approach is interesting in itself because it can be used to solve the problem when extraordinary overlap of break windows or start-time bands is present. A discussion of model size for a set of hypothetical test problems is presented to show the merits of the new formulation.     

A (0–1) goal programming model for scheduling the tour of a marketing executive

This paper addresses the problem of scheduling the tour of a marketing executive (ME) of a large electronics manufacturing company in India. In this problem, the ME has to visit a number of customers in a given planning period. The scheduling problem taken up in this study is different from the various personnel scheduling problems addressed in the literature. This type of personnel scheduling problem can be observed in many other situations such as periodical visits of inspection officers, tour of politicians during election campaigns, tour of mobile courts, schedule of mobile stalls in various areas, etc. In this paper the tour scheduling problem of the ME is modeled using (0–1) goal programming (GP). The (0–1) GP model for the data provided by the company for 1 month has 802 constraints and 1167 binary variables. The model is solved using LINDO software package. The model takes less than a minute (on a 1.50 MHz Pentium machine with 128 MB RAM) to get a solution of the non-preemptive version and about 6 days for the preemptive version. The main contribution is in problem definition and development of the mathematical model for scheduling the tour.     

A Comparative Study of Multiple-Objective Metaheuristics on the Bi-Objective Set Covering Problem and the Pareto Memetic Algorithm

Many organizations face employee scheduling problems under conditions of variable demand for service over the course of an operating day and across a planning horizon. These organizations are concerned with the tour scheduling problem that involves assigning shifts and break times to the work days of employees and allocating days off to individual work schedules. Nowadays, organizations try to adopt various scheduling flexibility alternatives to meet the fluctuating service demand. On the other hand, they have also realized that providing employee productivity and satisfaction is as much important as meeting the service demand. Up to date, tour scheduling solution approaches have neglected considering employee preferences and tried to develop work schedules for employees in a subsequent step. This paper presents a goal programming model that implicitly represents scheduling flexibility and also incorporates information about the preferred working patterns of employees. After solving the proposed model, a work schedule will be generated for each employee without requiring a further step for the assignment of shifts, break times, and work days to employees. The model is capable of handling multiple scheduling objectives, and it can produce optimal solutions in very short computing times.     

An enhanced decomposition algorithm for multistage stochastic hydroelectric scheduling

Handling uncertainty in natural inflow is an important part of a hydroelectric scheduling model. In a stochastic programming formulation, natural inflow may be modeled as a random vector with known distribution, but the size of the resulting mathematical program can be formidable. Decomposition-based algorithms take advantage of special structure and provide an attractive approach to such problems. We develop an enhanced Benders decomposition algorithm for solving multistage stochastic linear programs. The enhancements include warm start basis selection, preliminary cut generation, the multicut procedure, and decision tree traversing strategies. Computational results are presented for a collection of stochastic hydroelectric scheduling problems.     

A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows

This paper presents a novel three-phase heuristic/algorithmic approach for the multi-depot routing problem with time windows and heterogeneous vehicles. It has been derived from embedding a heuristic-based clustering algorithm within a VRPTW optimization framework. To this purpose, a rigorous MILP mathematical model for the VRPTW problem is first introduced. Likewise other optimization approaches, the new formulation can efficiently solve case studies involving at most 25 nodes to optimality. To overcome this limitation, a preprocessing stage clustering nodes together is initially performed to yield a more compact cluster-based MILP problem formulation. In this way, a hierarchical hybrid procedure involving one heuristic and two algorithmic phases was developed. Phase I aims to identifying a set of cost-effective feasible clusters while Phase II assigns clusters to vehicles and sequences them on each tour by using the cluster-based MILP formulation. Ordering nodes within clusters and scheduling vehicle arrival times at customer locations for each tour through solving a small MILP model is finally performed at Phase III. Numerous benchmark problems featuring different sizes, clustered/random customer locations and time window distributions have been solved at acceptable CPU times.     

A Hybrid Approach to Scheduling with Earliness and Tardiness Costs

A hybrid technique using constraint programming and linear programming is applied to the problem of scheduling with earliness and tardiness costs. The linear model maintains a set of relaxed optimal start times which are used to guide the constraint programming search heuristic. In addition, the constraint programming problem model employs the strong constraint propagation techniques responsible for many of the advances in constraint programming for scheduling in the past few years. Empirical results validate our approach and show, in particular, that creating and solving a subproblem containing only the activities with direct impact on the cost function and then using this solution in the main search, significantly increases the number of problems that can be solved to optimality while significantly decreasing the search time.     

Constraint-Based Job Shop Scheduling with IILOG SCHEDULER

We introduce constraint-based scheduling and discuss its main principles. An approximation algorithm based on tree search is developed for the job shop scheduling problem using ILOG SCHEDULER. A new way of calculating lower bounds on the makespan of the job shop scheduling problem is presented and we show how such results can be used within a constraint-based approach. An empirical performance analysis shows that the algorithm we developed performs well. Finally, taking the job shop scheduling problem as a start point, we discuss how constraint-based scheduling can be used to solve more general scheduling problems.     

A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags

The paper presents an exact procedure for a general resource-constrained project scheduling problem where multiple modes are available for the performance of the individual activities and minimum as well as maximum time lags between the different activities may be given. The objective is to determine a mode and a start time for each activity such that all constraints are observed and the project duration is minimized. Project scheduling problems of this type occur, e.g. in process industries. The solution method is a depth-first search based branch-and-bound procedure. It makes use of a branching strategy where the branching rule is selected dynamically. The solution approach is an integration approach where the modes and start times are determined simultaneously. Within an experimental performance analysis this procedure is compared with existing solution procedures.     

A Simulated Annealing Approach to the Solution of Flexible Labour Scheduling Problems

This paper presents a new solution approach to the discontinuous labour tour scheduling problem where the objective is to minimize the number of full-time employees required to satisfy forecast demand. Previous heuristic approaches have often limited the number of allowable tours by restricting labour scheduling flexibility in terms of shift length, shift start-times, days-off, meal-break placement, and other factors. These restrictions were essential to the tractability of the heuristic approaches but often resulted in solutions that contained a substantial amount of excess labour. In this study, we relaxed many of the restrictions on scheduling flexibility assumed in previous studies. The resulting problem environment contained more than two billion allowable tours, precluding the use of previous heuristic methods. Consequently, we developed a simulated annealing heuristic for solving the problem. An important facet of this new approach is an ‘intelligent’ improvement routine which eliminates the need for long run-times typically associated with simulated annealing algorithms. The simulated annealing framework does not rely on a special problem structure and our implementation rapidly converged to near-optimal solutions for all problems in the test environment.