Handbook of Scheduling: Algorithms, Models, and Performance Analysis

by Leung; Joseph Y-T.

• ISBN13: 9781584883975
• ISBN10: 1584883979
• Edition: 1st
• Format: Hardcover
• Copyright: 2004-04-27
• Publisher: Chapman & Hall/

Summary

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.

Table of Contents

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