Leung J.Y.-T. (ed.) Handbook of Scheduling. Algorithms, Models, and Performance Analysis

Chapman & Hall/CRC, 2004. — 1157 p.Scheduling is a form of decision-making that plays an important role in many disciplines. It is concerned with the allocation of scarce resources to activities with the objective of optimizing one or more performance measures. Depending on the situation, resources and activities can take on many different forms. Resources may be nurses in a hospital, bus drivers, machines in an assembly plant, CPUs, mechanics in an automobile repair shop, etc. Activities may be operations in a manufacturing process, duties of nurses in a hospital, executions of computer programs, car repairs in an automobile repair shop, and so on. There are also many different performance measures to optimize. One objective may be the minimization of the mean flow time, while another objective may be the minimization of the number of jobs completed after their due dates.
Scheduling has been studied intensively for more than 50 years, by researchers in management, industrial engineering, operations research, and computer science. There is now an astounding body of knowledge in this field. This book is the first handbook on scheduling. It is intended to provide a comprehensive coverage of the most advanced and timely topics in scheduling. A major goal of this project is to bring together researchers in the above disciplines in order to facilitate cross fertilization. The authors and topics chosen cut across all these disciplines.Introduction and Notation
A Tutorial on Complexity
Some Basic Scheduling Algorithms
Classical Scheduling Problems
Elimination Rules for Job-Shop Scheduling Problem: Overview and Extensions
Flexible Hybrid Flowshops
Open Shop Scheduling
Cycle Shop Scheduling
Reducibility among Scheduling Classes
Parallel Scheduling for Early Completion
Minimizing the Maximum Lateness
Approximation Algorithms for Minimizing Average Weighted Completion Time
Minimizing the Number of Tardy Jobs
Branch-and-Bound Algorithms for Total Weighted Tardiness
Scheduling Equal Processing Time Jobs
Online Scheduling
Convex Quadratic Relaxations in Scheduling
Other Scheduling Models
The Master–Slave Scheduling Model
Scheduling in Bluetooth Networks
Fair Sequences
Due Date Quotation Models and Algorithms
Scheduling with Due Date Assignment
Machine Scheduling with Availability Constraints
Scheduling with Discrete Resource Constraints
Scheduling with Resource Constraints — Continuous Resources
Scheduling Parallel Tasks — Algorithms and Complexity
Scheduling Parallel Tasks Approximation Algorithms
Real-Time Scheduling
The Pinwheel: A Real-Time Scheduling Problem
Scheduling Real-Time Tasks: Algorithms and Complexity
Real-Time Synchronization Protocols
A Categorization of Real-Time Multiprocessor Scheduling Problems and Algorithms
Fair Scheduling of Real-Time Tasks on Multiprocessors
Approximation Algorithms for Scheduling Time-Critical Jobs on Multiprocessor Systems
Scheduling Overloaded Real-Time Systems with Competitive/Worst Case Guarantees
Minimizing Total Weighted Error for Imprecise Computation Tasks and Related Problems
Dual Criteria Optimization Problems for Imprecise Computation Tasks
Periodic Reward-Based Scheduling and Its Application to Power-Aware Real-Time Systems
Routing Real-Time Messages on Networks
Stochastic Scheduling and Queueing Networks
Offline Deterministic Scheduling, Stochastic Scheduling, and Online Deterministic Scheduling: A Comparative Overview
Stochastic Scheduling with Earliness and Tardiness Penalties
Developments in Queueing Networks with Tractable Solutions
Scheduling in Secondary Storage Systems
Selfish Routing on the Internet
Applications
Scheduling of Flexible Resources in Professional Service Firms
Novel Metaheuristic Approaches to Nurse Rostering Problems in Belgian Hospitals
University Timetabling
Adapting the GATES Architecture to Scheduling Faculty
Constraint Programming for Scheduling
Batch Production Scheduling in the Process Industries
A Composite Very-Large-Scale Neighborhood Search Algorithm for the Vehicle Routing Problem
Scheduling Problems in the Airline Industry
Bus and Train Driver Scheduling
Sports Scheduling