Principles of Sequencing and Scheduling

Preface xiii Acknowledgments xvii 1 Introduction 1 1.1 Introduction to Sequencing and Scheduling 1 1.2 Scheduling Theory 4 1.3 Philosophy and Coverage of the Book 6 Bibliography 8 2 Single-machine Sequencing 11 2.1 Introduction 11 2.2 Preliminaries 12 2.3 Problems Without Due Dates: Elementary Results 15 2.3.1 Flowtime and Inventory 15 2.3.2 Minimizing Total Flowtime 17 2.3.3 Minimizing Total Weighted Flowtime 20 2.4 Problems with Due Dates: Elementary Results 22 2.4.1 Lateness Criteria 22 2.4.2 Minimizing the Number of Tardy Jobs 25 2.4.3 Minimizing Total Tardiness 26 2.5 Flexibility in the Basic Model 30 2.5.1 Due Dates as Decisions 30 2.5.2 Job Selection Decisions 32 2.6 Summary 34 Exercises 35 Bibliography 37 3 Optimization Methods for the Single-machine Problem 39 3.1 Introduction 39 3.2 Adjacent Pairwise Interchange Methods 41 3.3 A Dynamic Programming Approach 42 3.4 Dominance Properties 48 3.5 A Branch-and-bound Approach 52 3.6 Integer Programming 59 3.6.1 Minimizing the Weighted Number of Tardy Jobs 60 3.6.2 Minimizing Total Tardiness 63 3.7 Summary 65 Exercises 67 Bibliography 68 4 Heuristic Methods for the Single-machine Problem 71 4.1 Introduction 71 4.2 Dispatching and Construction Procedures 72 4.3 Random Sampling 77 4.4 Neighborhood Search Techniques 81 4.5 Tabu Search 85 4.6 Simulated Annealing 87 4.7 Genetic Algorithms 89 4.8 The Evolutionary Solver 91 4.9 Summary 96 Exercises 100 Bibliography 103 5 Earliness and Tardiness Costs 105 5.1 Introduction 105 5.2 Minimizing Deviations from a Common Due Date 107 5.2.1 Four Basic Results 107 5.2.2 Due Dates as Decisions 112 5.3 The Restricted Version 113 5.4 Asymmetric Earliness and Tardiness Costs 116 5.5 Quadratic Costs 118 5.6 Job-dependent Costs 120 5.7 Distinct Due Dates 120 5.8 Summary 124 Exercises 125 Bibliography 126 6 Sequencing for Stochastic Scheduling 129 6.1 Introduction 129 6.2 Basic Stochastic Counterpart Models 130 6.3 The Deterministic Counterpart 137 6.4 Minimizing the Maximum Cost 139 6.5 The Jensen Gap 144 6.6 Stochastic Dominance and Association 145 6.7 Using Analytic Solver Platform 149 6.8 Non-probabilistic Approaches: Fuzzy and Robust Scheduling 154 6.9 Summary 161 Exercises 163 Bibliography 166 7 Safe Scheduling 167 7.1 Introduction 167 7.2 Meeting Service Level Targets 169 7.2.1 Sample-based Analysis 169 7.2.2 The Normal Model 172 7.3 Trading Off Tightness and Tardiness 174 7.3.1 An Objective Function for the Trade-off 174 7.3.2 The Normal Model 175 7.3.3 A Branch-and-bound Solution 178 7.4 The Stochastic E/T Problem 184 7.5 Using the Lognormal Distribution 190 7.6 Setting Release Dates 194 7.7 The Stochastic U-problem: A Service-level Approach 197 7.8 The Stochastic U-problem: An Economic Approach 204 7.9 Summary 208 Exercises 210 Bibliography 213 8 Extensions of the Basic Model 215 8.1 Introduction 215 8.2 Nonsimultaneous Arrivals 216 8.2.1 Minimizing the Makespan 219 8.2.2 Minimizing Maximum Tardiness 221 8.2.3 Other Measures of Performance 223 8.3 Related Jobs 225 8.3.1 Minimizing Maximum Tardiness 226 8.3.2 Minimizing Total Flowtime with Strings 226 8.3.3 Minimizing Total Flowtime with Parallel Chains 229 8.4 Sequence-Dependent Setup Times 232 8.4.1 Dynamic Programming Solutions 234 8.4.2 Branch-And-Bound Solutions 235 8.4.3 Heuristic Solutions 240 8.5 Stochastic Traveling Salesperson Models 242 8.6 Summary 247 Exercises 248 Bibliography 251 9 Parallel-machine Models 255 9.1 Introduction 255 9.2 Minimizing the Makespan 255 9.2.1 Nonpreemptable Jobs 257 9.2.2 Nonpreemptable Related Jobs 263 9.2.3 Preemptable Jobs 267 9.3 Minimizing Total Flowtime 268 9.4 Stochastic Models 274 9.4.1 The Makespan Problem with Exponential Processing Times 274 9.4.2 Safe Scheduling with Parallel Machines 276 9.5 Summary 277 Exercises 279 Bibliography 280 10 Flow Shop Scheduling 283 10.1 Introduction 283 10.2 Permutation Schedules 286 10.3 The Two-machine Problem 288 10.3.1 Johnson's Rule 288 10.3.2 A Proof of Johnson's Rule 290 10.3.3 The Model with Time Lags 293 10.3.4 The Model with Setups 294 10.4 Special Cases of the Three-machine Problem 294 10.5 Minimizing the Makespan 296 10.5.1 Branch-and-Bound Solutions 297 10.5.2 Integer Programming Solutions 300 10.5.3 Heuristic Solutions 306 10.6 Variations of the m-Machine Model 308 10.6.1 Ordered Flow Shops 308 10.6.2 Flow Shops with Blocking 309 10.6.3 No-Wait Flow Shops 310 10.7 Summary 313 Exercises 313 Bibliography 315 11 Stochastic Flow Shop Scheduling 319 11.1 Introduction 319 11.2 Stochastic Counterpart Models 320 11.3 Safe Scheduling Models with Stochastic Independence 327 11.4 Flow Shops with Linear Association 330 11.5 Empirical Observations 331 11.6 Summary 336 Exercises 337 Bibliography 339 12 Lot Streaming Procedures for the Flow Shop 341 12.1 Introduction 341 12.2 The Basic Two-machine Model 342 12.2.1 Preliminaries 342 12.2.2 The Continuous Version 345 12.2.3 The Discrete Version 348 12.2.4 Models with Setups 350 12.3 The Three-machine Model with Consistent Sublots 352 12.3.1 The Continuous Version 352 12.3.2 The Discrete Version 355 12.4 The Three-machine Model with Variable Sublots 355 12.4.1 Item and Batch Availability 355 12.4.2 The Continuous Version 357 12.4.3 The Discrete Version 359 12.4.4 Computational Experiments 360 12.5 The Fundamental Partition 363 12.5.1 Defining the Fundamental Partition 364 12.5.2 A Heuristic Procedure for s Sublots 367 12.6 Summary 367 Exercises 369 Bibliography 371 13 Scheduling Groups of Jobs 373 13.1 Introduction 373 13.2 Scheduling Job Families 374 13.2.1 Minimizing Total Weighted Flowtime 375 13.2.2 Minimizing Maximum Lateness 377 13.2.3 Minimizing Makespan in the Two-Machine Flow Shop 379 13.3 Scheduling with Batch Availability 383 13.4 Scheduling with a Batch Processor 387 13.4.1 Minimizing the Makespan with Dynamic Arrivals 387 13.4.2 Minimizing Makespan in the Two-Machine Flow Shop 389 13.4.3 Minimizing Total Flowtime with Dynamic Arrivals 390 13.4.4 Batch-Dependent Processing Times 392 13.5 Summary 394 Exercises 395 Bibliography 397 14 The Job Shop Problem 399 14.1 Introduction 399 14.2 Types of Schedules 402 14.3 Schedule Generation 407 14.4 The Shifting Bottleneck Procedure 412 14.4.1 Bottleneck Machines 412 14.4.2 Heuristic and Optimal Solutions 414 14.5 Neighborhood Search Heuristics 417 14.6 Summary 421 Exercises 422 Bibliography 424 15 Simulation Models for the Dynamic Job Shop 427 15.1 Introduction 427 15.2 Model Elements 428 15.3 Types of Dispatching Rules 430 15.4 Reducing Mean Flowtime 432 15.5 Meeting Due Dates 436 15.5.1 Background 436 15.5.2 Some Clarifying Experiments 441 15.5.3 Experimental Results 443 15.6 Summary 449 Bibliography 451 16 Network Methods for Project Scheduling 453 16.1 Introduction 453 16.2 Logical Constraints And Network Construction 454 16.3 Temporal Analysis of Networks 458 16.4 The Time/Cost Trade-off 463 16.5 Traditional Probabilistic Network Analysis 467 16.5.1 The PERT Method 467 16.5.2 Theoretical Limitations of PERT 472 16.6 Summary 476 Exercises 478 Bibliography 481 17 Resource-Constrained Project Scheduling 483 17.1 Introduction 483 17.2 Extending the Job Shop Model 484 17.3 Extending the Project Model 490 17.4 Heuristic Construction and Search Algorithms 493 17.4.1 Construction Heuristics 493 17.4.2 Neighborhood Search Improvement Schemes 496 17.4.3 Selecting Priority Lists 499 17.5 Stochastic Sequencing with Limited Resources 501 17.6 Summary 503 Exercises 505 Bibliography 508 18 Project Analytics 511 18.1 Introduction 511 18.2 Basic Partitioning 513 18.3 Correcting for Rounding 515 18.4 Accounting for the Parkinson Effect 516 18.5 Identifying Mixtures 521 18.6 Addressing Subjective Estimation Bias 524 18.7 Linear Association 526 18.7.1 Systemic Bias 526 18.7.2 Cross-Validation 530 18.7.3 Using Nonparametric Bootstrap Sampling 531 18.8 Summary 534 Bibliography 536 19 PERT 21: Analytics-Based Safe Project Scheduling 537 19.1 Introduction 537 19.2 Stochastic Balance Principles for Activity Networks 539 19.2.1 The Assembly Coordination Model 540 19.2.2 Balancing a General Project Network 547 19.2.3 Additional Examples 550 19.3 Hierarchical Balancing and Progress Payments 557 19.4 Crashing Stochastic Activities 560 19.5 Summary 565 Exercises 567 Bibliography 569 Appendix A: Practical Processing Time Distributions 571 Appendix B: The Critical Ratio Rule 597 Index 613

Este título pertence ao(s) assunto(s) indicados(s). Para ver outros títulos clique no assunto desejado.

• Gestão da produção e do controlo de qualidade