Scheduling in Computer and Manufacturing Systems

ISBN-13: 9783642790362 / Angielski / Miękka / 2011 / 312 str.

Jacek Blazewicz; Klaus H. Ecker; G. Nter Schmidt

Opis

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.

Spis treści

1 Introduction.- References.- 2 Preliminaries.- 2.1 Sets and Relations.- 2.2 Problems, Algorithms, Complexity.- 2.2.1 Problems and their Encoding.- 2.2.2 Algorithms.- 2.2.3 Complexity.- 2.3 Graphs and Networks.- 2.3.1 Basic Notions.- 2.3.2 Special Classes of Digraphs.- 2.3.3 Networks.- 2.4 Enumerative Methods.- 2.4.1 Dynamic Programming.- 2.4.2 Branch and Bound.- 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.1.1 Scheduling with Release Times and Deadlines.- 4.1.2 Scheduling with Release Times and Delivery Times.- 4.2 Minimizing Mean Weighted Flow Time.- 4.3 Minimizing Due Date Involving Criteria.- 4.3.1 Maximum Lateness.- 4.3.2 Number of Tardy Tasks.- 4.3.3 Tardiness Problems.- 4.3.4 Earliness and Lateness Problems.- 4.4 Minimizing Change-Over Cost.- 4.4.1 Setup Scheduling.- 4.4.2 Lot Size Scheduling.- 4.5 Other Criteria.- 4.5.1 Minimizing Maximum Cost.- 4.5.2 Minimizing Mean Cost.- References.- 5 Parallel Processor Scheduling.- 5.1 Minimizing Schedule Length.- 5.1.1 Identical Processors.- 5.1.2 Uniform and Unrelated Processors.- 5.2 Minimizing Mean Row Time.- 5.2.1 Identical Processors.- 5.2.2 Uniform and Unrelated Processors.- 5.3 Minimizing Due Date Involving Criteria.- 5.3.1 Identical Processors.- 5.3.2 Uniform and Unrelated Processors.- 5.4 Other Models.- 5.4.1 Semi-Identical Processors.- 5.4.2 Scheduling Multiprocessor Tasks.- References.- 6 Static Shop Scheduling.- 6.1 Flow Shop Scheduling.- 6.2 Open Shop Scheduling.- 6.3 Job Shop Scheduling.- 6.3.1 Basic Ideas.- 6.3.2 Branch and Bound Algorithm.- 6.3.3 Simulated Annealing.- 6.3.4 Computational Results.- References.- 7 Resource Constrained Scheduling.- 7.1 Classical Model.- 7.2 Scheduling Multiprocessor Tasks.- 7.3 Scheduling with Continuous Resources.- 7.3.1 Introductory Remarks.- 7.3.2 Processing Speed vs. Resource Amount Model.- 7.3.3 Processing Time vs. Resource Amount Model.- 7.3.4 Ready Time vs. Resource Amount Model.- References.- 8 Scheduling in Flexible Manufacturing Systems.- 8.1 Introductory Remarks.- 8.2 Scheduling Flexible Flow Shops.- 8.2.1 Problem Formulation.- 8.2.2 Heuristics and their Performance.- 8.2.3 Branch and Bound Algorithm.- 8.3 Scheduling Dynamic Job Shops.- 8.3.1 Introductory Remarks.- 8.3.2 Heuristic Algorithm for the Static Problem.- 8.3.3 Computational Experiments.- 8.4 Simultaneous Scheduling and Routing in some FMS.- 8.4.1 Problem Formulation.- 8.4.2 Vehicle Scheduling for a Fixed Production Schedule.- 8.4.3 Simultaneous Job and Vehicle Scheduling.- References.- 9 From Theory to Practice.- 9.1 Scheduling in Computer Integrated Manufacturing.- 9.2 Solution Approaches Based on Artificial Intelligence.- 9.2.1 Interactive Scheduling.- 9.2.2 Knowledge-Based Systems.- 9.3 Integration of Knowledge and Algorithms.- 9.3.1 Intelligent Production Scheduling.- 9.3.2 Integrated Problem Solving.- References.

O autorze

Dr. Günter Schmidt, Jahrgang 1926, war viele Jahre bis zu seiner Pensionierung im Bereich Medizin der pharmazeutischen Industrie tätig. Er veröffentlichte neben medizinischen Fachbeiträgen und einem Buch über Angina pectoris weitere etwa 550 wissenschaftliche Arbeiten, darunter ca. 170 über Vogelspinnen, mit denen er sich seit 1952 befaßt. 1986 erste Fachveröffentlichung.