Klaus H. Ecker - Böcker

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 book provides a theoretical and application oriented analysis of deterministic scheduling problems arising in computer and manufacturing environments. In such systems processors (machines) and possibly other resources are to be allocated among tasks in such a way that certain scheduling objectives are met. Various scheduling problems are discussed where different problem parameters such as task processing times, urgency weights, arrival times, deadlines, precedence constraints, and processor speed factor are involved. Polynomial and exponential time optimization algorithms as well as approximation and heuristic approaches (including tabu search, simulated annealing, genetic algorithms, and ejection chains) are presented and discussed. Moreover, resource-constrained, imprecise computation, flexible flow shop and dynamic job shop scheduling, as well as flexible manufacturing systems, are considered.

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.

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.