Handbook of scheduling : algorithms, models, and performance analysis

Contents Part I: Introduction 1 Introduction and Notation Joseph Y-T. Leung 2 A Tutorial on Complexity Joseph Y-T. Leung 3 Some Basic Scheduling Algorithms Joseph Y-T. Leung Part II: Classical Scheduling Problems 4 Elimination Rules for Job-Shop Scheduling Problem: Overview and Extensions Jacques Carlier, Laurent P´eridy, Eric Pinson, and David Rivreau 5 Flexible Hybrid Flowshops George Vairaktarakis 6 Open Shop Scheduling Teofilo F. Gonzalez 7 Cycle Shop Scheduling Vadim G. Timkovsky 8 Reducibility among Scheduling Classes Vadim G. Timkovsky 9 Parallel Scheduling for Early Completion Bo Chen 10 Minimizing the Maximum Lateness Hans Kellerer 11 Approximation Algorithms for Minimizing AverageWeighted Completion Time Chandra Chekuri and Sanjeev Khanna 12 Minimizing the Number of Tardy Jobs Marjan van den Akker and Han Hoogeveen 13 Branch-and-Bound Algorithms for TotalWeighted Tardiness Antoine Jouglet, Philippe Baptiste, and Jacques Carlier 14 Scheduling Equal Processing Time Jobs Philippe Baptiste and Peter Brucker 15 Online Scheduling Kirk Pruhs, Jiˇr´ı Sgall, and Eric Torng 16 Convex Quadratic Relaxations in Scheduling Jay Sethuraman Part III: Other Scheduling Models 17 The Master–Slave Scheduling Model Sartaj Sahni and George Vairaktarakis 18 Scheduling in Bluetooth Networks Yong Man Kim and Ten H. Lai 19 Fair Sequences Wieslaw Kubiak 20 Due Date Quotation Models and Algorithms Philip Kaminsky and Dorit Hochbaum 21 Scheduling with Due Date Assignment Valery S. Gordon, Jean-Marie Proth, and Vitaly A. Strusevich 22 Machine Scheduling with Availability Constraints Chung-Yee Lee 23 Scheduling with Discrete Resource Constraints J. B
la˙zewicz, N. Brauner, and G. Finke 24 Scheduling with Resource Constraints—Continuous Resources Joanna J´ozefowska and Jan We˛glarz 25 Scheduling Parallel Tasks—Algorithms and Complexity M. Drozdowski 26 Scheduling Parallel Tasks Approximation Algorithms Pierre-Franc‚ ois Dutot, Gr´egory Mouni´e, and Denis Trystram Part IV: Real-Time Scheduling 27 The Pinwheel: A Real-Time Scheduling Problem Deji Chen and Aloysius Mok 28 Scheduling Real-Time Tasks: Algorithms and Complexity Sanjoy Baruah and Jo¨el Goossens 29 Real-Time Synchronization Protocols Lui Sha and Marco Caccamo 30 A Categorization of Real-Time Multiprocessor Scheduling Problems and Algorithms John Carpenter, Shelby Funk, Philip Holman, Anand Srinivasan, James Anderson, and Sanjoy Baruah 31 Fair Scheduling of Real-Time Tasks on Multiprocessors James Anderson, Philip Holman, and Anand Srinivasan 32 Approximation Algorithms for Scheduling Time-Critical Jobs on Multiprocessor Systems Sudarshan K. Dhall 33 Scheduling Overloaded Real-Time Systems with Competitive/Worst Case Guarantees Gilad Koren and Dennis Shasha 34 Minimizing TotalWeighted Error for Imprecise Computation Tasks and Related Problems Joseph Y-T. Leung 35 Dual Criteria Optimization Problems for Imprecise Computation Tasks Kevin I-J. Ho 36 Periodic Reward-Based Scheduling and Its Application to Power-Aware Real-Time Systems Hakan Aydin, Rami Melhem, and Daniel Moss´e 37 Routing Real-Time Messages on Networks G. Young Part V: Stochastic Scheduling and Queueing Networks 38 Offline Deterministic Scheduling, Stochastic Scheduling, and Online Deterministic Scheduling: A Comparative Overview Michael Pinedo 39 Stochastic Scheduling with Earliness and Tardiness Penalties Xiaoqiang Cai and Xian Zhou 40 Developments in Queueing Networks with Tractable Solutions Xiuli Chao 41 Scheduling in Secondary Storage Systems Alexander Thomasian 42 Selfish Routing on the Internet Artur Czumaj Part VI: Applications 43 Scheduling of Flexible Resources in Professional Service Firms Yal¸cin Ak¸cay, Anantaram Balakrishnan, and Susan H. Xu 44 Novel Metaheuristic Approaches to Nurse Rostering Problems in Belgian Hospitals Edmund Kieran Burke, Patrick De Causmaecker and Greet Vanden Berghe 45 University Timetabling Sanja Petrovic and Edmund Burke 46 Adapting the GATES Architecture to Scheduling Faculty R. P. Brazile and K. M. Swigger 47 Constraint Programming for Scheduling John J. Kanet, Sanjay L. Ahire, and Michael F. Gorman 48 Batch Production Scheduling in the Process Industries Karsten Gentner, Klaus Neumann, Christoph Schwindt, and Norbert Trautmann 49 A Composite Very-Large-Scale Neighborhood Search Algorithm for the Vehicle Routing Problem Richa Agarwal, Ravinder K. Ahuja, Gilbert Laporte, and Zuo-Jun “Max” Shen 50 Scheduling Problems in the Airline Industry Xiangtong Qi, Jian Yang and Gang Yu 51 Bus and Train Driver Scheduling Raymond S. K. Kwan 52 Sports Scheduling Kelly Easton, George Nemhauser, and Michael Trick