Theory of Scheduling

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

Overview

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.

Product Details

ISBN-13:	9780486428178
Publisher:	Dover Publications
Publication date:	06/09/2003
Series:	Dover Books on Computer Science
Edition description:	Reprint
Pages:	304
Product dimensions:	6.00(w) x 9.00(h) x (d)

Table of Contents

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