Theory of Scheduling

by Conway, Richard W.; Maxwell, William L.; Miller, Louis W.

• ISBN13: 9780486428178
• ISBN10: 0486428176
• Edition: Reprint
• Format: Paperback
• Copyright: 2003-06-09
• Publisher: Dover Publications

Summary

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.

Table of Contents

Problems of Sequence	1	(9)
Questions of ``pure'' sequence	2	(2)
The job-shop process	4	(2)
A classification of scheduling problems	6	(3)
Measures for Schedule Evaluation	9	(13)
Variables that define a scheduling problem	9	(2)
Variables that describe the solution to a scheduling problem	11	(3)
Performance measures for the shop	14	(1)
The relationship between flow-time and inventory	15	(5)
Costs associated with scheduling decisions	20	(2)
Finite Sequencing for a Single Machine	22	(31)
Permutation schedules	23	(3)
Sequencing according to processing-time	26	(4)
Sequencing according to due-date	30	(4)
Random sequencing	34	(2)
Properties of antithetical rules	36	(3)
SPT sequencing with incomplete information	39	(4)
Sequencing against weighted measures of performance	43	(6)
Sequencing with multiple classes	49	(4)
Further Problems with One Operation per Job	53	(27)
Sequence-dependent setup-times	53	(14)
A ``branch-and-bound'' algorithm for the traveling-salesman problem	56	(5)
Solution of the traveling-salesman problem by dynamic programming	61	(5)
The ``closest-unvisited-city'' algorithm for the traveling-salesman problem	66	(1)
Intermittent job arrivals	67	(2)
Required precedence among jobs	69	(5)
Required strings of jobs	70	(1)
General precedence constraints	71	(3)
Parallel machines	74	(6)
Flow-Shop Scheduling	80	(23)
Permutation schedules	80	(3)
Minimizing maximum flow-time in a two-machine flow-shop	83	(6)
Minimizing mean flow-time in a two-machine flow-shop	89	(4)
The three-machine flow shop	93	(5)
Sequencing in large flow-shops	98	(5)
The General n/m Job-Shop Problem	103	(29)
A graphical description of the problem	103	(2)
The two-machine job-shop problem	105	(1)
The two-job job-shop problem	106	(1)
Integer programming formulation of the job-shop problem	107	(2)
Types of schedules	109	(3)
Generation of schedules	112	(5)
Branch-and-bound approach to the job-shop problem	117	(2)
Examples of schedule generation	119	(5)
Probabilistic dispatching	124	(5)
Heuristic procedures	129	(3)
General Network Problems Related to Scheduling	132	(9)
Critical route analysis	134	(3)
Shortest route determination	137	(2)
Assembly-line balancing problems	139	(2)
Selection Disciplines in a Single-Server Queuing System	141	(50)
Queues with Poisson arrivals	142	(6)
System states	148	(1)
The busy period of a queue with Poisson arrivals	149	(3)
The distribution of flow-time under the first-come, first-served discipline	152	(3)
Selection disciplines that are independent of processing-times	155	(4)
Distribution of number of jobs in the system	156	(1)
The last-come, first-served discipline	157	(2)
The random rule	159	(1)
Nonpreemptive priority and shortest-processing-time disciplines	159	(9)
Nonpreemptive priority disciplines	160	(6)
The shortest-processing-time discipline	166	(1)
Multiple-level nonpreemptive-priority disciplines	167	(1)
Preemptive priority disciplines	168	(12)
Preemptive-resume and preemptive-repeat disciplines	169	(8)
Semi-preemptive priority and shortest-remaining-processing-time disciplines	177	(3)
The due-date rule and related disciplines	180	(3)
The effect of processing-time-dependent disciplines on flow-time	183	(6)
Historical notes	189	(2)
Single-Server Queuing Systems with Setup Classes	191	(17)
Preemptive-resume priorities with preemptive-repeat setup-times for each job	192	(2)
Alternating priority discipline without setup-time	194	(6)
First-come, first-served with setup classes	200	(1)
Alternating-priority disciplines with setup-times	201	(7)
Multiple-Server Queuing Models	208	(11)
State-dependent completion rates; multiple-channel queues	209	(2)
The output of a Poisson-exponential queuing system	211	(3)
Queues in series	214	(1)
General queue networks	215	(4)
Experimental Investigation of the Continuous Job-Shop Process	219	(30)
Experimental conditions and procedures	220	(1)
The reduction of mean queue length and work-in-process inventory	221	(8)
Truncation of the shortest-processing-time rule	226	(1)
SPT sequencing with multiple classes	227	(1)
SPT sequencing with incomplete information	228	(1)
Sequencing against due-dates	229	(10)
Assignment of due-dates	230	(4)
A state-dependent due-date procedure	234	(5)
Investigations of more complex job-shop models	239	(10)
Flexibility in machine selection	239	(2)
Flexibility in operation sequence	241	(2)
Sequencing in an assembly shop	243	(6)
Bibliography	249	(10)
Appendix A The Laplace-Stieltjes Transform of a Distribution Function	259	(2)
Appendix B Experimental Results: n/m Job-Shop Problem	261	(21)
B--1 Mean flow-time	262	(8)
B--2 Maximum flow-time	270	(8)
B--3 Mean machine finish-time	278	(4)
Appendix C Experimental Results: Continuous-Process Job-Shop Problem	282	(9)
C--1 Notation used in priority rules	282	(1)
C--2 Definition of priority rules for the RAND study	283	(2)
C--3 Experimental investigation of priority assignment in a simple, symmetric, random-routed job-shop of 9 machines	285	(3)
C--4 Experimental results for a state-dependent due-date procedure in a simple, symmetric, random-routed job-shop of 8 machines	288	(1)
C--5 Flexibility in machine selection in a symmetric random-routed job-shop of 9 machines	289	(1)
C--6 Flexibility in operation sequence in a symmetric random-routed job-shop of 9 machines	289	(1)
C--7 Sequencing in an assembly shop	290	(1)
Index	291