Skip to main content

Combinatorial Scheduling Theory

  • Chapter
Mathematics Today Twelve Informal Essays

Abstract

Things had not been going at all well in the assembly section of the Acme Bicycle Company. For the past six months, the section had consistently failed to meet its quota and heads were beginning to roll. As newly appointed foreman of the assembly section, you have been brought in to remedy this sad state of affairs. You realize that this is your big chance to catch the eye of upper management, so the first day on the job you roll up your sleeves and begin finding out everything you can about what goes on in the section.

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

Access this chapter

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight 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

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Suggestions for Further Reading

General

  • Graham, Ronald L. and Garey, Michael R. The limits to computation. 1978 Yearbook of Science and the Future. Encyclopaedia Britannica, 1977, pp. 170–185.

    Google Scholar 

  • Knuth, Donald E. Mathematics and computer science: coping with finiteness. Science 194 (December 17, 1976 ) 1235–1242.

    Article  MATH  MathSciNet  Google Scholar 

  • Kolata, Gina Bari. Analysis of algorithms: coping with hard problems. Science 186 (1974) 520–521.

    Article  MathSciNet  Google Scholar 

  • Steen, Lynn Arthur. Computational unsolvability. Science News, 109 (1976) 298–301.

    Article  Google Scholar 

Technical

  • Garey, Michael R., Graham, Ronald L., and Johnson, D.S. Performance guarantees for scheduling algorithms. Operations Research 26 (1978) 3–21.

    Article  MATH  MathSciNet  Google Scholar 

  • Garey, Michael R. and Johnson, David S. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1978.

    Google Scholar 

  • Graham, Ronald L. Bounds on the performance of scheduling algorithms. In Coffman, E. G., Computer and Jobshop Scheduling Theory. Wiley, New York, 1976.

    Google Scholar 

Download references

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 1978 Conference Board of the Mathematical Sciences

About this chapter

Cite this chapter

Graham, R.L. (1978). Combinatorial Scheduling Theory. In: Steen, L.A. (eds) Mathematics Today Twelve Informal Essays. Springer, New York, NY. https://doi.org/10.1007/978-1-4613-9435-8_8

Download citation

  • DOI: https://doi.org/10.1007/978-1-4613-9435-8_8

  • Publisher Name: Springer, New York, NY

  • Print ISBN: 978-1-4613-9437-2

  • Online ISBN: 978-1-4613-9435-8

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics