[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Focused simulated annealing search: An application to job shop scheduling

  • Simulated Annealing
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

This paper presents a simulated annealing search procedure developed to solve job shop scheduling problems simultaneously subject to tardiness and inventory costs. The procedure is shown to significantly increase schedule quality compared to multiple combinations of dispatch rules and release policies, though at the expense of intense computational efforts. A meta-heuristic procedure is developed that aims at increasing the efficiency of simulated annealing by dynamically inflating the costs associated with major inefficiencies in the current solution. Three different variations of this procedure are considered. One of these variations is shown to yield significant reductions in computation time, especially on problems where search is more likely to get trapped in local minima. We analyze why this variation of the meta-heuristic is more effective than the others.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.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

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. K.R. Baker,Introduction to Sequencing and Scheduling (Wiley, 1974).

  2. V. Cerny, Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, J. Opt. Theory Appl. 45(1985)41–51.

    Article  Google Scholar 

  3. S. French,Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop (Wiley, 1982).

  4. T. Fry, R. Amstrong and J. Blackstone, Minimizing weighted absolute deviation in single machine scheduling, IIE Trans. 19(1987)445–450.

    Google Scholar 

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

  6. M.R. Garey, R.E. Tarjan and G.T. Wilfgong, One-processor scheduling with symmetric earliness and tardiness penalties, Math. Oper. Res. 13(1988)330–348.

    Google Scholar 

  7. F. Glover, Heuristics for integer programming using surrogate constraints, Dec. Sci. 8(1977)156–166.

    Google Scholar 

  8. F. Glover, Future paths for integer programming and links to artificial intelligence, Comp. Oper. Res. 13(1986)533–549.

    Article  Google Scholar 

  9. F. Glover, Tabu thresholding: Improved search by non-monotonic trajectories, Technical Report, Graduate School of Business, University of Colorado, Boulder, CO 80309–0419 (1993).

    Google Scholar 

  10. F. Glover and M. Laguna, Tabu search, inModern Heuristic Techniques for Combinatorial Problems, ed. C. Reeves (Blackwell Scientific, Oxford, 1992) pp. 70–150.

    Google Scholar 

  11. J. Holland,Adaptation in Natural and Artificial Systems (University of Michigan Press, Ann Arbor, MI, 1975).

    Google Scholar 

  12. D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon, Optimization by sumulated annealing: Experimental evaluation. Part I: Graph partitioning, Oper. Res. 37(1989)865–892.

    Google Scholar 

  13. D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon, Optimization by simulated annealing: Experimental evaluation, Part II: Graph coloring and number partitioning, Oper. Res. 39(1991) 378–406.

    Google Scholar 

  14. S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing, Science 220(1983) 671–680.

    Article  Google Scholar 

  15. M. Laguna and F. Glover, Integrating target analysis and tabu search for improved scheduling systems, Expert Syst. Appl. 6(1993)287–297.

    Article  Google Scholar 

  16. H. Matsuo, C.J. Suh and R.S. Sullivan, A controlled search simulated annealing method for the general job shop scheduling problem, Technical Report, Department of Management, The University of Texas at Austin, Austin, TX (1988).

    Google Scholar 

  17. T.E. Morton, SCHED-STAR: A price-based shop scheduling module, J. Manufac. Oper. Manag. (1988) 131–181.

  18. T.E. Morton and D.W. Pentico,Heuristic Scheduling Systems, Wiley Series in Engineering and Technology Management (1993).

  19. E. Nowicki and C. Smutnicki, A fast tabu search algorithm for the job shop problem, Technical University of Wroclaw, Institute of Engineering Cybernetics. ul. Janiszewskiego 1/17, 50–372 Wroclaw, Poland (1993).

    Google Scholar 

  20. I.H. Osman and C.N. Potts, Simulated annealing for permutation flow-shop scheduling, OMEGA Int. J. Manag. Sci. 17(1989)551–557.

    Article  Google Scholar 

  21. I.H. Osman, Meta-strategy simulated annealing and tabu search algorithms for the vehicle routing problem, Ann. Oper. Res. 41(1993)421–451.

    Article  Google Scholar 

  22. P.S. Ow and T. Morton, The single machine early/tardy problem, Manag. Sci. 35(1989)177–191.

    Article  Google Scholar 

  23. N. Sadeh, Look-ahead techniques for micro-opportunistic job shop scheduling, Ph.D. Thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213 (March 1991).

    Google Scholar 

  24. N. Sadeh, Micro-opportunistic scheduling: The micro-boss factory scheduler, in:Intelligent Scheduling, ed. Zweben and Fox (Morgan Kaufmann, 1994) Chap. 4.

  25. E. Taillard, Parallel tabu search techniques for the job shop scheduling problem, ORSA J. Comp. 6(1994)108–117.

    Google Scholar 

  26. P.J. van Laarhoven, E.H.L. Aarts and J.K. Lenstra, Job shop scheduling by simulated annealing, Oper. Res. 40(1992)113–125.

    Google Scholar 

  27. A.P.J. Vepsalainen and T.E. Morton, Priority rules for job shops with weighted tardiness costs, Manag. Sci. 33(1987)1035–1047.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The Robotics Institute, Carnegie Mellon University, 15213, Pittsburgh, PA, USA

    Norman M. Sadeh

  2. NEC C & C Research Laboratories, 4-1-1 Miyazaki, Miyamae-ku, 216, Kawasaki, Japan

    Yoichiro Nakakuki

Authors
  1. Norman M. Sadeh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yoichiro Nakakuki
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sadeh, N.M., Nakakuki, Y. Focused simulated annealing search: An application to job shop scheduling. Ann Oper Res 63, 77–103 (1996). https://doi.org/10.1007/BF02601640

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02601640

Keywords

Search

Navigation