Scheduling Algorithms

by BRUCKER PETER

• ISBN13: 9783540415107
• ISBN10: 3540415106
• eBook ISBN(s): 9783662045503
• Edition: 3rd
• Format: Hardcover
• Copyright: 2001-08-01
• Publisher: SPRINGER VERLAG INC
• More Book Details
• Purchase Benefits

Summary

Besides scheduling problems for single and parallel machines and shop scheduling problems the book covers advanced models involving due-dates, sequence dependent changeover times and batching. Also multiprocessor task scheduling and problems with multipurpose machines are discussed. The method used to solve these problems are linear programming, dynamic programming, branch-and-bound algorithms, and local search heuristics. Complexity results for the different classes of deterministic scheduling problems are updated and summarized. Also the references are updated.

Table of Contents

Preface	v
Classification of Scheduling Problems	1	(10)
Scheduling Problems	1	(1)
Job Data	2	(1)
Job Characteristics	3	(2)
Machine Environment	5	(1)
Optimality Criteria	6	(1)
Examples	7	(4)
Some Problems in Combinatorial Optimization	11	(26)
Linear and Integer Programming	11	(1)
Transshipment Problems	12	(1)
The Maximum Flow Problem	13	(1)
Bipartite Matching Problems	14	(4)
The Assignment Problem	18	(5)
Arc Coloring of Bipartite Graphs	23	(3)
Shortest Path Problems and Dynamic Programming	26	(11)
Computational Complexity	37	(24)
The Classes P and NP	37	(4)
NP-complete and NP-hard Problems	41	(7)
Simple Reductions Between Scheduling Problems	48	(3)
Living with NP-hard Problems	51	(10)
Local Search Techniques	51	(5)
Branch-and-Bound Algorithms	56	(5)
Single Machine Scheduling Problems	61	(46)
Minimax Criteria	62	(5)
Lawler's Algorithm for 1 /prec/ fmax	62	(1)
1/prec;p; = 1;r; / fmax and 1/prec; pmtn;r; / fmax	63	(4)
Maximum Lateness and Related Criteria	67	(6)
Total Weighted Completion Time	73	(12)
1 /tree/ Σ wjCj	73	(7)
1 /sp-graph/ Σ wjCj	80	(5)
Weighted Number of Late Jobs	85	(9)
1 /rj;pj = 1 Σ wjUj	85	(1)
1 / pj = 1 /ΣUj	85	(1)
1 // ΣUj	86	(3)
1/ rj;pmtn Σ wjUj	89	(5)
Total Weighted Tardiness	94	(4)
Problems with Release Times and Identical Processing Times	98	(6)
1 /rj;pj = p /Σ wjUj	98	(4)
1 /rj;pj = p /Σ wjUj and 1 /rj;pj = p /ΣTj	102	(2)
Complexity of Single Machine Problems	104	(3)
Parallel Machines	107	(48)
Independent Jobs	107	(32)
Identical Machines	107	(17)
Uniform Machines	124	(12)
Unrelated Machines	136	(3)
Jobs with Precedence Constraints	139	(11)
P /tree;pi = 1 \Lmax-Problems	139	(6)
Problem P2 \prec;p; = 1\Lmax	145	(5)
Complexity Results	150	(5)
Shop Scheduling Problems	155	(86)
The Disjunctive Graph Model	156	(2)
Open Shop Problems	158	(16)
Arbitrary Processing Times	158	(3)
Unit Processing Times	161	(13)
Flow Shop Problems	174	(5)
Minimizing Makespan	175	(4)
Job Shop Problems	179	(47)
Problems with Two Machines	179	(8)
Problems with Two Jobs. A Geometric Approach	187	(9)
Job Shop Problems with Two Machines	196	(6)
A Branch-and-Bound Algorithm	202	(19)
Applying Tabu-Search to the Job Shop Problem	221	(5)
Mixed Shop Problems	226	(6)
Problems with Two Machines	226	(1)
Problems with Two Jobs	227	(5)
Complexity of Shop Scheduling Problems	232	(9)
Due-Date Scheduling	241	(24)
Problem 1 / dopt / Σ wi / Lσ(i) / + wo. d	242	(3)
Problem 1 / dopt / wE Σei+wT Σ Ti + wod	245	(2)
Problem 1 / d / Σ wi / Lσ(i)/	247	(6)
Problem 1 / d / wE Σ Ei + wT ΣTi	253	(2)
Problem 1 / d / /Li/max and 1 / dopt / / Li/ max	255	(2)
Problem 1 / dopt / &Sigma wi/Li/	257	(3)
Problem 1 / d / Σ wi / Li /	260	(5)
Batching Problems	265	(14)
Single Machine s-Batching Problems	265	(4)
Single Machine p-Batching Problems	269	(6)
The Unbounded Model	270	(5)
The Bounded Model	275	(1)
Complexity Results for Single Machine Batching Problems	275	(4)
Changeover Times and Transportation Times	279	(10)
Single Machine Problems	280	(4)
Problems with Parallel Machines	284	(4)
General Shop Problems	288	(1)
Multi-Purpose Machines	289	(24)
MPM Problems with Identical and Uniform Machines	290	(6)
MPM Problems with Shop Characteristics	296	(15)
Arbitrary Processing Times	296	(11)
Unit Processing Times	307	(4)
Complexity Results	311	(2)
Multiprocessor Tasks	313	(30)
Multiprocessor Task Systems	314	(5)
Shop Problems with MPT: Arbitrary Processing Times	319	(6)
Shop Problems with MPT: Unit Processing Times	325	(6)
Multi-Mode Multiprocessor-Task Scheduling Problems	331	(7)
Complexity Results	338	(5)
Bibliography	343	(18)
Index	361