Local Search Techniques and Tools for Scheduling Problems

Introduction The Calvin and Hobbes strip reported in the first page is a nutshell description of our work. Similarly to Calvin, we deal with high-quality organization of time. However, our real “homework” is to devise the ETM1 for drawing up the schedules, rather than carrying out the assignments as Calvin will do. For this purpose, we have also our own Hobbes tiger (i.e., a quality measure) that gives us an objective judgment of the schedules we developed. In our work we look inside several ETMs, arising from different domains. Actually, these ETMs in the scientific terminology are the methods to tackle scheduling problems. This thesis mainly deals with a specific class of these methods. Scheduling problems can be defined as the task of associating one or several resources to ac- tivities over a certain time period. These problems are of particular interest both in the research community and in the industrial environment. They commonly arise in business operations, espe- cially in the areas of supply chain management, airline flight crew scheduling, and scheduling for manufacturing and assembling. High-quality solutions to instances of these problems can result in huge financial savings. Moreover, scheduling problems arise also in other organizations, such as schools (and at home, as Calvin suggested), universities or hospitals. In these cases other aspects beside the financial one are more meaningful. For instance, a good school or university timetable improves students’ satisfaction, while a well-done nurse rostering (i.e., the shift assignment in hospitals) is of critical importance for assuring an adequate health-care level to patients. Differently from Calvin, in order to draw up a schedule for these problems we cannot start with pencil and paper. Generally speaking, scheduling problems belong to the class of combinatorial optimization problems. Furthermore, in non-trivial cases these problems are NP -hard and it is extremely unlikely that someone could find an efficient method (i.e., a polynomial algorithm) for solving them exactly. For this reason our solution methods are based on heuristic algorithms that do not assure us to find the “best” solution, but which perform fairly well in practice. The algorithms studied in this thesis belong to the Local Search paradigm described in the following. Local Search methods are based on the simple idea of navigating a solution space by iteratively stepping from one solution to one of its neighbors. The neighborhood of a solution is usually given in an intensional fashion, i.e., in terms of atomic local changes that can be applied upon it. Furthermore, each solution is assigned a quality measure by means of a problem dependent cost function, that is exploited to guide the exploration of the solutions. On this simple setting it is possible to design a wide variety of abstract algorithms or meta- heuristics such as Hill Climbing, Simulated Annealing, or Tabu Search. These techniques are non-exhaustive in the sense that they do not guarantee to find a feasible (or optimal) solution, but they search non-systematically until a specific stop criterion is satisfied. Individual heuristics do not always perform well on all problem instances, even though a com- mon requirement of approximation algorithms is to be robust on a wide variety of instances. To cope with this issue, a possible direction to pursue is the employment of several heuristics on the same problem. This should reduce the bias of a specific heuristic to be applied on a given instance. Furthermore, this idea opens the way to a line of research which attempts to investigate new compound Local Search methods obtained by combination of neighborhoods and basic techniques. 1ETM is the short for “Effective Time Management” (see the first page). We remark that it is absolutely not a scientific term, but a word invented by the cartoonist.