Scheduling computer and manufacturing processes.

Authors Jacek Blazewicz, Erwin Pesch, Günter Schmidt, Jan Węglarz, Klaus H. Ecker

Publication date 2 September 2001

branch-and-bound algorithm deterministic scheduling ejection chains flexible flow shop genetic algorithms heuristic intelligent production scheduling manufacturing processes simulated annealing

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Deterministic scheduling theory in operations research (90B35)

Review text

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. A brief outline of the book is the following. In Chapter 2 basic definitions and concepts used throughout the book are introduced. One of the main issues studied here is the complexity analysis of combinatorial problems. Two general approaches dealing with computationally hard problems are briefly discussed: enumerative and heuristic. Then, the authors present the ideas of general local search metaheuristics known under names: simulated annealing, tabu search, and ejection chains as well as genetic algorithms. In Chapter 3 definitions, motivations and classification for deterministic scheduling problems are introduced. The following chapters contain the most important classical results as well as new results, including real-world problems. Chapter 4 deals with single-processor scheduling. The results given here are mainly concerned with polynomial time optimization algorithms. Along with the basic problems some more advanced ones (e.g., lot size scheduling) are considered. Chapter 5 carries on an analysis of scheduling problems where multiple parallel processors (identical, uniform or unrelated) are involved. Since these scheduling problems are more complicated than in Chapter 4, more attention is paid to the presentation of polynomial time heuristic algorithms with guaranteed accuracy, as well as to the description of some enumerative algorithms. Some more advanced models (including semi-identical processors, imprecise computations, lot size scheduling) are also considered. In Chapter 6 the authors discuss the models which take into account multiprocessor tasks, communications delays and divisible tasks. In Chapter 7 flow shop scheduling problems are described. Recent local search heuristics as well as heuristics relying on the two-machine flow shop scheduling problem are considered. Some special flow shops (e.g., permutation and no-wait ones) are introduced. Besides, a few results for the open shop problem are described. In Chapter 8 job shop scheduling problems are investigated. Here the most successful branch and bound ideas are described. The authors also discuss local search methods which are the currently most powerful solution approaches. Moreover, they introduce priority rule based scheduling and describe a well-known opportunistic approach: the shifting bottleneck procedure. Chapter 9 deals with resource constrained scheduling. For the classical model with parallel processors and certain fixed amounts of discrete resources polynomial time optimization algorithms are described. This model is also generalized to cover multiprocessor tasks. Then the authors consider several scheduling problems in which additional resources are continuous. Chapter 10 is devoted to problems of scheduling in flexible manufacturing systems. Here flexible flow shops and dynamic job shops are considered. Besides, the problem of simultaneous assignment of machines and vehicles to jobs is presented. Finally, the authors describe the real world problem of manufacturing of acrylic-glass as a batch scheduling problem under resource constraints. In Chapter 11 results from interactive and knowledge-based scheduling are surveyed and used, together with previous results, for solving practical scheduling problems in the framework of computer integrated manufacturing and object-oriented modeling. This book is the second, revised edition of the original (Berlin, Springer) (1996; Zbl 0911.90201) in which the authors did their best to correct all the errors and to update the References.

Recommendations

Cited in

(70)

This page was built for publication: Scheduling computer and manufacturing processes.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2735585)