This comprehensive text explores the mathematical models underlying the theory of scheduling. Organized according to scheduling problem type, it examines three solution techniques: algebraic, probabilistic, and Monte Carlo simulation by computer. Topics include problems of sequence, measures for schedule evaluation, finite sequencing for a single machine, and further problems with one operation per job. Additional chapters cover flow-shop scheduling, the general n/m job-shop problem, general network problems related to scheduling, selection disciplines in a single-server queuing system, single-server queuing systems with setup classes, multiple-server queuing models, and experimental investigation of the continuous job-shop process. 1967 edition.
Chapter 1 Problems of Sequence 1-1 "Questions of "pure" sequence" 1-2 The job-shop process 1-3 A classification of scheduling probems Chapter 2 Measures for Schedule Evaluation 2-1 Variables that define a scheduling problem 2-2 Variables that describe the solution to a scheduling problem 2-3 Performance measures for the shop 2-4 The relationship between flow-time and inventory 2-5 Costs associated with scheudling decisions Chapter 3 Finite Sequencing for a Single Machine 3-1 Permutation schedules 3-2 Sequencing according to processing-time 3-3 Sequencing according to due date 3-4 Random sequencing 3-5 Properties of antithetical rules 3-6 SPT sequencing with incomplete information 3-7 Sequencing against weighted measures of performance 3-8 Sequencing with multiple classes Chapter 4 Further Problems with One Operation per Job 4-1 Sequence-dependent setup-times 4-1.1 "A "branch-and-bound" algorithm for the traveling-salesman problem" 4-1.2 Solution of the traveling-salesman problem by dynamic programming 4-1.3 "The "closest-unvisited-city" algorithm for the traveling-salesman problem" 4-2 Intermittent job arrivals 4-3 Required precedence among jobs 4-3.1 Required strings of jobs 4-3.2 General precedence constraints 4-4 Parallel machines Chapter 5 Flow-Shop Scheduling 5-1 Permutation schedules 5-2 Minimizing maximum flow-time in a two-machine flow-shop 5-3 Minimizing mean flow-time in a two-machine flow-shop 5-4 The three-machine flow shop 5-5 Sequencing in large flow-shops Chapter 6 The General n/m Job-Shop Problem 6-1 A graphical description of the problem 6-2 The two-machine job-shop problem 6-3 The two-job job-shop problem 6-4 Integer programming formulation of the job-shop problem 6-5 Types of schedules 6-6 Generation of schedules 6-7 Branch-and-bound approach to the job-shop problem 6-8 Examples of schedule generation 6-9 Probabilistic dispatching 6-10 Heuristic procedures Chapter 7 General Network Problems Related to Scheduling 7-1 Critical route analysis 7-2 Shortest route determination 7-3 Assembly-line balancing problems Chapter 8 Selection Disciplines in a Single-Server Queuing System 8-1 Queues with Poisson arrivals 8-2 System states 8-3 The busy period of a queue with Poisson arrivals 8-4 "The distribution of flow-time under the first-come, first-served discipline" 8-5 Selection disciplines that are independent of processing-times 8-5.1 Distribution of number of jobs in the system 8-5.2 "The last-come, first-served discipline" 8-5.3 The random rule 8-6 Nonpreemptive priority and shortest-processing-time disciplines 8-6.1 Nonpreemptive priority disciplines 8-6.2 The shortest-processing-time discipline 8-6.3 Multiple-level nonpreemptive-priority disciplines 8-7 Preemptive priortity disciplines 8-7.1 Preemptive-resume and preemptive-repeat disciplines 8-7.2 Semi-preemptive priority and shortest-remaining-processing-time disciplines 8-8 The due-date rule and related disciplines 8-9 The effect of processing-time-dependent disciplines on flow-time 8-10 Historical notes Chapter 9 Single-Server Queuing Systems with Setup Classes 9-1 Preemptive-resume priorities with preemptive-repeat setup-times for each job 9-2 Alternating priority discipline without setup-time 9-3 "First-come, first-served with setup classes" 9-4 Alternating priority disciplines with setup-time Chapter 10 Multiple-Server Queuing Models 10-1 State-dependent completion rates; multiple-channel queues 10-2 The output of a Poisson-exponential queuing system 10-3 Queues in series 10-4 General queue networks Chapter 11 Experimental Investigation of the Continuous Job-Shop Process 11-1 Experimental conditions and procedures 11-2 The reduction of mean queue length and work-in-process inventory 11-2.1 Truncation of the shortest-processing-time rule 11-2.2 SPT sequencing with multiple classes 11-2.3 SPT sequencing with incomplete information 11-3 Sequencing against due-dates 11-3.1 Assignment of due-dates 11-3.2 A state-dependent due-date procedure 11-4 Investigations of more complex job-shop models 11-4.1 Flexibility in machine selection 11-4.2 Flexibility in operation sequence 11-4.3 Sequencing in an assembly shop Bibliography Appendix A The Laplace-Stieltjes Transform of a Distribution Function Appendix B Experimental Results: n/m Job-Shop Problem B-1 Mean flow-time B-2 Maximum flow-time B-3 Mean machine finish-time Appendix C Experimental Results: Continuous-Process Job-Shop Problem C-1 Notation used in priority rules C-2 Definition of priority rules for the RAND study C-3 "Experimental investigation of priority assignment in a simple, symmetric, random-routed job-shop of 9 machines" C-4 "Experimental results for a state-dependent due-date procedure in a simple, symmetric, random-routed job-shop of 8 machines" C-5 Flexibility in machine selection in a symmetric random-routed job-shop of 9 machines C-6 Flexibility in operation sequence in a symmetric random-routed job-shop of 9 machines C-7 Sequencing in an assembly shop Index
