scheduling operations research

Scheduling and Sequencing

• Reference work entry
• First Online: 01 January 2016
• pp 1356–1363
• Cite this reference work entry

• Nicholas G. Hall 3 &
• Michael Magazine 4  

766 Accesses

Introduction

Scheduling is the allocation of limited resources over time to perform a given set of jobs or activities. The focus here is on scheduling models with applications to factory and computer systems. Other common uses of the term scheduling include:

Project scheduling – the determination of activity times and project duration for complex projects composed of multiple activities with precedence relations;

Workforce scheduling – the determination of the number of workers and their duty cycles to meet certain labor restrictions; and

Timetabling – the determination of the matching of participants with each other and with resources, such as sports scheduling or student/room exam assignments.

Scheduling problems have been studied informally for centuries. The Gantt Chart, developed in World War I for logistics purposes, is a graphical representation of tasks and resources over time, and was the first formal model used for scheduling purposes. Critical path methods were...

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Durable hardcover edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Adams, J., Balas, E., & Zawack, D. (1988). The shifting bottleneck procedure for job shop scheduling. Management Science, 34 , 391–401.

Article   Google Scholar  

Anderson, E. J., Glass, C. A., & Potts, C. N. (1997). Machine scheduling. In E. H. L. Aaarts & J. K. Lenstra (Eds.), 361–414 in Local Search in Combinatorial Optimization . Chichester, UK: Wiley.

Google Scholar  

Baker, K. (1995). Elements of sequencing and scheduling (Rev. ed.). Hanover, NH: Amos Tuck School of Business Administration, Dartmouth College.

Baker, K., & Scudder, G. (1990). Sequencing with earliness and tardiness penalties: A review. Operations Research, 38 , 22–36.

Baker, K., & Trietsch, D. (2009). Principles of sequencing and scheduling . Hoboken, NJ: Wiley.

Book   Google Scholar  

Bertsekas, D. P. (1987). Dynamic programming: Deterministic and stochastic models . Englewood Cliffs, NJ: Prentice Hall.

Blazewicz, J., Cellary, W., Slowinski, R., & Weglarz, J. (1986). Scheduling under resource constraints – Deterministic models. Annals of Operations Research , 7 .

Carlier, J., & Pinson, E. (1988). An algorithm for solving the job-shop problem. Management Science, 35 , 164–176.

Chen, Z.-L. (2010). Integrated production and outbound distribution scheduling: Review and extensions. Operations Research, 58 , 130–148.

Chen, Z.-L., & Hall, N. G. (2007). Supply chain scheduling: Conflict and cooperation in assembly systems. Operations Research, 55 , 1072–1089.

Conway, R., Maxwell, W., & Miller, L. (1967). Theory of scheduling . Reading, MA: Addison-Wesley.

Crama, Y. (1997). Combinatorial models for production scheduling in automated manufacturing systems. European Journal of Operational Research, 99 , 136–153.

Daniels, R., & Kouvelis, P. (1995). Robust scheduling to hedge against processing time uncertainty in single stage production. Management Science, 41 , 363–376.

Fisher, H., & Thompson, G. (1963). Probabilistic learning combinations of local job-shop scheduling rules. In J. Muth & G. Thompson (Eds.), Industrial scheduling (pp. 225–251). Englewood Cliffs, NJ: Prentice-Hal.

Fox, M. S., & Smith, S. F. (1984). ISIS: A knowledge-based system for factory scheduling. Expert Systems, 1 , 25–49.

French, S. (1982). Sequencing and scheduling: An introduction to the mathematics of the job shop . Chichester, UK: Harwood.

Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness . San Francisco: W.H. Freeman & Company.

Graham, R. (1969). Bounds on multiprocessor timing anomalies. SIAM Journal on Applied Mathematics, 17 , 416–425.

Hall, N. G., Kamoun, H., & Sriskandarajah, C. (1997). Scheduling in robotic cells: Classification, two and three machine cells. Operations Research, 45 , 421–439.

Hall, N. G., & Posner, M. E. (1991). Earliness-tardiness scheduling problems, I: Weighted deviation of completion times about a common due date. Operations Research, 39 , 847–856.

Hall, N. G., Posner, M. E., & Potts, C. N. (1998). Scheduling with finite capacity output buffers. Operations Research, 46 , S84–S97.

Hall, N. G., Posner, M. E., & Potts, C. N. (2009). Online scheduling with known arrival times. Mathematics of Operations Research, 34 , 92–102.

