Handbook of Scheduling:

Algorithms, Models, and Performance Analysis


Edited by Joseph Y-T. Leung

Published by CRC Press, Boca Raton, FL, USA, 2004


Table of Contents

*  —  indicates contacting author


Part I — Introduction

1. Introduction and Notation

J. Leung*   —   *Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102.
*Email:   leung@cis.njit.edu

2. A Tutorial on Complexity

J. Leung*   —   *Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102.
*Email:   leung@cis.njit.edu

3. Some Basic Scheduling Algorithms

J. Leung*   —   *Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102.
*Email:   leung@cis.njit.edu

 

Part II — Classical Scheduling Problems

4. Elimination Rules for Job-shop Scheduling Problem: Overview and Extensions

J. Carlier*, L. Peridy, E. Pinson, and D. Rivreau    —    *Universite de Technologie de Compiegne, BP 60319-60203, Compiegne Cedex, France.
*Email:   carlier@utc.fr

5. Flexible Hybrid Flowshops

G. Vairaktarakis*    —    *Department of Operations, Case Western Reserve University, Cleveland, OH 44106.
*Email:   gxv5@po.cwru.edu

6. Open Shop Scheduling

T. Gonzalez*   —    *Department of Computer Science, University of California, Santa Barbara, CA 93106.
*Email:   teo@cs.ucsb.edu

7. Cycle Shop Scheduling

V. Timkovsky*  —    *CGI Group, Inc., 30 Wellington St. W., Suite 300, Toronto, Ontario, M5L 1G1, and Department of Computing and Software, McMaster University, Hamilton, Ontario, L8S 4L7, Canada.
*Email:   timko@cgi.ca

8. Reducibility Among Scheduling Classes

V. Timkovsky*  —    *CGI Group, Inc., 30 Wellington St. W., Suite 300, Toronto, Ontario, M5L 1G1, and Department of Computing and Software, McMaster University, Hamilton, Ontario, L8S 4L7, Canada.
*Email:   timko@cgi.ca

9. Parallel Scheduling for Early Completion

B. Chen*  —    *Warwick Business School, University of Warwick, Coventry, CV4 7AL, United Kingdom.
*Email:   Bo.Chen@wbs.ac.uk

10. Minimizing the Maximum Lateness

H. Kellerer*  —    *Institut fur Statistik and Operations Research, Universitat Graz, Universitatsstrabe 15, A-8010 Graz, Austria.
*Email:   hans.kellerer@uni-graz.at

11. Approximation Algorithms for Minimizing the Weighted Sum of Completion Times

C. Chekuri* and S. Khanna  —    *Bell Laboratories, 700 Mountain Ave., Room 2C-441, Murray Hill, NJ 07974-0636.
*Email:   chekuri@research.bell-labs.com

12. Minimizing the Number of Tardy Jobs

M. van den Akker and H. Hoogeveen*  —    *Department of Computer Science, Utrecht University, CGN, A312, Padualaan 14, NL-3508 TB Utrecht, The Netherland.
*Email:   slam@cs.uu.nl

13. Branch-and-Bound Algorithms for Total Weighted Tardiness

A. Jouglet, Ph. Baptiste*, and J. Carlier  —    *CNRS, UMR 6599 Heudiasyc, UTC, BP 20529, F-60205, Campiegne, France.
*Email:   Philippe.Baptiste@utc.fr

14. Scheduling Equal Processing Time Jobs

P. Brucker* and Ph. Baptiste  —    *Universitat Osnabruck, FB Mathematik/Informatik, Albrechstr. 28, D-49069 Osnabruck, Germany.
*Email:   peter@mathematik.uni-osnabrueck.de

15. Online Scheduling

K. Pruhs, J. Sgall*, and E. Torng  —    *Mathematical Institute of the Academy of Sciences of the Czech Republic, Zitna 25, 115 67 Praha 1, Czech Republic.
*Email:   sgall@math.cas.cz

16. Convex Relaxations in Scheduling

J. Sethuraman*  —    *Department of Industrial Engineering and Operations Research, Columbia University, New York, NY 10027.
*Email:   jay@fermi.ieor.columbia.edu

 

Part III — Other Scheduling Models

17. The Master/Slave Model

S. Sahni* and G. Vairaktaraki  —    *Department of Computer and Information Science, University of Florida, Gainesville, FL 32611.
*Email:   sahni@cis.ufl.edu

18. Scheduling in Blue-Tooth Networks

Y. M. Kim and S. Lai*  —    *Department of Computer and Information Science, Ohio State University, Columbus, OH 43210.
*Email:   lai@cis.ohio-state.edu

19. Fair Sequences

W. Kubiak*  —    *Faculty of Business Administration, Memorial University of Newfoundland, St. Johns, NF, Canada, A1B 3X5.
*Email:   wkubiak@morgan.ucs.mun.ca

20. Due Date Quotation Models and Algorithms

P. Kaminsky* and D. Hochbaum  —    *Department of Industrial Engineering and Operations Research, University of California, Berkely, CA 94720-1777.
*Email:   kaminsky@ieor.berkeley.edu

21. Scheduling with Due Date Assignment

V. S. Gordon*, J-M Proth, and V. A. Strusevich  —    *Institute of Engineering Cybernetics, National Academy of Sciences of Belarus, 6 Surganov Str., 220012 Minsk, Belarus.
*Email:   gordon@newman.bas-net.by

22. Machine Scheduling with Availability Constraints

C. Y. Lee*  —    *Department of Industrial Engineering and Engineering Management, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong.
*Email:   cylee@ust.hk

23. Scheduling with Discrete Resource Constraints

J. Blazewicz*, N. Brauner, and G. Finke  —    *Institute of Computing Science, Poznan University of Technology, Piotrowo 3a, 60-965 Poznan, Poland.
*Email:   blazewic@sol.put.poznan.pl

24. Scheduling with Resource Constraints— Continuous Resources

J. Jozefowska and J. Weglarz*  —   *Institute of Computing Science, Poznan University of Technology, Piotrowo 3a, 60-965 Poznan, Poland.
*Email:   weglarz@put.poznan.pl

25. Scheduling Parallel Tasks— Algorithms and Complexity

M. Drozdowski*  —   *Institute of Computing Science, Poznan University of Technology, Piotrowo 3a, 60-965 Poznan, Poland.
*Email:   maciej_d@sol.put.poznan.pl

26. Scheduling Parallel Tasks— Approximation Algorithms

P-F Dutot, G. Mounie, and D. Trystram*  —   *Laboratoire Informatique et Distribution, 51, Avenue Jean Kuntzmann, F-38330 Montbonnot St. Martin, France.
*Email:   denis.trystram@imag.fr


Part IV— Real-Time Scheduling

27. The Pinwheel: A Real-Time Scheduling Problem

D. Chen and A. Mok*  —   *Department of Computer Science, University of Texas at Austin, Austin, TX 78712.
*Email:   mok@cs.utexas.edu

28. Scheduling Real-Time Tasks: Algorithms and Complexity

S. Baruah* and J. Goossens  —  *Department of Computer Science, University of North Carolina, Campus Box 3175, Chapel Hill, NC 27599-3175.
*Email:   baruah@cs.unc.edu

29. Real Time Synchronization Protocols

L. Sha* and M. Cacammo  —   *Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801.
*Email:   lrs@cs.uiuc.edu

30. Fair Scheduling of Real-Time Tasks on Multiprocessors

J. Anderson*, P. Holman, and A. Srinivasan  —   *Department of Computer Science, University of North Carolina, Campus Box 3175, Chapel Hill, NC 27599-3175.
*Email:   anderson@cs.unc.edu

31. A Categorization of Real-Time Multiprocessor Scheduling Problems and Algorithms

J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Anderson*, and S. Baruah  —   *Department of Computer Science, University of North Carolina, Campus Box 3175, Chapel Hill, NC 27599-3175.
*Email:   anderson@cs.unc.edu

32. Approximation Algorithms for Scheduling Time-Critical Jobs on Multiprocessor Systems

S. K. Dhall*  —   *School of Computer Science, University of Oklahoma, Norman, OK 73019-6151.
*Email:   sdhall@ou.edu

33. Scheduling Overloaded Real-Time Systems with Competitive/Worst Case Guarantees

G. Koren and D. Shasha*  —   *Department of Computer Science, New York University, New York, NY 10012.
*Email:   shasha@cs.nyu.edu

34. Minimizing Total Weighted Error for Imprecise Computation Tasks and Related Problems

J. Leung*  —   *Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102.
*Email:   leung@cis.njit.edu

35. Dual Criteria Optimization Problems for Imprecise Computation Tasks

K. Ho*  —   *Department of Information Management, Chun Shan Medical University, Taichung, Taiwan, Republic of China.
*Email:   ho@csmu.edu.tw

36. Periodic Reward-Based Scheduling and Its Application to Power-Aware Real-Time Systems

H. Aydin*, R. Melhem, and D. Mosse  —   *Department of Computer Science, 4400 University Drive, MSN 4A5, George Mason University, Fairfax, VA 22030.
*Email:   aydin@cs.gmu.edu

37. Routing Real-Time Messages on Networks

G. Young*  —   *Department of Computer Science, California State Polytechnic University at Pomona, 3801 W. Temple Ave., Pomona, CA 91768.
*Email:   gsyoung@csupomona.edu


Part V— Stochastic Scheduling and Queuing Networks

38. Offline Deterministic Scheduling, Stochastic Scheduling, and Online Deterministic Scheduling: A Comparative Review

M. Pinedo*  —   *Department of Operations Management, Stern School of Business, New York University, New York, NY 10012.
*Email: mpinedo@stern.nyu.edu

39. Stochastic Scheduling with Earliness and Tardiness Penalties

X. Cai* and S. Zhou  —   *Department of Systems Engineering and Engineering Management, Chinese University of Hong Kong, Shatin, NT, Hong Kong.
*Email:   xqcai@se.cuhk.edu.hk

40. Developments in Queueing Networks with Tractable Solutions

X. Chao*  —   *Department of Industrial Engineering, North Carolina State University, Raleigh, NC 27695-7960.
*Email:   xchao@eos.ncsu.edu

41. Scheduling in Secondary Storage Systems

A. Thomasian*  —   *Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102.
*Email:   athomas@cis.njit.edu

42. Selfish Routing on the Internet

A. Czumaj*  —   *Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102.
*Email:   czumaj@cis.njit.edu

 

Part VI— Applications

43. Scheduling of Multi-Classes of Jobs on Flexible Resources

Y. Alcay, A. Balakrishnan, and S. Xu*  —   *Department of Management Science and Information Systems, Pennsylvania State University, University Park, PA 16802.
*Email:   shx@psu.edu

44. Novel Meta-heuristic Approaches to Nurse Rostering Problems in Belgian Hospitals

E. Burke*, P. DeCausmaecker and G. Vanden Berghe  —   *School of Computer Science and Information Technology, University of Nottingham, Wollaton Road, Jubilee Campus, N681BB, Nottingham, Great Britain.
*Email:   ekb@cs.nott.ac.uk

45. University Timetabling

S. Petrovic* and E. Burke  —   *School of Computer Science and Information Technology, University of Nottingham, Wollaton Road, Jubilee Campus, N681BB, Nottingham, Great Britain.
*Email:   sxp@cs.nott.ac.uk

46. Adapting the GATES Architecture to Scheduling Faculty

R. Brazile* and K. Swigger  —   *Department of Computer Science, University of North Texas, Denton, TX 76203.
*Email:   brazile@cs.unt.edu

47. Constraint Programming for Scheduling

J. Kanet*, S. Ahire, and M. Gorman  —   *Department of MIS, Operations Management and Decision Sciences, University of Dayton, Dayton, OH 45469-2130.
*Email:   kanet@udayton.edu

48. Batch Production Scheduling in the Process Industry

K. Gentner, K. Neumann*, C. Schwindt, and N. Trautmann— *Universitat Karlsruhe, Institute fur Wirtschaftstheorie und Operations Research, Postfach 6980, D-76128 Karlsruhe, Germany.
*Email:   neumann@wior.uni-karlsruhe.de

49. A Composite Very Large-Scale Neighborhood Search Algorithms for the Vehicle Routing
Problem

R. Agarwal, R. Ahuja*, G. Laporte, and Z-J. M. Shen  —   *Department of Industrial and Systems Engineering, University of Florida, P.O. Box 116595, Gainesville, FL 32611-6595.
*Email:   ahuja@ufl.edu

50. Scheduling Problems in the Airline Industry

X. Qi, J. Yang* and G. Yu  —   *Department of Industrial and Manufacturing Engineering, New Jersey Instute of Technology, Newark, NJ 07102.
*Email:   yang@adm.njit.edu

51. Bus and Train Driver Scheduling

R. Kwan*  —   *School of Computing, University of Leeds, Leeds, LS2 9JT, United Kingdom.
*Email: rsk@comp.leeds.ac.uk

52. Sports Scheduling

K. Easton, G. Nemhauser, and M. Trick*  —   *Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA 15213.
*Email:   trick@mat.gsia.cmu.edu