A New Neighborhood for the Job Shop Scheduling Problem

Abstract:

The effectiveness of the local search algorithms for shop scheduling problems is proved frequently. Local search algorithms like tabu search use neighborhood structures in order to obtain new solutions. This paper presents a new neighborhood for the job shop scheduling problem. In this neighborhood, few enhanced conditions are proposed to prevent cycle generation. These conditions allow that the neighborhood encompasses larger number of solutions without increasing the order of computational efforts.

• Periodical: Advanced Materials Research (Volumes 433-440)
• Pages: 1540-1544
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.433-440.1540
• Online since: January 2012
• Authors: Mohammad Mahdi Nasiri, Farhad Kianfar
• Keywords: General Shop, Mixed Shop, Scheduling, Stage Shop

References

[1] C. Y. Zhang, , P. G. Li, Z.L. Guan and Y. Q. Rao, A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem, Computers & Operations Research, vol. 34, 2007, p.3229 – 3242.

DOI: 10.1016/j.cor.2005.12.002

[2] D. Applegate and W. Cook, A computational study of the job-shop scheduling problem, ORSA Journal on Computing, vol. 3(2), 1991, p.149–156.

DOI: 10.1287/ijoc.3.2.149

[3] M. R. Garey, D. S. Johnson and R. Sethi, The complexity of flowshop and job-shop scheduling, Mathematics of Operations Research, vol. 1, 1976, p.117–29.

DOI: 10.1287/moor.1.2.117

[4] M. M. Nasiri and F. Kianfar, A hybrid scatter search for the partial job shop scheduling problem, Int J Adv Manuf Technol. doi: 10. 1007/s00170-010-2792-2.

DOI: 10.1007/s00170-010-2792-2

[5] E. Nowicki and C. Smutnicki, A fast taboo search algorithm for the job shop problem, Management Science, vol. 42(6), 1996, p.797–813.

DOI: 10.1287/mnsc.42.6.797

[6] J. Blazewicz, W. Domschke and E. Pesch, The job shop scheduling problem: Conventional and new solution techniques, European Journal of‏ Operational Research, vol. 93, 1996, p.1–33.

DOI: 10.1016/0377-2217(95)00362-2

[7] E. Balas and A. Vazacopoulos, Guided local search with shifting bottleneck for job shop scheduling, Management Science, vol. 44(2), 1998, p.262–275.

DOI: 10.1287/mnsc.44.2.262

[8] E. Nowicki and C. Smutnicki, An advanced tabu search algorithm for the job shop problem, Journal of Scheduling, vol. 8(2), 2005, pp.145-159.

DOI: 10.1007/s10951-005-6364-5

[9] P. Pardalos, and O. Shylo, An algorithm for the job shop scheduling problem based on global equilibrium search techniques, Computational Management Science, vol. 3, 2006, pp.331-348.

DOI: 10.1007/s10287-006-0023-y

[10] C. Y. Zhang, P. G. Li, Y. Q. Rao and Z. L. Guan, A very fast TS/SA algorithm for the job shop scheduling problem, Computers & Operations Research, vol. 35, 2008, p.282–294.

DOI: 10.1016/j.cor.2006.02.024

[11] P. Pardalos, O. Shylo and A. Vazacopoulos, Solving job shop scheduling problems utilizing the properties of backbone and big valley, Computational Optimization and Applications, vol. 47, 2010, pp.61-76.

DOI: 10.1007/s10589-008-9206-5

[12] E. D. Taillard, Benchmarks for basic scheduling problems, European Journal of‏ Operational Research, vol. 64(2), 1993, p.278–285.

DOI: 10.1016/0377-2217(93)90182-m

[13] E. D. Taillard, http: /mistic. heig-vd. ch/taillard. November (2009).

[14] F. Glover and M. Laguna, Tabu search. Dordrecht, Kluwer Academic Publishers, (1997).

[15] P. J. M. Van Laarhoven, E. H. L. Aarts and J. K. Lenstra, Job shop scheduling by simulated annealing, Operations Research, vol. 40(1), 1992, p.113–125.

DOI: 10.1287/opre.40.1.113

[16] M. Dell'Amico and M. Trubian, Applying tabu-search to job-shop scheduling problem, Annals of Operations Research, vol. 41(1–4), 1993, p.231–252.

DOI: 10.1007/bf02023076

[17] J. Grabowski and M. Wodecki, A very fast tabu search algorithm for the job shop problem. In: Rego C, Alidaee B (Eds), Metaheuristic optimization via memory and evolution: Tabu Search and Scatter Search, Dordrecht: Kluwer Academic Publishers, Boston (2005).

DOI: 10.1007/0-387-23667-8_5