Theory of Scheduling

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.

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

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Summary

Table of Contents

Supplemental Materials