Hall, N. G., & Potts, C. N. (2003). Supply chain scheduling: Batching and delivery. Operations Research, 51 , 566–584.

Hall, N. G., & Sriskandarajah, C. (1996). A survey of machine scheduling problems with blocking and no-wait in process. Operations Research, 44 , 510–525.

Hoogeveen, H. (2005). Multicriteria scheduling. European Journal of Operational Research, 167 , 592–623.

Jackson, J. R. (1955). Scheduling a production line to minimize maximum tardiness . Research Report 43, Management Science Research Project, University of California, Los Angeles.

Johnson, S. (1954). Optimal two and three stage production schedules with setup times included. Naval Research Logistics Quarterly, 1 , 61–68.

Lawler, E., Lenstra, J., Rinnooy Kan, A., & Shmoys, D. (1993). Sequencing and scheduling: Algorithms and complexity. In S. Graves, A. Rinnooy Kan, & P. Zipkin (Eds.), Handbooks in operations research and management science (Logistics of production and inventory, Vol. 4). Amsterdam: North-Holland.

Lee, C.-Y. (2004). Machine scheduling with availability constraints. In J. Y.-T. Leung (Ed.), Handbook of scheduling: Algorithms, models and performance analysis (pp. 22-1–22-13). Boca Raton: Chapman & Hall/ CRC.

Lee, C.-Y., Li, L., & Pinedo, M. (1997). Current trends in deterministic scheduling. Annals of Operations Research, 70 , 1–42.

Lee, C.-Y., Uzsoy, R., & Martin-Vega, L. A. (1992). Efficient algorithms for scheduling semiconductor burn-in operations. Operations Research, 40 , 764–775.

Matsuo, H., Suh, C. J., & Sullivan, R. S. (1989). A controlled search simulated annealing method for the single machine weighted tardiness problem. Annals of Operations Research, 21 , 85–108.

McKay, K., Safayeni, F., & Buzacott, J. (1988). Job-shop scheduling theory: What is relevant. Interfaces, 18 (4), 84–90.

McNaughton, R. (1959). Scheduling with deadlines and loss functions. Management Science, 6 , 1–12.

Monma, C. L. (1981). Sequencing with general precedence constraints. Mathematics of Operations Research, 4 , 215–224.

Monma, C. L., & Potts, C. N. (1989). On the complexity of scheduling with batch setup times. Operations Research, 37 , 798–804.

Morton, T., & Pentico, D. (1993). Heuristic scheduling systems . New York: Wiley.

Ng, C. T., & Kovalyov, M. Y. (2004). An FPTAS for scheduling a two-machine flowshop with one unavailability interval. Naval Research Logistics, 51 , 307–315.

Pinedo, M. (1995). Scheduling: Theory, algorithms, and systems . Englewood Cliffs, NJ: Prentice Hall.

Pinedo, M., & Chao, X. (1998). Operations scheduling: Applications in manufacturing and services . Burr Ridge, IL: McGraw-Hill.

Potts, C. N., & Kovalyov, M. Y. (2002). Scheduling with batching: A review. European Journal of Operational Research, 120 , 228–249.

Potts, C. N., & Strusevich, V. A. (2009). Fifty years of scheduling: A survey of milestones. Journal of the Operational Research Society, 60 , S41–S68.

Pruhs, K., Sgall, J., & Torng, E. (2004). Online scheduling. In J. Y.-T. Leung (Ed.), Handbook of scheduling: Algorithms, models and performance analysis (pp. 15-1–15-43). Boca Raton: Chapman & Hall/ CRC.

Righter, R. (1994). Stochastic scheduling. In M. Shaked & G. Shanthikumar (Eds.), Stochastic orders . San Diego, CA: Academic Press.

Santos, C., & Magazine, M. (1985). Batching in single operation manufacturing systems. Operations Research Letters, 4 , 99–103.

Schmidt, G. (2000). Scheduling with limited machine availability. European Journal of Operational Research, 121 , 1–15.

Smith, W. (1956). Various optimizers for single stage production. Naval Research Logistics Quarterly, 3 , 59–66.

Storer, R. H., Wu, S. D., & Vaccari, R. (1992). New search spaces for sequencing problems with application to job shop scheduling. Management Science, 38 , 1495–1509.

Trietsch, D., & Baker, K. (1993). Basic techniques for lot streaming. Operations Research, 41 , 1065–1076.

Widmer, M., & Hertz, A. (1989). A new heuristic method for the flow shop sequencing problem. European Journal of Operational Research, 41 , 186–193.

Download references

Author information

Authors and affiliations.

Department of Management Sciences, Fisher College of Business, The Ohio State University, 658 Fisher Hall, 2100 Neil Avenue, Columbus, OH, 43210-1144, USA

Nicholas G. Hall

College of Business, University of Cincinnati, 2925 Campus Green Drive, 210020, Cincinnati, OH, 45221-0020, USA

Michael Magazine

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Nicholas G. Hall .

Editor information

Editors and affiliations.

Robert H. Smith School of Business, University of Maryland, College Park, MD, USA

Saul I. Gass

Robert H. Smith School of Business and Institute for Systems Research, University of Maryland, College Park, MD, USA

Michael C. Fu

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer Science+Business Media New York

About this entry

Cite this entry.

Hall, N.G., Magazine, M. (2013). Scheduling and Sequencing. In: Gass, S.I., Fu, M.C. (eds) Encyclopedia of Operations Research and Management Science. Springer, Boston, MA. https://doi.org/10.1007/978-1-4419-1153-7_925

Download citation

DOI : https://doi.org/10.1007/978-1-4419-1153-7_925

Published : 23 January 2016

Publisher Name : Springer, Boston, MA

Print ISBN : 978-1-4419-1137-7

Online ISBN : 978-1-4419-1153-7

eBook Packages : Business and Economics Reference Module Humanities and Social Sciences Reference Module Business, Economics and Social Sciences

Share this entry

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

Machine Scheduling

Research: hybrid (meta-)heuristic optimization for single machine, parallel machine and job shop scheduling problems, 1. an overview of genetic algorithms for the single machine scheduling problem.

• Set1 (Dependent due dates set)
• Set2 (Independent due dates set)
• Sels, V. and Vanhoucke, M., 2011, “A hybrid dual-population genetic algorithm for the single machine maximum lateness problem”, Lecture Notes in Computer Science, 6622, 14–25.
• Sels, V. and Vanhoucke, M., 2012, “Genetic algorithms for single machine scheduling problems: a trade-off between intensifications and diversification”, In A.R. Muñoz and I.G. Rodriguez (Eds.), Handbook of Genetic Algorithms: New Research, 265-293

2. Single machine scheduling with release times and family setups

• SMS instances with family setup times
• Overview of the computational results
• Sels, V. and Vanhoucke, M., 2012, “A hybrid genetic algorithm for the single machine maximum lateness problem with release times and family setups”, Computers and Operations Research, 39, 2346-2358.

3. Single machine scheduling with precedence constraints 

• Sels, V. and Vanhoucke, M., 2014, “A hybrid electromagnetism-like mechanism/tabu search procedure for the single machine scheduling problem with a maximum lateness objective”, Computers and Industrial Engineering, 67, 44-55.

4. Unrelated parallel machine scheduling problem

• Sels, V., Coelho, J., Dias, A.M. and Vanhoucke, M., 2014, “Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem”, Computers and Operations Research, To Appear.

5. A hybrid single and dual population search procedure for the job shop scheduling problem

• Excel file (with Job Shop results after year 2000)
• PDF file (with Job Shop results after year 2000)
• Sels, V., Craeymeersch, K. and Vanhoucke, M., 2011, “A hybrid single and dual population search procedure for the job shop scheduling problem”, European Journal of Operational Research, 215, 512-523.

6. The parallel machine scheduling problem: A case study

• Kerkhove, L.P. and Vanhoucke, M., 2014, "Scheduling of unrelated parallel machines with limited server availability on multiple production locations: a case study in knitted fabrics", International Journal of Production Research, 52, 2630–265 

7. The flexible job shop problem: A case study

• Sels, V., Steen, F. and Vanhoucke, M., 2011, “Applying a hybrid job shop procedure to a Belgian manufacturing company producing industrial wheels and castors in rubber”, Computers and Industrial Engineering, 61, 697-708.

8. Comparison of priority rules for the job shop scheduling problem under different objective functions

• Appendix with abbreviations and the construction of the combined rules
• Sels, V., Gheysen, N. and Vanhoucke, M., 2012, “A comparison of priority rules for the job shop scheduling problem under different flow time- and tardiness-related objective functions”, International Journal of Production Research, 39, 2346-2358.