A New Solution Seed for Job Shop Scheduling Problem

Abstract:

Scheduling for job shop is very important in both fields of production management and combinatorial optimization. Since the problem is well known as NP-Hard class, many metaheuristic approaches are developed to solve the medium and large scale problems. One of the main elements of these metaheuristics is the solution seed structure. Solution seed represent the coding structure of real solution. In this paper, a new solution seed for job shop scheduling is presented. This solution seed is compared with a famous solution seed presented for the job shop scheduling. Since the problem is well known as NP-Hard class, a Tabu search algorithm is developed to solve large scale problems. The proposed solution seed are examined using an example and tabu search algorithm.

• Periodical: Applied Mechanics and Materials (Volumes 110-116)
• Pages: 3899-3905
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.110-116.3899
• Online since: October 2011
• Authors: Parviz Fattahi, Mojdeh Shirazi Manesh, Abdolreza Roshani
• Keywords: Job Shop, Scheduling, Solution Seed, Tabu Search

References

[1] J. Adams, E. Balas, and D. Zawack, The shifting bottleneck procedure for job shop scheduling, Management Science. 34 (1988) 391–401.

DOI: 10.1287/mnsc.34.3.391

[2] K.R. Baker, Sequencing rules and due-date assignments in a job shop, Management Science. 30 (1984) 1093–1104.

DOI: 10.1287/mnsc.30.9.1093

[3] M.R. Garey, D.S. Johnson, and R. Sethi, The complexity of flow shop and job shop scheduling, Mathematics of Operations Research. 1 (1976) 117-129.

[4] T. Satake, K. Morikawa, K. Takahashi, and N. Nakamura, Simulated annealing approach for minimizing the makespan of the general job-shop, International Journal of Production Economics. 60 (1999) 515–522.

DOI: 10.1016/s0925-5273(98)00171-6

[5] S.G. Ponnambalam, P. Aravindan, and S.V. Rajesh, A Tabu search algorithm for job shop scheduling, The International Journal of Advanced Manufacturing Technology. 16 (2000) 765-771.

DOI: 10.1007/s001700070030

[6] Jain, and S. Meeran, Job shop scheduling using neural networks, International Journal of Production Research, 36 (1998) 1249-1272.

DOI: 10.1080/002075498193309

[7] J.F. Goncalves, J.M. Mendes, and M.C.G. Resende, A hybrid genetic algorithm for the job shop scheduling problem, European Journal of Operational Research. 167 (2005) 77–95.

DOI: 10.1016/j.ejor.2004.03.012

[8] M. Gen and R. Cheng, Genetic algorithm and engineering design, John Wiley, New York, (1997).

[9] S.G. Ponnambalam, P. Aravindan, and S.V. Rajesh, A tabu search algorithm for job shop scheduling, Int J Adv Manuf Technol 16 (2000) 765–771.

DOI: 10.1007/s001700070030

[10] C. Bierwirth, D. Mattfeld, and H. Kopfer, In H. M. Voigt (Ed. ), On permutation representations for scheduling problems, (p.310–318). Proceedings of Parallel Problem Solving from Nature IV, Berlin, Germany: Springer, (1996).

DOI: 10.1007/3-540-61723-x_995

[11] M. Watanabe, K. Ida, M. Gen. A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem. Computers & Industrial Engineering 48 (2005) 743–752.

DOI: 10.1016/j.cie.2004.12.008

[12] B.J. Park, H.R. Choi, and H.S. Kim, A hybrid genetic algorithm for the job shop scheduling problems, Computers & Industrial Engineering, 45 (2003) 597–613.

DOI: 10.1016/s0360-8352(03)00077-9

[13] P. Fattahi, F. Jolai, and J. Arkat, Flexible job shop scheduling with overlapping in operations, Applied Mathematical modeling, 33 (2009) 3076-3087.

DOI: 10.1016/j.apm.2008.10.029

[14] D.T. Pham, and D. Karaboga, Intelligent optimization techniques: genetic algorithms, tabu search, simulated annealing and neural networks,. London: Springer 2000. Figure 10. Gant chart of the current solution after iteration 1 Figure 11. Gant chart of the current solution after iteration 2 Figure 12. Gant chart of the current solution after iteration 3.

DOI: 10.1002/rnc.986