Search

Designing shift plans represents a difficult but interesting task because they must satisfy various, often conflicting, requirements. In this article, we address a complex real-world break-scheduling problem for supervisory personnel and present a scheduling system that can help professional planners create high-quality shift plans. Supervisory personnel spend most of their workday in front of computer monitors, addressing critical and constantly changing situations. For employees working under such conditions to always maintain high levels of concentration, it's essential that they take occasional breaks. Usually, the amount of break time, as well as the position and duration of breaks within their work time (shift) are regulated by labor rules that must be satisfied by a feasible shift plan. Moreover, to guarantee effective supervision, a minimum number of employees must be working at any given time.

This chapter deals with the application of evolutionary approaches and other metaheuristic techniques for generating tree decompositions. Tree decomposition is a concept introduced by Robertson and Seymour [1] and it is used to characterize the difficulty of constraint satisfaction and NP-hard problems that can be represented as a graph. Although, in general, no polynomial algorithms have been found for such problems, particular instances can be solved in polynomial time if the treewidth of their corresponding graph is bounded by a constant. The process of solving problems based on tree decomposition comprises two phases. First, a decomposition with small width is generated. Basically in this phase the problem is divided into several subproblems, each included in one of the nodes of the tree decomposition. The second phase includes solving a problem (based on the generated tree decomposition) with a particular algorithm such as dynamic programming. The main idea is that by decomposing a problem into subproblems of limited size, the whole problem can be solved more efficiently. The time for solving the problem based on its tree decomposition usually depends on the width of the tree decomposition. Thus, it is of high interest to generate tree decompositions having small widths.

We present TEMPLE, a domain specific language for modeling and solving staff scheduling problems. TEMPLE provides a set of intuitive abstractions and notations allowing to formulate the constraints of a particular problem in a very compact and natural way. After modeling a staff scheduling problem in TEMPLE, three generic local search algorithms can immediately be applied to the corresponding optimization problem. We show how real-life staff scheduling problems can be both effectively modeled as well as efficiently solved using our approach. Finally, we report on a practical application of TEMPLE in a commercial staff scheduling software.

Many practical problems in mathematics and computer science may be formulated as Constraint Satisfaction Problems (CSPs). Although CSPs are NP-hard in general, it has been proven that instances of CSPs may be solved efficiently, if they have generalised hypertree decompositions of small width. Unfortunately, finding a generalised hypertree decomposition of minimum width is an NP-hard problem. Based on a Genetic Algorithm (GA) for tree decompositions we propose two extensions searching for small-width generalised hypertree decompositions. We carry out comprehensive experiments to obtain suitable operators and parameter settings and apply each GA to numerous benchmark examples for tree and generalised hypertree decompositions. Compared to the best solutions known from literature our GAs were able to return results of equal quality for many benchmark instances and even for some benchmarks improved solutions were obtained. [Received 6 February 2007; Revised 21 May 2007; Accepted 22 May 2007]

The problem of designing workforce shifts and break patterns is a relevant employee scheduling problem that arises in many contexts, especially in service industries. The issue is to find a minimum number of shifts, the number of workers assigned to them, and a suitable number of breaks so that the deviation from predetermined workforce requirements is minimized. We tackle this problem by means of a hybrid strategy in the spirit of Large Neighborhood Search, which exploits a set of Local Search operators that resort to a Constraint Programming model for assigning breaks. We test this strategy on a set of random and real life instances employed in the literature.

Shift design and break scheduling are important employee scheduling problems that arise in many contexts, especially at airports, call centers, and service industries. The aim is to find a minimum number of legal shifts, the number of workers assigned to them, and a suitable number of breaks so that the deviation from predetermined workforce requirements is minimized. Such problems have been extensively investigated in Operations Research and recently have been also tackled with Artificial Intelligence techniques. In this chapter we outline major characteristics of these problems and provide a literature survey over solution techniques to solve them. We then describe in detail two state-of-the-art approaches based on local search techniques. Finally, we discuss our experiences with the application of one of these techniques in a real life case study.