Skip to main content
Springer Nature Link
Log in

Job shop scheduling

  • Reference work entry
  • First Online:
Encyclopedia of Operations Research and Management Science

  • 82 Accesses

INTRODUCTION

In the United States today, there are approximately 40,000 factories producing metalfabricated parts. These parts end up in a wide variety of products sold here and abroad. These factories employ roughly 2 million people and ship close to $3 billion worth of products every year. The vast majority of these factories are what we call “job shops,” meaning that the flow of raw and unfinished goods through them is completely random. Over the years, the behavior and performance of these job shops have been the focus of considerable attention in the operations research (OR) literature. Research papers on topics such as factory layout, inventory control, process control, production scheduling, and resource utilization can be found in almost every issue of every OR journal on the market today. The most popular of these topics is production (often referred to as job shop) scheduling. Job shop scheduling can be thought of as the allocation of resources over a specified time to...

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

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

    Google Scholar 

  2. Agin, N. (1966). “Optimum seeking with branch and bound,” Management Science, 13, 176–185.

    Google Scholar 

  3. Baker, K. (1974). Introduction to Sequencing and Scheduling, John Wiley, New York.

    Google Scholar 

  4. Balas, E. (1965). “An additive algorithm for solving linear programs with zero-one variables,” Operations Research, 13, 517–546.

    Google Scholar 

  5. Balas, E. (1967). “Discrete programming by the filter method,” Operations Research, 15, 915–957.

    Google Scholar 

  6. Balas, E. (1969). “Machine sequencing via disjunctive graphs: An implicit enumeration algorithm,” Operations Research, 17, 1–10.

    Google Scholar 

  7. Balas, E. (1970). “Machine sequencing: disjunctive graphs and degree-constrained subgraphs,” Naval Research Logistics Quarterly, 17, 941–957.

    Google Scholar 

  8. Bean, J. and Birge, J. (1986). “Match-up real-time scheduling,” NBS Special Publication 724, 197–212.

    Google Scholar 

  9. Benders, J. (1960). “Partitioning procedures for solving mixed-variables mathematical programming problems,” Numersche Mathematik, 4(3), 238–252.

    Google Scholar 

  10. Blackstone, J., Phillips, D., and Hogg, G. (1982). “A state-of-the-art survey of dispatching rules for manufacturing job shop operations,” International Jl. Production Research, 20(1), 27–45.

    Google Scholar 

  11. Conway, R., Maxwell, W., and Miller, L.W. (1967). Theory of Scheduling, Addison-Wesley, Reading, Massachusetts.

    Google Scholar 

  12. Dantzig, G. and Wolfe, P. (1960). “Decomposition principles for linear programs,” Naval Research Logistics Quarterly, 8, 101–111.

    Google Scholar 

  13. Daouas, T., Ghedira, K., and Muller, J. (1995). “Distributed flow shop scheduling problem versus local optimization,” Proceedings of the First International Conference on Multi-Agent Systems, MIT Press, Cambridge, Massachusetts.

    Google Scholar 

  14. Davis, L. (1985). “Job shop scheduling with genetic algorithms,” Proceedings of an International Conference on Genetic Algorithms and Their Applications, Carnegie-Mellon University, 136–140.

    Google Scholar 

  15. Davis, W. and Jones, A. (1988). “A real-time production scheduler for a stochastic manufacturing environment,” International Jl. Computer Integrated Manufacturing, 1(2), 101–112.

    Google Scholar 

  16. Dettmer, W. (1997). Goldratt's Theory of Constraints: A Systems Approach to Continuous Improvement, Quality Press, Milwaukee, Wisconsin.

    Google Scholar 

  17. Foo, Y. and Takefuji, Y. (1988). “Stochastic neural networks for solving job-shop scheduling: Part 2 — Architecture and simulations,” Proceedings of the IEEE International Conference on Neural Networks, published by IEEE TAB, Piscataway, New Jersey, II283–II290.

    Google Scholar 

  18. Fox, M. (1983). “Constraint-Directed Search: A Case Study of Job Shop Scheduling,” Ph.D. Dissertation, Carnegie-Mellon University, Pittsburgh, Pennsylvania.

    Google Scholar 

  19. Gershwin, S. (1989). “Hierarchical flow control: a framework for scheduling and planning discrete events in manufacturing systems,” Proceedings of IEEE Special Issue on Discrete Event Systems, 77, 195–209.

    Google Scholar 

  20. Glover, F. (1989). “Tabu search-Part I,” ORSA Jl. Computing, 1, 190–206.

    Google Scholar 

  21. Glover, F. (1990). “Tabu search-Part II,” ORSA Jl. Computing, 2, 4–32.

    Google Scholar 

  22. Glover, F. (1996). “Tabu search and adaptive memory programming — advances, applications and challenges,” Interfaces in Computer Science and Operations Research: Advances in Meta-heuristics, Optimization, and Stochastic Modeling Technologies, Barr R. S., Helgason R. V., and J.L. Kennington J. L., eds., Kluwer Academic Publishers, Dordrecht.

    Google Scholar 

  23. Goldberg, D. and Lingle, R. (1985). “Alleles, loci, and the traveling salesman problem,” Proceedings of the International Conference on Genetic Algorithms and Their Applications, Carnegie Mellon University, 162–164.

    Google Scholar 

  24. Goldberg, D. (1988). Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesley, Menlo Park, California.

    Google Scholar 

  25. Goldratt, E. (1990). Theory of Constraints, North River Press, Great Barrington, Massachusetts.

    Google Scholar 

  26. Goldratt, E. (1992). The Goal, North River Press, Great Barrington, Massachusetts.

    Google Scholar 

  27. Grabot, B. and Geneste, L. (1994). “Dispatching rules in scheduling: a fuzzy approach,” International Jl. Production Research, 32, 903–915.

    Google Scholar 

  28. Hopfield, J. and Tank, D. (1985). “Neural computation of decisions in optimization problems,” Biological Cybernetics, 52, 141–152.

    Google Scholar 

  29. Jeffcoat, D. and Bulfin, R. (1993). “Simulated annealing for resource-constrained scheduling,” European Jl. Operational Research, 70, 43–51.

    Google Scholar 

  30. Kirkpatrick, S., Gelatt, C., and Vecchi, M. (1983). “Optimization by simulated annealing,” Science, 220(4598), 671–680.

    Google Scholar 

  31. Krucky, J. (1994). “Fuzzy family setup assignment and machine balancing,” Hewlett-Packard Jl., June, 51–64.

    Google Scholar 

  32. Lawler, E. and Wood, D. (1966). “Branch and bound methods: a survey,” Operations Research, 14, 699–719.

    Google Scholar 

  33. Lo, Z. and Bavarian, B. (1991). “Scheduling with neural networks for flexible manufacturing systems,” Proceedings of the IEEE International Conference on Robotics and Automation, Sacramento, California, 818–823.

    Google Scholar 

  34. McKenzie, L. (1976). “Turnpike theory,” Econometrics, 44, 841–864.

    Google Scholar 

  35. Montazer, M. and Van Wassenhove, L. (1990). “Analysis of scheduling rules for an FMS,” International Jl. Production Research, 28, 785–802.

    Google Scholar 

  36. Morton, E. and Pentico, D. (1993). Heuristic Scheduling Systems, John Wiley, New York.

    Google Scholar 

  37. Panwalker, S. and Iskander, W. (1977). “A survey of scheduling rules,” Operations Research, 25, 45–61.

    Google Scholar 

  38. Parunak, H., Irish, B., Kindrick, J., and Lozo, P. (1985). “Fractal actors for distributed manufacturing control,” Proceedings of the Second IEEE Conference on Artificial Intelligence Applications, 653–660.

    Google Scholar 

  39. Quinlan, J. (1986). “Induction of decision trees,” Machine Learning, 1, 81–106.

    Google Scholar 

  40. Rabelo, L. (1990). “Hybrid Artificial Neural Networks and Knowledge-Based Expert Systems Approach to Flexible Manufacturing System Scheduling,” Ph.D. Dissertation, University of Missouri-Rolla.

    Google Scholar 

  41. Rabelo, L., Sahinoglu, M., and Avula, X. (1994). “Flexible manufacturing systems scheduling using Q-Learning,” Proceedings of the World Congress on Neural Networks, San Diego, California, I378–I385.

    Google Scholar 

  42. Rumelhart, D., McClelland, J., and the PDP Research Group (1986). Parallel Distributed Processing: Explorations in the Microstructure of Cognition, 1: Foundations, MIT Press, Cambridge, Massachusetts.

    Google Scholar 

  43. Saleh, A. (1988). “Real-Time Control of a Flexible Manufacturing Cell,” Ph.D. Dissertation, Lehigh University, Bethlehem, Pennsylvania.

    Google Scholar 

  44. Shapiro, J. (1979). “A survey of Lagrangian techniques for discrete optimization,” Annals Discrete Mathematics, 5, 113–138.

    Google Scholar 

  45. Slany, W. (1994). “Scheduling as a fuzzy multiple criteria optimization problem.” CD-Technical Report 94/62, Technical University of Vienna.

    Google Scholar 

  46. Smith, S. (1995). “OPIS: A methodology and architecture for reactive scheduling,” Intelligent Scheduling, M. Zweben and M. Fox, eds., Morgan Kaufman, San Francisco, California, 29–66.

    Google Scholar 

  47. Srinivasan, V. (1971). “A hybrid algorithm for the one machine sequencing problem to minimize total tardiness,” Naval Research Logistics Quarterly, 18, 317–327.

    Google Scholar 

  48. Starkweather, T., Whitley, D., Mathias, K., and Mc-Daniel, S. (1992). “Sequence scheduling with genetic algorithms,” Proceedings of the US/German Conference on New Directions for OR in Manufacturing, 130–148.

    Google Scholar 

  49. Starkweather, T., Whitley, D., and Cookson, B. (1993). “A Genetic Algorithm for scheduling with resource consumption,” Proceedings of the Joint German/US Conference on Operations Research in Production Planning and Control, 567–583.

    Google Scholar 

  50. Tesauro, G. (1992). “Practical issues in temporal difference learning,” Machine Learning, 8, 257–277.

    Google Scholar 

  51. Tsujimura, Y., Park, S., Chang, S., and Gen, M. (1993). “An effective method for solving flow shop scheduling problems with fuzzy processing times,” Computers and Industrial Engineering, 25, 239–242.

    Google Scholar 

  52. Vakharia, A. and Chang, Y. (1990). “A simulated annealing approach to scheduling a manufacturing cell,” Naval Research Logistics, 37, 559–577.

    Google Scholar 

  53. Watkins, C. (1989). “Learning from Delayed Rewards,” Ph.D. Dissertation, King's College, Cambridge, England.

    Google Scholar 

  54. Werbos, P. (1995). “Neurocontrol and supervised learning: An overview and evaluation,” Handbook of Intelligent Control: Neural, Fuzzy, and Adaptive Approaches, Van Nostrand Reinhold, New York, 65–89.

    Google Scholar 

  55. Wilkerson, L. and Irwin, J. (1971). “An improved algorithm for scheduling independent tasks,” AIIE Transactions, 3, 239–245.

    Google Scholar 

  56. Wu, D. (1987). “An Expert Systems Approach for the Control and Scheduling of Flexible Manufacturing Systems,” Ph.D. Dissertation, Pennsylvania State University.

    Google Scholar 

  57. Wysk, R., Wu, D., and Yang, F (1986). “A multi-pass expert control system (MPECS) for flexible manufacturing systems,” NBS Special Publication 724, 251–278.

    Google Scholar 

  58. Yih, Y. (1990). “Tracedriven knowledge acquisition (TDKA) for rule-based real-time scheduling systems,” Jl. Intelligent Manufacturing, 1, 217–230.

    Google Scholar 

  59. Zentner, M., Pekny, J., Reklaitis, G., and Gupta, N. (1994). “Practical considerations in using model-based optimization for the scheduling and planning of batch/semicontinuous processes,” Jl. Process Control, 4, 259–280.

    Google Scholar 

  60. Zhang, M. and Zhang, C. (1995). “The consensus of uncertainties in distributed expert systems,” Proceedings of the First International Conference on Multi-Agent Systems, MIT Press, Cambridge, Massachusetts.

    Google Scholar 

  61. Zhou, D., Cherkassky, V., Baldwin, T. and Hong, D. (1990). “Scaling neural networks for job shop scheduling,” Proceedings of the International Conference on Neural Networks, 3, 889–894.

    Google Scholar 

  62. Zweben, M., Daun, B., Davis, E., and Deale, M. (1995). “Scheduling and rescheduling with iterative repair,” Intelligent Scheduling, M. Zweben and M. Fox, eds., Morgan Kaufman, San Francisco, California, 241–256.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Massachusetts Institute of Technology, Cambridge, USA

    Luis C. Rabelo

  2. National Institute of Standards and Technology, Gaithersburg, Maryland, USA

    Albert Jones

Authors
  1. Luis C. Rabelo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Albert Jones
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Robert H. Smith School of Business, University of Maryland, College Part, Maryland, USA

    Saul I. Gass

  2. School of Information Technology & Engineering, George Mason University, Fairfax, Virginia, USA

    Carl M. Harris

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Kluwer Academic Publishers

About this entry

Cite this entry

Rabelo, L.C., Jones, A. (2001). Job shop scheduling . In: Gass, S.I., Harris, C.M. (eds) Encyclopedia of Operations Research and Management Science. Springer, New York, NY. https://doi.org/10.1007/1-4020-0611-X_490

Download citation

  • DOI: https://doi.org/10.1007/1-4020-0611-X_490

  • Published:

  • Publisher Name: Springer, New York, NY

  • Print ISBN: 978-0-7923-7827-3

  • Online ISBN: 978-1-4020-0611-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics