A Tabu Search Algorithm for the Stage Shop Problem

Abstract:

This paper presents stage shop problem which is a special case of the general shop. The stage shop is a more realistic generalization of the mixed shop problem. In the stage shop problem, each job has several stages of operations. In order to solve the stage shop problem with makespan objective function, a tabu search algorithm is developed. In addition, an existing lower bound of the job shop is adapted to the new problem and the computational results have been compared to it. The proposed TS algorithm has reached the optimal solutions for about half of the problem instances

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

References

[1] 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

[2] P. Brucker, Scheduling Algorithms, Fourth Edition. Springer Verlag, Berlin, (2004).

[3] N. V. Shakhlevich, Y. N. Sotskov and F. Werner, Complexity of mixed shop scheduling problems: A survey, European Journal of Operational Research, vol. 120, 2000, p.343–351.

DOI: 10.1016/s0377-2217(99)00161-7

[4] W. Ferrell, J. Sale, J. Sams and M. Yellamarju, Evaluating simple scheduling rules in a mixed shop environment, Computers & Industrial Engineering, vol. 38, 2000, p.39–66.

DOI: 10.1016/s0360-8352(00)00028-0

[5] A. Ramudhin and P. Marier, The generalized shifting bottleneck procedure, European Journal of Operational Research, vol. 93, 1996, p.34–48.

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

[6] T. Kis, Job-shop scheduling with processing alternatives, European Journal of Operational Research, vol. 151, 2003, p.307–332.

DOI: 10.1016/s0377-2217(02)00828-7

[7] 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

[8] J. Carlier, The one machine sequencing problem, European Journal of Operational Research, vol. 11, 1982, p.42–47.

DOI: 10.1016/s0377-2217(82)80007-6

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

[10] J. Watson, J. C. Beck, A. E. Howe and L. D. Whitley, Problem difficulty for tabu search in job-shop scheduling, Artificial Intelligence, vol. 143, 2003, p.189–217.

DOI: 10.1016/s0004-3702(02)00363-6

[11] 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

[12] 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

[13] 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

[14] 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

[15] 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

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