Abstract
In this paper, a new metaheuristic for the job shop scheduling problem is proposed. Our approach uses the backbone and “big valley” properties of the job shop scheduling problem. The results of the computational experiments have demonstrated the high efficiency of our approach. New upper bounds have been obtained for many problems.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Aiex, R., Binato, S., Resende, M.: Parallel grasp with path-relinking for job shop scheduling. Parallel Comput. 29, 393–430 (2003)
Balas, E., Vazacopoulos, A.: Guided local search with shifting bottleneck for job shop scheduling. Manag. Sci. 44, 262–275 (1998)
Binato, S., Hery, W., Loewenstern, D., Resende, M.: A GRASP for job shop scheduling. In: Essays and Surveys on Metaheuristics, pp. 59–79. Kluwer Academic, Dordrecht (2001)
Blazewicz, J., Domschke, W., Pesch, E.: The job-shop scheduling problem: Conventional and new solution techniques. Eur. J. Oper. Res. 93(1), 1–33 (1996)
Darwen, P.J.: Looking for the big valley in the fitness landscape of single machine scheduling with batching, precedence constraints, and sequence-dependent setup times. In: 5th Australasia-Japan Joint Workshop University of Otago, Dunedin, New Zealand, 19–21 November 2001
Demirkol, E., Mehta, S., Uzsloy, R.: Benchmarks for job shop scheduling problems. Eur. J. Oper. Res. 109, 137–141 (1997)
Grabowski, J., Nowicki, E., Smutnicki, C.: Block algorithm for scheduling of operations in job-shop system. Prz. Stat. 35, 67–80 (1988) (in Polish)
Internet: Home page Eric Taillard http://www.eivd.ch/ina/collaborateurs/etd/default.htm (2008). Accessed 22 January 2008
Jain, A., Meeran, S.: Deterministic job shop scheduling: Past, present and future. Eur. J. Oper. Res. 113, 390–434 (1999)
Internet: Job Shop Scheduling webpage http://plaza.ufl.edu/shylo/jobshopinfo.html (2008). Accessed 22 January 2008
Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Lawler, E.L., Lenstra, J.-K., Rinnooy Kan, A.: Recent Developments in Deterministic Sequencing and Scheduling, pp. 35–73. Reidel, Dordrecht (1982)
Lee, C.-Y., Pinedo, M.: Optimization and heuristic scheduling. In: Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Applied Optimization, pp. 569–584. Oxford University Press, London (2002)
Lourenco, H., Martin, O., Stützle, T.: Iterated local search. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics. Kluwer Academic, Dordrecht (2003)
Nowicki, E., Smutnicki, C.: A fast tabu search algorithm for the job-shop problem. Manag. Sci. 42(6), 797–813 (1996)
Nowicki, E., Smutnicki, C.: An advanced tabu search algorithm for the job shop problem. J. Sched. 8(2), 145–159 (2005)
Nowicki, E., Smutnicki, C.: Some new ideas in TS for job shop scheduling. In: Operations Research/Computer Science Interfaces Series, vol. 30, pp. 165–190. Springer, Berlin (2005). Part II
Nowicki, E., Smutnicki, C.: Some aspects of scatter search in the flow-shop problem. EJOR 169(2), 654–666 (2006)
Pardalos, P., Shylo, O.: An algorithm for the job shop scheduling problem based on global equilibrium search techniques. Comput. Manag. Sci. 3(4), 331–348 (2006)
Roy, B., Sussman, B.: Les problèm d’ordonnancement avec contraintes disjonctives. Note DS9 bis, SEMA, Paris (1964) (in French)
Shylo, V.: A global equilibrium search method. Kybern. Syst. Anal. 1, 74–80 (1999) (in Russian)
Streeter, J., Smith, S.: How the landscape of random job shop scheduling instances depends on the ratio of jobs to machines. J. Artif. Intell. Res. 26, 247–287 (2006)
Taillard, E.: Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64, 278–285 (1993)
Van Laarhoven, P., Aarts, E., Lenstra, J.: Job shop scheduling by simulated annealing. Oper. Res. 40, 113–125 (1992)
Watson, J., Howe, A., Whitley, L.: An analysis of iterated local search for job-shop scheduling. In: Fifth Metaheuristics International Conference (MIC 2003), September 2003
Watson, J.-P., Beck, J., Howe, A., Whitley, L.: Problem difficulty for tabu search in job-shop scheduling. Artif. Intell. 143(2), 189–217 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research partially supported by NSF and AirForce grants.
Rights and permissions
About this article
Cite this article
Pardalos, P.M., Shylo, O.V. & Vazacopoulos, A. Solving job shop scheduling problems utilizing the properties of backbone and “big valley”. Comput Optim Appl 47, 61–76 (2010). https://doi.org/10.1007/s10589-008-9206-5
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-008-9206-5