调度 原理、算法和系统PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

1 INTRODUCTION1

1.1 The Role of Scheduling1

1.2 The Scheduling Function in an Enterprise4

1.3 Outline of the Book6

Part 1 Deterministic Models11

2 DETERMINISTIC MODELS:PRELIMINARIES13

2.1 Framework and Notation14

2.2 Examples20

2.3 Classes of Schedules21

2.4 Complexity Hierarchy26

3 SINGLE MACHINE MODELS(DETERMINISTIC）33

3.1 The Total Weighted Completion Time34

3.2 The Maximum Lateness40

3.3 The Number of Tardy Jobs46

3.4 The Total Tardiness49

3.5 The Total Weighted Tardiness53

3.6 Discussion57

4 MORE ADVANCED SINGLE MACHINE MODELS(DETERMINISTIC）62

4.1 The Total Tardiness:An Approximation Scheme63

4.2 The Total Earliness and Tardiness66

4.3 Primary and Secondary Objectives74

4.4 Multiple Objectives:A Parametric Analysis76

4.5 The Makespan with Sequence-Dependent Setup Times79

4.6 Discussion88

5 PARALLEL MACHINE MODELS(DETERMINISTIC)93

5.1 The Makespan without Preemptions94

5.2 The Makespan with Preemptions105

5.3 The Total Completion Time without Preemptions112

5.4 The Total Completion Time with Preemptions116

5.5 Due Date-Related Objectives119

5.6 Discussion121

6 FLOW SHOPS AND FLEXIBLE FLOW SHOPS(DETERMINISTIC)129

6.1 Flow Shops with Unlimited Intermediate Storage130

6.2 Flow Shops with Limited Intermediate Storage142

6.3 Flexible Flow Shops with Unlimited Intermediate Storage150

7 JOB SHOPS(DETERMINISTIC)156

7.1 Disjunctive Programming and Branch and Bound157

7.2 The Shifting Bottleneck Heuristic and the Makespan167

7.3 The Shifting Bottleneck Heuristic and the Total Weighted Tardiness174

7.4 Discussion181

8 OPEN SHOPS(DETERMINISTIC)186

8.1 The Makespan without Preemptions187

8.2 The Makespan with Preemptions191

8.3 The Maximum Lateness without Preemptions193

8.4 The Maximum Lateness with Preemptions198

8.5 The Number of Tardy Jobs203

8.6 Discussion204

Part 2 Stochastic Models209

9 STOCHASTIC MODELS:PRELIMINARIES211

9.1 Framework and Notation212

9.2 Distributions and Classes of Distributions212

9.3 Stochastic Dominance217

9.4 Impact of Randomness on Fixed Schedules220

9.5 Classes of Policies223

10 SINGLE MACHINE MODELS(STOCHASTIC)231

10.1 Arbitrary Distributions without Preemptions231

10.2 Arbitrary Distributions with Preemptions:The Gittins Index238

10.3 Likelihood Ratio Ordered Distributions243

10.4 Exponential Distributions247

11 SINGLE MACHINE MODELS WITH RELEASE DATES(STOCHASTIC)258

11.1 Arbitrary Releases and Arbitrary Processing Times259

11.2 Priority Queues,Work Conservation,and Poisson Releases261

11.3 Arbitrary Releases and Exponential Processing Times266

11.4 Poisson Releases and Arbitrary Processing Times272

11.5 Discussion278

12 PARALLEL MACHINE MODELS(STOCHASTIC)283

12.1 The Makespan without Preemptions284

12.2 The Makespan and Total Completion Time with Preemptions293

12.3 Due Date-Related Objectives302

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

13.1 Stochastic Flow Shops with Unlimited Intermediate Storage309

13.2 Stochastic Flow Shops with Blocking316

13.3 Stochastic Job Shops321

13.4 Stochastic Open Shops322

Part 3 Scheduling in Practice333

14 GENERAL PURPOSE PROCEDURES FOR SCHEDULING IN PRACTICE335

14.1 Dispatching Rules336

14.2 Composite Dispatching Rules338

14.3 Filtered Beam Search342

14.4 Local Search:Simulated Annealing and Tabu-Search345

14.5 Local Search:Genetic Algorithms352

14.6 Discussion353

15 MORE ADVANCED GENERAL PURPOSE PROCEDURES359

15.1 Decomposition Methods and Rolling Horizon Procedures360

15.2 Constraint Guided Heuristic Search364

15.3 Market-Based and Agent-Based Procedures373

15.4 Procedures for Scheduling Problems with Multiple Objectives380

15.5 Discussion386

16 MODELING AND SOLVING SCHEDULING PROBLEMS IN PRACTICE391

16.1 Scheduling Problems in Practice392

16.2 Cyclic Scheduling of a Flow Line396

16.3 Flexible Flow Line with Limited Buffers and Bypass401

16.4 Flexible Flow Line with Unlimited Buffers and Setups407

16.5 Bank of Parallel Machines with Release Dates and Due Dates413

16.6 Discussion414

17 DESIGN,DEVELOPMENT,AND IMPLEMENTATION OF SCHEDULING SYSTEMS419

17.1 Systems Architecture420

17.2 Databases and Knowledge-Bases421

17.3 Schedule Generation Issues426

17.4 User Interfaces and Interactive Optimization429

17.5 Generic Systems Versus Application-Specific Systems435

17.6 Implementation and Maintenance Issues438

18 ADVANCED CONCEPTS IN SCHEDULING SYSTEM DESIGN444

18.1 Robustness and Reactive Scheduling445

18.2 Machine Learning Mechanisms450

18.3 Design of Scheduling Engines and Algorithm Libraries455

18.4 Reconfigurable Systems459

18.5 Scheduling Systems on the Internet461

18.6 Discussion464

19 EXAMPLES OF SYSTEM DESIGNS AND IMPLEMENTATIONS468

19.1 The SAP-APO System469

19.2 IBM's Independent Agents Architecture472

19.3 i2's TradeMatrix Production Scheduler476

19.4 An Implementation of Cybertec's Cyberplan483

19.5 Synquest's Virtual Production Engine488

19.6 The LEKIN System for Research and Teaching493

19.7 Discussion500

20 WHAT LIES AHEAD?502

20.1 Theoretical Research503

20.2 Applied Research505

20.3 Systems Development and Integration507

APPENDIXES511

A MATHEMATICAL PROGRAMMING:FORMULATIONS AND APPLICATIONS513

A.1 Linear Programming Formulations513

A.2 Integer Programming Formulations518

A.3 Disjunctive Programming Formulations522

B DETERMINISTIC AND STOCHASTIC DYNAMIC PROGRAMMING525

B.1 Deterministic Dynamic Programming525

B.2 Stochastic Dynamic Programming529

C COMPLEXITY THEORY533

C.1 Preliminaries533

C.2 Polynomial Time Solutions Versus NP-Hardness536

C.3 Examples539

D COMPLEXITY CLASSIFICATION OF DETERMINISTIC SCHEDULING PROBLEMS543

E OVERVIEW OF STOCHASTIC SCHEDULING PROBLEMS547

F SELECTED SCHEDULING SYSTEMS551

REFERENCES555

NAME INDEX577

SUBJECT INDEX582