1st Edition

Handbook of Scheduling Algorithms, Models, and Performance Analysis

Edited By Joseph Y-T. Leung Copyright 2004
    1212 Pages 262 B/W Illustrations
    by Chapman & Hall

    Researchers in management, industrial engineering, operations, and computer science have intensely studied scheduling for more than 50 years, resulting in an astounding body of knowledge in this field. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, the first handbook on scheduling, provides full coverage of the most recent and advanced topics on the subject. It assembles researchers from all relevant disciplines in order to facilitate cross-fertilization and create new scheduling insights.

    The book comprises six major parts, each of which breaks down into smaller chapters:

    ·         Part I introduces materials and notation, with tutorials on complexity theory and algorithms for the minimization of makespan, total completion time, dual objectives, maximum lateness, the number of late jobs, and total tardiness.

    ·         Part II is devoted to classical scheduling problems.

    ·         Part III explores scheduling models that originate in computer science, operations research, and management science.

    ·         Part IV examines scheduling problems that arise in real-time systems, focusing on meeting hard deadline constraints while maximizing machine utilization.

    ·         Part V discusses stochastic scheduling and queueing networks, highlighting jobs that are not deterministic.

    ·         Part VI covers applications, discussing scheduling problems in airline, process, and transportation industries, as well as in hospitals and educational institutions. 

    Introduction

    Introduction and Notation, Joseph Y-T. Leung

    A Tutorial on Complexity, Joseph Y-T. Leung

    Some Basic Scheduling Algorithms, Joseph Y-T. Leung

    Classical Scheduling Problems


    Elimination Rules for Job-shop Scheduling Problem: Overview and Extensions, Jacques Carlier, Laurent Peridy, Eric Pinson, and David Rivreau

    Flexible Hybrid Flowshops, George Vairaktarakis

    Open Shop Scheduling, Teofilo F. Gonzalez

    Cycle Shop Scheduling, Vadim G. Timkovsky

    Reducibility among Scheduling Classes, Vadim G. Timkovsky

    Parallel Scheduling for Early Completion, Bo Chen

    Minimizing the Maximum Lateness, Hans Kellerer


    Approximation Algorithms for Minimizing Average Weighted Completion Time, Chandra Chekuri and Sanjeev Khanna

    Minimizing the Number of Tardy Jobs, Marjan van den Akker and Han Hoogeveen

    Branch-and-Bound Algorithms for Total Weighted Tardiness, Antoino Jouglet, Philippe Baptiste, and Jacques Carlier

    Scheduling Equal Processing Time Jobs, Philippe Baptiste and Peter Brucker

    Online Scheduling, Kirk Pruhs, Jiri Sgall, and Eric Torng

    Convex Quadratic Relaxations in Scheduling, Jay Sethuraman

    Other Scheduling Models

    The Master/Slave Scheduling Model, Sartaj Sahni and George Vairaktarakis

    Scheduling in Bluetooth Networks, Yong Man Kim and Ten H. Lai

    Fair Sequences, Wieslaw Kubiak

    Due-Date Quotation Models and Algorithms, Philip Kaminsky and Dorit Hochbaum

    Scheduling with Due-Date Assignment, Valery S. Gordon, Jean-Marie Proth, and Vitaly A. Strusevich

    Machine Scheduling with Availability Constraints, Chung-Yee Lee

    Scheduling with Discrete Resource Constraints, J. B_la˙zewicz, N. Brauner, and G. Finke


    Scheduling with Resource Constraints—Continuous Resources, Joanna J´ozefowska and Jan Weglarz

    Scheduling Parallel Tasks—Algorithms and Complexity, M. Drozdowski

    Scheduling Parallel Tasks Approximation Algorithms, Pierre-Franc‚ ois Dutot, Gr´egory Mouni´e, and Denis Trystram


    Real-Time Scheduling

    The Pinwheel: A Real-Time Scheduling Problem, Deji Chen and Aloysivs Mok

    Scheduling Real-Time Tasks: Algorithms and Complexity, Sanjay Baruah and Joa¨el Goossens

    Real Time Synchronization Protocols, Lui Sha and Marco Caccamo

    Fair Scheduling of Real-Time Tasks on Multiprocessors, James Anderson, Philip Holman, and Anand Srinivasan


    A Categorization of Real-Time Multiprocessor Scheduling Problems and Algorithms, John Carpenter, Shelby Funk, Philip Holman, Anand Srinivasan, James Anderson, and Sanjoy Baruah
    Approximation Algorithms for Scheduling Time-Critical Jobs on Multiprocessor System, Sudarshan K. Dhall
    Scheduling Overloaded Real-Time Systems with Competitive/Worst Case Guarantees, Gilad Koren and Dennis Shasha
    Minimizing TotalWeighted Error for Imprecise Computation Tasks and Related Problems, Joseph Y-T. Leung
    Dual Criteria Optimization Problems for Imprecise Computation Tasks, Kevin I-J Ho
    Periodic Reward-Based Scheduling and Its Application to Power-Aware Real-Time Systems, Hakan Aydin, Rami Melhem, and Daniel Mosse

    Routing Real-Time Messages on Networks, G. Young


    Stochastic Scheduling and Queueing Networks
    Offline Deterministic Scheduling, Stochastic Scheduling, and Online Deterministic Scheduling: A Comparative Overview, Michael Pinedo

    Stochastic Scheduling with Earliness and Tardiness Penalties, Xiaoqiang Cai and Xian Zhou


    Developments in Queueing Networks with Tractable Solutions, Xiuli Chao

    Scheduling in Secondary Storage Systems, Alexander Thomasian

    Selfish Routing on the Internet, Artur Czumaj

    Applications


    Scheduling of Flexible Resources in Professional Service Firms, Yalcın Akcay, Anantaram Balakrishnan, and Susan H. Xu
    Novel Metaheuristic Approaches to Nurse Rostering Problems in Belgian Hospitals, Edmund Kieran Burke, Patrick De Causmaecker and Greet Vanden Berghe

    University Timetabling, Sanja Petrovic and Edmund Burke

    Adapting the GATES Architecture to Scheduling Faculty, R. P. Brazile and K. M. Swigger

    Constraint Programming for Scheduling, John J. Kanet, Sanjay L. Ahire, and Michael F. Gorman

    Batch Production Scheduling in the Process Industries, Karsten Gentner, Klaus Neumann, Christoph Schwindt, and Norbert Trautmann


    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

    Scheduling Problems in the Airline Industry, Xiangtong Qi, Jian Yang and Gang Yu

    Bus and Train Driver Scheduling, Raymond S. K. Kwan

    Sports Scheduling, Kelly Easton, George Nemhauser, and Michael Trick

    Index

     

    Biography

    Joseph Y-T. Leung

    “More than 90 well-known authors in this area have made contributions to this handbook … . This handbook is certainly valuable for researchers that want to get an impression on recent research areas and also an overview on existing results. … [T]his handbook presents a huge volume of recent research in different scheduling areas, and certainly will stimulate further developments in many directions … .”
    — Mathematical Reviews, Issue 2005d

    “This is an absolutely excellent, rigorous, mathematical book, something that the scheduling literature has, until now, really lacked…consists of high quality contributions that embrace all the significant and hot topics of the field.”
    Computing Reviews, 2005