调度 原理、算法和系统PDF电子书下载

1 INTRODUCTION 1

1.1 The Role of Scheduling 1

1.2 The Scheduling Function in an Enterprise 4

1.3 Outline of the Book 6

Part 1 Deterministic Models 11

2 DETERMINISTIC MODELS:PRELIMINARIES 13

2.1 Framework and Notation 14

2.2 Examples 20

2.3 Classes of Schedules 21

2.4 Complexity Hierarchy 26

3 SINGLE MACHINE MODELS(DETERMINISTIC） 33

3.1 The Total Weighted Completion Time 34

3.2 The Maximum Lateness 40

3.3 The Number of Tardy Jobs 46

3.4 The Total Tardiness 49

3.5 The Total Weighted Tardiness 53

3.6 Discussion 57

4 MORE ADVANCED SINGLE MACHINE MODELS(DETERMINISTIC） 62

4.1 The Total Tardiness:An Approximation Scheme 63

4.2 The Total Earliness and Tardiness 66

4.3 Primary and Secondary Objectives 74

4.4 Multiple Objectives:A Parametric Analysis 76

4.5 The Makespan with Sequence-Dependent Setup Times 79

4.6 Discussion 88

5 PARALLEL MACHINE MODELS(DETERMINISTIC) 93

5.1 The Makespan without Preemptions 94

5.2 The Makespan with Preemptions 105

5.3 The Total Completion Time without Preemptions 112

5.4 The Total Completion Time with Preemptions 116

5.5 Due Date-Related Objectives 119

5.6 Discussion 121

6 FLOW SHOPS AND FLEXIBLE FLOW SHOPS(DETERMINISTIC) 129

6.1 Flow Shops with Unlimited Intermediate Storage 130

6.2 Flow Shops with Limited Intermediate Storage 142

6.3 Flexible Flow Shops with Unlimited Intermediate Storage 150

7 JOB SHOPS(DETERMINISTIC) 156

7.1 Disjunctive Programming and Branch and Bound 157

7.2 The Shifting Bottleneck Heuristic and the Makespan 167

7.3 The Shifting Bottleneck Heuristic and the Total Weighted Tardiness 174

7.4 Discussion 181

8 OPEN SHOPS(DETERMINISTIC) 186

8.1 The Makespan without Preemptions 187

8.2 The Makespan with Preemptions 191

8.3 The Maximum Lateness without Preemptions 193

8.4 The Maximum Lateness with Preemptions 198

8.5 The Number of Tardy Jobs 203

8.6 Discussion 204

Part 2 Stochastic Models 209

9 STOCHASTIC MODELS:PRELIMINARIES 211

9.1 Framework and Notation 212

9.2 Distributions and Classes of Distributions 212

9.3 Stochastic Dominance 217

9.4 Impact of Randomness on Fixed Schedules 220

9.5 Classes of Policies 223

10 SINGLE MACHINE MODELS(STOCHASTIC) 231

10.1 Arbitrary Distributions without Preemptions 231

10.2 Arbitrary Distributions with Preemptions:The Gittins Index 238

10.3 Likelihood Ratio Ordered Distributions 243

10.4 Exponential Distributions 247

11 SINGLE MACHINE MODELS WITH RELEASE DATES(STOCHASTIC) 258

11.1 Arbitrary Releases and Arbitrary Processing Times 259

11.2 Priority Queues,Work Conservation,and Poisson Releases 261

11.3 Arbitrary Releases and Exponential Processing Times 266

11.4 Poisson Releases and Arbitrary Processing Times 272

11.5 Discussion 278

12 PARALLEL MACHINE MODELS(STOCHASTIC) 283

12.1 The Makespan without Preemptions 284

12.2 The Makespan and Total Completion Time with Preemptions 293

12.3 Due Date-Related Objectives 302

13 FLOW SHOPS,JOB SHOPS,AND OPEN SHOPS(STOCHASTIC) 308

13.1 Stochastic Flow Shops with Unlimited Intermediate Storage 309

13.2 Stochastic Flow Shops with Blocking 316

13.3 Stochastic Job Shops 321

13.4 Stochastic Open Shops 322

Part 3 Scheduling in Practice 333

14 GENERAL PURPOSE PROCEDURES FOR SCHEDULING IN PRACTICE 335

14.1 Dispatching Rules 336

14.2 Composite Dispatching Rules 338

14.3 Filtered Beam Search 342

14.4 Local Search:Simulated Annealing and Tabu-Search 345

14.5 Local Search:Genetic Algorithms 352

14.6 Discussion 353

15 MORE ADVANCED GENERAL PURPOSE PROCEDURES 359

15.1 Decomposition Methods and Rolling Horizon Procedures 360

15.2 Constraint Guided Heuristic Search 364

15.3 Market-Based and Agent-Based Procedures 373

15.4 Procedures for Scheduling Problems with Multiple Objectives 380

15.5 Discussion 386

16 MODELING AND SOLVING SCHEDULING PROBLEMS IN PRACTICE 391

16.1 Scheduling Problems in Practice 392

16.2 Cyclic Scheduling of a Flow Line 396

16.3 Flexible Flow Line with Limited Buffers and Bypass 401

16.4 Flexible Flow Line with Unlimited Buffers and Setups 407

16.5 Bank of Parallel Machines with Release Dates and Due Dates 413

16.6 Discussion 414

17 DESIGN,DEVELOPMENT,AND IMPLEMENTATION OF SCHEDULING SYSTEMS 419

17.1 Systems Architecture 420

17.2 Databases and Knowledge-Bases 421

17.3 Schedule Generation Issues 426

17.4 User Interfaces and Interactive Optimization 429

17.5 Generic Systems Versus Application-Specific Systems 435

17.6 Implementation and Maintenance Issues 438

18 ADVANCED CONCEPTS IN SCHEDULING SYSTEM DESIGN 444

18.1 Robustness and Reactive Scheduling 445

18.2 Machine Learning Mechanisms 450

18.3 Design of Scheduling Engines and Algorithm Libraries 455

18.4 Reconfigurable Systems 459

18.5 Scheduling Systems on the Internet 461

18.6 Discussion 464

19 EXAMPLES OF SYSTEM DESIGNS AND IMPLEMENTATIONS 468

19.1 The SAP-APO System 469

19.2 IBM's Independent Agents Architecture 472

19.3 i2's TradeMatrix Production Scheduler 476

19.4 An Implementation of Cybertec's Cyberplan 483

19.5 Synquest's Virtual Production Engine 488

19.6 The LEKIN System for Research and Teaching 493

19.7 Discussion 500

20 WHAT LIES AHEAD? 502

20.1 Theoretical Research 503

20.2 Applied Research 505

20.3 Systems Development and Integration 507

APPENDIXES 511

A MATHEMATICAL PROGRAMMING:FORMULATIONS AND APPLICATIONS 513

A.1 Linear Programming Formulations 513

A.2 Integer Programming Formulations 518

A.3 Disjunctive Programming Formulations 522

B DETERMINISTIC AND STOCHASTIC DYNAMIC PROGRAMMING 525

B.1 Deterministic Dynamic Programming 525

B.2 Stochastic Dynamic Programming 529

C COMPLEXITY THEORY 533

C.1 Preliminaries 533

C.2 Polynomial Time Solutions Versus NP-Hardness 536

C.3 Examples 539

D COMPLEXITY CLASSIFICATION OF DETERMINISTIC SCHEDULING PROBLEMS 543

E OVERVIEW OF STOCHASTIC SCHEDULING PROBLEMS 547

F SELECTED SCHEDULING SYSTEMS 551

REFERENCES 555

NAME INDEX 577

SUBJECT INDEX 582