Scheduling in Computer and Manufacturing Systems

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.

1 Introduction.- References.- 2 Preliminaries.- 2.1 Sets and Relations.- 2.2 Problems, Algorithms, Complexity.- 2.3 Graphs and Networks.- 2.4 Enumerative Methods.- 2.5 Heuristic and Approximation Algorithms.- References.- 3 Formulation of Scheduling Problems.- 3.1 Definition of Scheduling Problems.- 3.2 Analysis of Scheduling Problems and Algorithms.- 3.3 Motivations for Deterministic Scheduling Problems.- 3.4 Classification of Deterministic Scheduling Problems.- References.- 4 Single Processor Scheduling.- 4.1 Minimizing Schedule Length.- 4.2 Minimizing Mean Weighted Flow Time.- 4.3 Minimizing Due Date Involving Criteria.- 4.4 Minimizing Change-Over Cost.- 4.5 Other Criteria.- References.- 5 Parallel Processor Scheduling.- 5.1 Minimizing Schedule Length.- 5.2 Minimizing Mean Row Time.- 5.3 Minimizing Due Date Involving Criteria.- 5.4 Other Models.- References.- 6 Static Shop Scheduling.- 6.1 Flow Shop Scheduling.- 6.2 Open Shop Scheduling.- 6.3 Job Shop Scheduling.- References.- 7 Resource Constrained Scheduling.- 7.1 Classical Model.- 7.2 Scheduling Multiprocessor Tasks.- 7.3 Scheduling with Continuous Resources.- References.- 8 Scheduling in Flexible Manufacturing Systems.- 8.1 Introductory Remarks.- 8.2 Scheduling Flexible Flow Shops.- 8.3 Scheduling Dynamic Job Shops.- 8.4 Simultaneous Scheduling and Routing in some FMS.- References.- 9 From Theory to Practice.- 9.1 Scheduling in Computer Integrated Manufacturing.- 9.2 Solution Approaches Based on Artificial Intelligence.- 9.3 Integration of Knowledge and Algorithms.- References.