Skip to main content
SpringerLink
Log in

Worst-Case Analysis of Heuristic Algorithms for Scheduling and Packing

  • Conference paper
Deterministic and Stochastic Scheduling

Part of the book series: NATO Advanced Study Institutes Series ((ASIC,volume 84))

Abstract

The increased focus on heuristics for the approximate solution of integer programs has led to more sophisticated analysis methods for studying their performance. This paper is concerned with the worst-case approach to the analysis of heuristic performance. A worst-case study establishes the maximum deviation from optimality that can occur when a specified heuristic is applied within a given problem class. This is an important piece of information that can be combined with empirical testing and other analyses to provide a more complete evaluation of a heuristic. In this paper the basic ground rules of worst-case analysis of heuristics are reviewed, and a large variety of the existing types of worst-case results are described in terms of the knapsack problem. Then existing results are surveyed for the parallel machine scheduling and bin packing problems. The paper concludes with a discussion of possibilities for further research.

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

Access this chapter

Log in via an institution
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.

References

  1. G. Ausiello, A. D’atri (1977) On the structure of combinatorial problems and structure preserving reductions. In: A. Salomaa, M. Steinby (eds.) (1977) Automata, Languages and Programming, Lecture Notes in Computer Science 52, Springer, Berlin, 45–60.

    Google Scholar 

  2. N. Christofides (1977) Worst-case analysis of a new heuristic for the travelling salesman problem. Management Sciences Research Report 388, Carnegie-Mellon University.

    Google Scholar 

  3. E.G. Coffman, Jr., M.R. Garey, D.S. Johnson (1977) An application of bin packing to multiprocessor scheduling. SIAM J. Comput. 7, 1–17.

    Article  MathSciNet  Google Scholar 

  4. S.A. Cook (1971) The complexity of theorem-proving procedures. Proc. 3rd Annual ACM Symp. Theory of Computing, 151–158.

    Google Scholar 

  5. G. Cornuejols, M.L. Fisher, G.L. Nemhauser (1977) Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Management Sci. 23, 789–810.

    Article  MathSciNet  MATH  Google Scholar 

  6. G. Cornuejols, G.L. Nemhauser (1978) Tight bounds for Christofides’ traveling salesman heuristic. Math. Programming 14, 116–121.

    Article  MathSciNet  MATH  Google Scholar 

  7. G. Cornuejols, G.L. Nemhauser, L.A. Wolsey (1978) Worst-case and probabilistic analysis of algorithms for a location problem. Operations Research Technical Report 375, Cornell University; Oper. Res., to appear.

    Google Scholar 

  8. M.A.H. Dempster, M.L. Fisher, L. Jansen, B.J. Lageweg, J.K. Lenstra, A.H.G. Rinnooy Kan (1981) Analytical evaluation of hierarchical planning systems. Oper. Res. 29, to appear.

    Google Scholar 

  9. M.A.H. Dempster, M.L. Fisher, L. Jansen, B.J. Lageweg, J.K. Lenstra, A.H.G. Rinnooy Kan (1981) Analysis of heuristics for stochastic programming: results for hierarchical scheduling problems. Report BW 142, Mathematisch Centrum, Amsterdam.

    Google Scholar 

  10. M.L. Fisher, G.L. Nemhauser, L.A. Wolsey (1979) An analysis of approximations for finding a maximum weight Hamiltonian circuit. Oper. Res. 27, 799–809.

    Article  MathSciNet  MATH  Google Scholar 

  11. M.L. Fisher, G.L. Nemhauser, L.A. Wolsey (1978) An analysis of approximations for maximizing submodular set functions — II. Math. Programming Stud. 8, 73–87.

    MathSciNet  Google Scholar 

  12. M.L. Fisher (1978) Worst-case analysis of heuristics. In: J. K. Lenstra, A.H.G. Rinnooy Kan, P. Van Emde Boas (eds.) (1978 Interfaces Between Computer Science and Operations Research, Mathematical Centre Tracts 99, Mathematisch Centrum, 87–108.

    Google Scholar 

  13. M.L. Fisher, D.S. Hochbaum (1980) Probabilistic analysis of the planar K-median problem. Math. Oper. Res. 5, 27–34.

    Article  MathSciNet  MATH  Google Scholar 

  14. M.L. Fisher (1979) On the equivalence of greedy covering and greedy location. Decision Sciences Working Paper 79-11-01, University of Pennsylvania.

    Google Scholar 

  15. A.M. Frieze (1978) Worst-case analysis of two algorithms for travelling salesman problems. Technical Report, Department o: Computer Science and Statistics, Queen Mary College, London.

    Google Scholar 

  16. M.R. Garey, D.S. Johnson (1976) The complexity of near-optimal graph coloring. J. Assoc. Comput. Mach. 23, 43–49.

    MathSciNet  MATH  Google Scholar 

  17. M.R. Garey, D.S. Johnson (1976) Approximation algorithms for combinatorial problems: an annotated bibliography. In: J.F. Traub (ed.) (1976) Algorithms and Complexity: New Directions and Recent Results, Academic Press, New York, 41–52.

    Google Scholar 

  18. M.R. Garey, D.S. Johnson (1978) “Strong” NP-completeness results: motivation, examples and implications. J. Assoc. Comput. Mach. 25, 499–508.

    MathSciNet  MATH  Google Scholar 

  19. M.R. Garey, R.L. Graham, D.S. Johnson (1978) Performance guarantees for scheduling algorithms. Oper. Res. 26, 3–21.

    Article  MathSciNet  MATH  Google Scholar 

  20. M.R. Garey, R.L. Graham, D.S. Jonson, A.C. Yao (1976) Resource constrained scheduling as generalized bin packing. J. Combin. Theory Ser. A 21, 257–298.

    Article  MATH  Google Scholar 

  21. M.R. Garey, D.S. Johnson (1979) Computers and Intractability: a Guide to the Theory of NP-Completeness, Freeman, San Francisco.

    MATH  Google Scholar 

  22. A.M. Geoffrion (1977) Objective function approximations in mathematical programming. Math. Programming 13, 23–27.

    Article  MathSciNet  MATH  Google Scholar 

  23. A.M. Geoffrion (1977) A priori error bounds for procurement commodity aggregation in logistics planning models. Naval Res. Logist. Quart. 24, 201–212.

    Article  MathSciNet  MATH  Google Scholar 

  24. A.M. Geoffrion, G.W. Graves (1974) Multi-commodity distribution system design by Benders decomposition. Management Sci. 20, 822–844.

    Article  MathSciNet  MATH  Google Scholar 

  25. R.L. Graham (1966) Bounds for certain multiprocessing anomalies. Bell System Tech. J. 45, 1563–1581.

    Google Scholar 

  26. R.L. Graham (1969) Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17, 416–429.

    Article  MathSciNet  MATH  Google Scholar 

  27. R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326.

    Article  MathSciNet  MATH  Google Scholar 

  28. O.H. Ibarra, C.E. Kim (1975) Fast approximation algorithms for the knapsack and sum of subset problems. J. Assoc. Comput. Mach. 22, 463–468.

    MathSciNet  MATH  Google Scholar 

  29. T.A. Jenkyns (1977) The greedy travelling salesman’s problem. Technical Report, Brock University.

    Google Scholar 

  30. D.S. Johnson (1974) Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9, 256–278.

    Article  MathSciNet  MATH  Google Scholar 

  31. D.S. Johnson (1973) Near optimal bin packing algorithms. Report MAC TR-109, Massachusetts Institute of Technology.

    Google Scholar 

  32. D.S. Johnson, A. Demers, J.D. Ullman, M.R. Garey, R.L. Graham (1974) Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 299–325.

    Article  MathSciNet  Google Scholar 

  33. R. Kannan, B. Korte (1978) Approximative combinatorial algorithms. Report 78107-OR, Institut f&3x00FC;r Ökonometrie und Operations Research, Universität Bonn.

    Google Scholar 

  34. R.M. Karp (1972) Reducibility among combinatorial problems. In: R.E. Miller, J.W. Thatcher (eds.) (1972) Complexity of Computer Computations, Plenum, New York, 85–103.

    Google Scholar 

  35. R.M. Karp (1975) On the computational complexity of combinatorial problems. Networks 5, 45–68.

    MathSciNet  MATH  Google Scholar 

  36. R.M. Karp (1976) The probabilistic analysis of some combinatorial search algorithms. In: J.F. Traub (ed.) (1976) Algorithms and Complexity: New Directions and Recent Results, Academic Press, New York, 1–19.

    Google Scholar 

  37. R.M. Karp (1977) Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. Math. Oper. Res. 2, 209–224.

    Article  MathSciNet  MATH  Google Scholar 

  38. E.L. Lawler (1978) Fast approximation algorithms for knapsack problems. In: J.K. Lenstra, A.H.G. Rinnooy Kan, P. Van Emde Boas (eds.) (1978) Interfaces Between Computer Science and Operations Research, Mathematical Centre Tracts 99, Mathematisch Centrum, Amsterdam, 109–139.

    Google Scholar 

  39. S. Lin, B.W. Kernighan (1973) An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21, 498–516.

    Article  MathSciNet  MATH  Google Scholar 

  40. N. Lynch, R.J. Lipton (1978) On structure preserving reductions. SIAM J. Comput. 7, 119–126.

    Article  MathSciNet  Google Scholar 

  41. T.G. Mairs, G.W. Wakefield, E.L. Johnson, K. Spielberg (1978) On a production allocation and distribution problem. Management Sci. 24, 1622–1630.

    Article  Google Scholar 

  42. R.E. Marsten, M.R. Muller, C.L. Killion (1978) Crew planning at Flying Tiger: a successful application of integer programming. MIS Technical Report 533, University of Arizona.

    Google Scholar 

  43. G.L. Nemhauser, L.A. Wolsey, M.L. Fisher (1978) An analysis of approximations for maximizing submodular set functions — I. Math. Programming 14, 265–294.

    Article  MathSciNet  MATH  Google Scholar 

  44. G.L. Nemhauser, L.A. Wolsey (1978) Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3, 177–188.

    Article  MathSciNet  MATH  Google Scholar 

  45. G.L. Nemhauser, L.A. Wolsey (1978) Maximizing submodular set functions: formulations, algorithms and applications. CORE Discussion Paper 7832, University of Louvain.

    Google Scholar 

  46. A. Paz, S. Moran (1977) Non-deterministic polynomial optimization problems and their approximation. In: A. Salomaa, M. Steinby (eds.) (1977) Automata, Languages and Programming, Lecture Notes in Computer Science 52, Springer, Berlin, 370–379.

    Google Scholar 

  47. S. Rabin, P. Kolesar (1978) Mathematical optimization of glaucoma visual field screening protocols. Documenta Ophthalmologica 45, 361–380.

    Article  Google Scholar 

  48. D.J. Rosenkrantz, R.E. Stearns, P.M. Lewis II (1977) An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6, 563–581.

    Article  MathSciNet  MATH  Google Scholar 

  49. S. Sahni, T. Gonzalez (1976) P-Complete approximation problems. J. Assoc. Comput. Mach. 23, 555–565.

    MathSciNet  MATH  Google Scholar 

  50. S. Sahni (1975) Approximate algorithms for the 0-1 knapsack problem. J. Assoc. Comput. Mach. 22, 115–124.

    MathSciNet  MATH  Google Scholar 

  51. S. Sahni (1976) Algorithms for scheduling independent tasks. J. Assoc. Comput. Mach. 23, 116–127.

    MathSciNet  MATH  Google Scholar 

  52. C. Westerberg, B. Bjorklund, E. Hultman (1977) An application of mixed integer programming in a Swedish steel mill. Interfaces.

    Google Scholar 

  53. E. Zemel (1978) Functions for measuring the quality of approximate solutions to zero-one programming problems. Disscussion Paper 323, Graduate School of Management, Northwestern University.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Pennsylvania, Philadelphia, USA

    Marshall L. Fisher

Authors
  1. Marshall L. Fisher
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Mathematics, Dalhousie University, Halifax, Nova Scotia, Canada

    M. A. H. Dempster

  2. Balliol College, Oxford, England

    M. A. H. Dempster

  3. Mathematisch Centrum, P.O. Box 4079, 1009 AB, Amsterdam, The Netherlands

    J. K. Lenstra

  4. Econometric Institute H2-11, Erasmus University, P.O. Box 1738, 3000 DR, Rotterdam, The Netherlands

    A. H. G. Rinnooy Kan

Rights and permissions

Reprints and permissions

Copyright information

© 1982 D. Reidel Publishing Company

About this paper

Cite this paper

Fisher, M.L. (1982). Worst-Case Analysis of Heuristic Algorithms for Scheduling and Packing. In: Dempster, M.A.H., Lenstra, J.K., Rinnooy Kan, A.H.G. (eds) Deterministic and Stochastic Scheduling. NATO Advanced Study Institutes Series, vol 84. Springer, Dordrecht. https://doi.org/10.1007/978-94-009-7801-0_2

Download citation

  • DOI: https://doi.org/10.1007/978-94-009-7801-0_2

  • Publisher Name: Springer, Dordrecht

  • Print ISBN: 978-94-009-7803-4

  • Online ISBN: 978-94-009-7801-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation