Klaus H. Ecker

This handbook provides a comprehensive introduction to the theory and applications of scheduling in advanced planning and computer systems. It addresses a broad audience including practitioners and researchers interested in scheduling, as well as graduate and advanced undergraduate students in the fields of computer science and computer engineering, operations research, industrial and real-time engineering, management science, business administration and information systems, and applied mathematics. The book begins by providing an introduction to and basic concepts from discrete mathematics. Single and multiple processor systems are covered, with a focus on multiprocessor tasks and hard real-time systems. Flow shop and open shop scheduling, as well as scheduling in job shops, are explained in detail. Issues like limited processor availability, time-dependence, resource constraints and imprecise computations are dealt with in dedicated chapters. Special attention is given toonline scheduling, constraint programming and disjunctive scheduling. The book also features applications and cases involving flexible manufacturing systems, computer integrated production scheduling and logistics. In particular it presents case studies on optimization procedures for the production of acrylic glass and of helicopter parts in a flexible manufacturing system, an efficient decision support system for airport gate scheduling, concrete delivery planning, and berth and quay crane allocation at seaports.

This handbook is in a sense a continuation of Scheduling Computer and Manu­ facturing Processes [1], two editions of which have received kind acceptance of a wide readership. As the previous volume, it is the result of a long lasting Ger­ man-Polish collaboration. However, due to important reasons, it has a new form. Namely, following the suggestions of the Publisher, we decided to prepare a handbook filling out a gap on the market in the area. The gap concerns a unified approach to the most important scheduling models and methods with the special emphasis put on their relevance to practical situations. Thus, in comparison with [1], the contents has been changed significantly. This concerns not only correc­ tions we have introduced, following the suggestions made by many readers (we are very grateful to all of them) and taking into account our own experience, but first of all this means that important new material has been added. It is character­ ized in Chapter 1, and, generally speaking, covers a transition from theory to ap­ plications in a wide spectrum of scheduling problems, hidependently of this, in all chapters new results have been reported and new illustrative material, includ­ ing real-world problems, has been given. We very much hope that in this way the handbook will be of interest to a much wider readership than the former volume, the fact which has been under­ lined in the title.

Let us start with the description of the purpose of this book. First we should explain how we understand its tide. In general, scheduling problems can be understood very broadly as the problems of the allocation of resources over time to perform a set of tasks. By resources we understand arbitrary means tasks compete for. They can be of a very different nature, e.g. manpower, money, processors (machines), energy, tools. Also tasks can have a variety of interpretations starting from machining parts in manu­ facturing systems up to processing information in computer systems. The same is true for task characteristics, e. g. ready times, due dates, relative urgency weights, functions describing task processing in relation to allotted resources. Moreover, a structure of a set of tasks, reflecting precedence constraints among them, can be defined in different ways. In addition, different criteria which measure the quality of the performance of a set of tasks can be taken into account.

Let us first describe the purpose of this book, starting with the explanation of its title. In general, scheduling problems can be understood very broadly as the problems of allocating resources over time to perform a set of tasks being parts of some processes, among which computational and manufacturing ones are most important. Tasks individually compete for resources which can be of a very different nature, e.g. manpower, money, processors (machines), energy, tools. The same is true for task characteristics, e.g. ready times, due dates, relative ur­ gency weights, functions describing task processing in relation to allotted re­ sources. Moreover, a structure of a set of tasks, reflecting precedence constraints among them, can be defined in different ways. In addition, different criteria which measure the quality of the performance of a set of tasks can be taken into account. It is easy to imagine that scheduling problems understood so generally ap­ pear almost everywhere in real-world situations. Of course, there are many as­ pects concerning approaches for modeling and solving these problems which are of general methodological importance. On the other hand, however, some classes of scheduling problems have their own specificity which should be taken into ac­ count. Since it is rather impossible to treat all these classes with the same atten­ tion in a framework of one book, some constraints must be put on the subject area considered. In the case of this book these constraints are as follows.

Let us first describe the purpose of this book, starting with the explanation of its title. In general, scheduling problems can be understood very broadly as the problems of allocating resources over time to perform a set of tasks being parts of some processes, among which computational and manufacturing ones are most important. Tasks individually compete for resources which can be of a very different nature, e.g. manpower, money, processors (machines), energy, tools. The same is true for task characteristics, e.g. ready times, due dates, relative ur­ gency weights, functions describing task processing in relation to allotted re­ sources. Moreover, a structure of a set of tasks, reflecting precedence constraints among them, can be defined in different ways. In addition, different criteria which measure the quality of the performance of a set of tasks can be taken into account. It is easy to imagine that scheduling problems understood so generally ap­ pear almost everywhere in real-world situations. Of course, there are many as­ pects concerning approaches for modeling and solving these problems which are of general methodological importance. On the other hand, however, some classes of scheduling problems have their own specificity which should be taken into ac­ count. Since it is rather impossible to treat all these classes with the same atten­ tion in a framework of one book, some constraints must be put on the subject area considered. In the case of this book these constraints are as follows.