CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Integrating Genetic Algorithm, Tabu Search and Simulated Annealing For Job Shop Scheduling Proble

by R. Thamilselvan, P. Balasubramanie
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 48 - Number 5
Year of Publication: 2012
Authors: R. Thamilselvan, P. Balasubramanie
10.5120/7348-0283

R. Thamilselvan, P. Balasubramanie . Integrating Genetic Algorithm, Tabu Search and Simulated Annealing For Job Shop Scheduling Proble. International Journal of Computer Applications. 48, 5 ( June 2012), 42-54. DOI=10.5120/7348-0283

@article{ 10.5120/7348-0283,
author = { R. Thamilselvan, P. Balasubramanie },
title = { Integrating Genetic Algorithm, Tabu Search and Simulated Annealing For Job Shop Scheduling Proble },
journal = { International Journal of Computer Applications },
issue_date = { June 2012 },
volume = { 48 },
number = { 5 },
month = { June },
year = { 2012 },
issn = { 0975-8887 },
pages = { 42-54 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume48/number5/7348-0283/ },
doi = { 10.5120/7348-0283 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:43:20.945815+05:30
%A R. Thamilselvan
%A P. Balasubramanie
%T Integrating Genetic Algorithm, Tabu Search and Simulated Annealing For Job Shop Scheduling Proble
%J International Journal of Computer Applications
%@ 0975-8887
%V 48
%N 5
%P 42-54
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Job Shop Scheduling Problem (JSSP) is an optimization problem in which ideal jobs are assigned to resources at particular times. In recent years many attempts have been made at the solution of JSSP using a various range of tools and techniques such as Branch and Bound and Heuristics algorithms. This paper proposed a new algorithm based on Genetic Algorithm (GA), Tabu Search (TS) and Simulated Annealing (SA) algorithms to solve JSSP. The proposed algorithm is mainly based on the genetic algorithm. The reproduction phase of the genetic algorithm uses the tabu search to generate new population. Simulated annealing algorithm is used to speed up the genetic algorithm to get the solution by applying the simulated annealing test for all the population members. The proposed algorithm used many small but important features such as chromosome representation, effective genetic operators, and restricted neighbourhood strategies. The above features are used in the hybrid algorithm to solve several bench mark problems.

References
  1. Garey. E. L, Johnson. D. S and Sethi. R, "The complexity of flow shop and job shop scheduling", Mathematics of Operations Research, Vol. 1, pp. 117-129, 1976.
  2. Brucker. P, Jurisch. B and Sievers. B, "A branch and bound algorithm for job shop scheduling problem", Discrete Applied Math, Vol. 49, pp. 105-127, 1994.
  3. Artigues. C, Feillet. D, "A branch and bound method for the job shop problem with sequence dependent setup times", Annals of Operations Research, Vol. 159, No. 1, pp. 135-159, 2008.
  4. Lorigeon. T, "A dynamic programming algorithm for scheduling jobs in a two-machine open shop with an availability constraint", Journal of the Operational Research Society, Vol. 53, No. 11, pp. 1239-1246, 2002.
  5. Potts. C. N and Van Wassonhove. L. N, "Dynamic programming and decomposition approaches for the single machine total tardiness problem", European Journal of Operational Research, Vol. 32, pp, 405-414, 1987.
  6. Zhang. C. Y, Li. P. G, Rao. Y. Q, "A very fast TS/SA algorithm for the job shop scheduling problem", Computers and Operations Research, Vol. 35, pp. 282-294, 2008.
  7. Nowicki. E andSmutnicki. C, "A fast taboo search algorithm for the job shop scheduling problem", Management Science, Vol. 41, No. 6, pp. 113-125, 1996.
  8. Dell. A. M, Trubian. M, "Applying tabu-search to job shop scheduling problem," Annals of Operations Research, Vol. 41, No. 3, pp. 231-252, 1993.
  9. Wang. T. Y, Wu. K. B, "A revised simulated annealing algorithm for obtaining the minimum total tardiness in job shop scheduling problems", International Journal of Systems Science, vol. 31, no. 4, pp. 537-542, 2000.
  10. Kolonko. M, "Some new results on simulated annealing applied to the job shop scheduling problem", European Journal of Operational Research, vol. 113, no. 1, pp. 123-136, 1999.
  11. Moon. I, Lee. S and Bae. H, "Genetic algorithms for job shop scheduling problems with alternative routings", International Journal of Production Research, Vol. 46, No. 10, pp. 2695-2705, 2008.
  12. Goncalves. J. F, Mendes. J. J. D. M and, Resende. M. G. C, "A hybrid genetic algorithm for the job shop scheduling problem", European Journal of Operational Research, Vol. 167, No. 1, pp. 77-95, 2005.
  13. Bierwirth. C and Mattfeld. D. C, "Production scheduling and rescheduling with genetic algorithms", Evolutionary Computation, Vol. 7, No. 1, pp. 1-17, 1999.
  14. Liu. B, Wang. L and Jin. Y. H, "An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers", Computers and Operations Research, Vol. 35, No. 9, pp. 2791-2806, 2008.
  15. Tasgetiren. M. F, Liang. Y. C and Sevkli. M, "A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem", European Journal of Operational Research, Vol. 177, No. 3, pp. 1930-1947, 2007.
  16. Holland. J. H, Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan Press, 1975.
  17. Goldberg. G. E. Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley, 1989.
  18. Glover. F , "Future paths for integer programming and links to artificial intelligence", Computer and Operation Research, Vol. 13, No. 5, pp. 533-549, 1986.
  19. Glover. F , Tabu Search – Part I, ORSA Journal on Computing, Vol. 1, No. 3, pp. 190-206, 1989.
  20. Glover. F , Tabu Search – Part II, ORSA Journal on Computing, Vol. 2, No. 3, pp. 4-32, 1990.
  21. Brucker. P, Scheduling Algorithms, Springer Verlag, Berlin, 1995
  22. Davis, L. Job-shop scheduling with genetic algorithm. In Proceedings of the 1st international conference on genetic algorithms and their applications, Pittsburgh, PA, pp. 136–140, 1985.
  23. Della Croce. F. , Tadei. R. , andVolta. G. A genetic algorithm for the job shop problem. Computers and Operations Research, Vol. 22, No. 1,pp. 15–24, 1995.
  24. Dorndorf. U. , and Pesch. E. Evolution based learning in a job-shop scheduling environment. Computers and Operations Research, Vol. 22, No. 1, pp. 25–40, 1995.
  25. Eswarmurthy. V. , and Tamilarasi. A. Hybridizing tabu search with ant colony optimization for solving job shop scheduling problem. The International Journal of Advanced Manufacturing Technology, Vol. 40, pp. 1004–1015, 2009.
  26. Mattfeld. D. C. Evolutionary search and the job shop: Investigations on genetic algorithms for production scheduling. Heidelberg, Germany: Physica-Verlag, 1996.
  27. Yamada. T. and Nakano. R. Scheduling by genetic local search with multi-step crossover. In PPSN'IV 4th international conference on parallel problem solving from nature, Berlin, Germany, pp. 960-969, 1996.
  28. Park. B. J. , Choi, H. R. , and Kim. H. S. A hybrid genetic algorithm for the job shop scheduling problems. Computers and Industrial Engineering, Vol. 45, pp. 597–613, 2003
  29. Aydin. M. E. , and Fogarty. T. C. A simulated annealing algorithm for multi-agent systems: A job-shop scheduling application. Journal of Intelligent Manufacturing, Vol. 15, No. 6, pp. 805–814, 2004.
  30. Gao. J. , Gen. M. , and Sun. L. Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm. Journal of Intelligent Manufacturing, Vol. 17, No. 4, pp. 493–507, 2006.
  31. Pezzella. F. , and Merelli. E. A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operation Research, Vol. 120, pp. 297–310, 2000.
  32. Pezzella. F. , Morganti. G. , and Ciaschetti. G. A genetic algorithm for the flexible job-shop scheduling problem. Computers and Operations Research, Vol. 35, pp. 3202–3212, 2008.
  33. Gholami. M. and Zandieh. M. Integrating simulation and genetic algorithm to schedule a dynamic flexible job shop. Journal of Intelligent Manufacturing, Vol. 20, No. 4, pp. 481–498, 2009.
  34. Gen. M. , Gao. J. , and Lin. L. Multistage-based genetic algorithm for flexible job-shop scheduling problem. Intelligent and Evolutionary Systems, Studies in Computational Intelligence, Vo. 187, pp. 183–196, 2009.
  35. Pérez. E. , Posada. M. , and Herrera. F. Analysis of new niching genetic algorithms for finding multiple solutions in the job shop scheduling. Journal of Intelligent Manufacturing, Online Firsttrademark, March 10, 2010.
  36. Dell'Amico. M. , and Trubian, M. Applying tabu search to the job-shop scheduling problem. Annals of Operations Research, Vol. 41, pp. 231–252, 1993.
  37. Thomsen. S. Meta-heuristics combined with branch and bound. Technical Report. Copenhagen Business School, Copenhagen, Denmark, 1997.
  38. Chen. L. , Bostel. N. , Dejax, P. , Cai. J. , and xi. L. A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal. European Journal of Operational Research, Vol. 181, No. 1, pp. 40–58, 2007.
  39. Yamada, T. and Nakano, R. Scheduling by genetic local search with multi-step crossover. In PPSN'IV 4th international conference on parallel problem solving from nature, Berlin, Germany, pp. 960–969, 1996
  40. Zhou, R. , Nee, A. Y. C. , and Lee, H. P. Performance of an ant colony optimisation algorithm in dynamic job shop scheduling problems. International Journal of Production Research, Vol. 47, pp. 2903–2920, 2009.
  41. Jain, A. S. , andMeeran, S. A multi-level hybrid framework applied to the general flow-shop scheduling problem. Computers and Operations Research, Vol. 29, pp. 1873–1901, 2002.
  42. Satake, T. , Morikawa, K. , Takahashi, K. , and Nakamura, N. Simulated annealing approach for minimizing the make-span of the general job shop. International Journal of Production Economics, Vol. 60, No. 61, pp. 515–522, 1999.
  43. Suresh, R. K. , andMohanasundaram, K. M. Pareto archived simulated annealing for job shop scheduling with multiple objectives. The International Journal of Advanced Manufacturing Technology, Vol. 29, pp. 184–196, 2005.
  44. Guohui Zhang, Liang Gao and Yang Shi, "A Genetic Algorithm and Tabu Search for Multi Objective Flexible Job Shop Scheduling Problems", International Conference on Computing, Control and Industrial Engineering, 2010.
  45. Wang. L. , and Zheng, D. Z. An effective hybrid optimisation strategy for job shop scheduling problems. Computers and Operations Research, Vol. 28, pp. 585–596, 2001.
  46. Meeran. S. andMorshed. M. S. A hybrid configuration for solving job shop scheduling problems. In 8th Asia Pacific industrial engineering and mangement science Conference, Kaohsiung, Taiwan, 2007.
  47. González, M. A. , Vela, C. R. , and Varela, R. Genetic algorithm combined with tabu search for the job shop scheduling problem with setup times' methods and models in artificial and natural computation. A homage to professor Mira's scientific legacy. Lecture Notes in Computer Science, 5601/2009, pp. 265–274, 2009. doi:10. 1007/978-3-642-02264-7_28.
  48. Thamilselvan, R, P. Balasubramanie, Analysis of Various Alternate Crossover Strategies for Genetic Algorithm to Solve Job Shop Scheduling. European Journal of Scientific Research, 64(4): 538-554, 2011. www. europeanjournalofscientificresearch. com /ISSUES/EJSR_64_4_05. pdf.
  49. Thamilselvan, R, P. Balasubramanie, Integration of Genetic Algorithm with Tabu Search for Job Shop Scheduling with Unordered Subsequence Exchange Crossover. Journal of Computer Science, 8(5): 681-693. DOI: 10. 3844/jcssp. 2012. 681. 693, 2012
Index Terms

Computer Science
Information Sciences

Keywords

Simulated Annealing Tabu Search Genetic Algorithm And Job Shop Scheduling

Powered by PhDFocusTM