Scheduling in Computer and Manufacturing Systems

Inhaltsverzeichnis

• 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.
• 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.
• 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 Other Criteria.
• 4.4.1 Minimizing Maximum Cost.
• 4.4.2 Minimizing Mean Cost.
• 4.5 Minimizing Change-Over Cost.
• 4.5.1 Setup Scheduling.
• 4.5.2 Lot Size Scheduling.
• 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 Flow 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.
• 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.
• 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.
• 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.
• 9 Knowledge-Based Scheduling.
• 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.