Saturday , April 20 2024

A Hybrid Algorithm for Job Shop Scheduling Problem

Florentina Alina TOADER
Petroleum Gas University of Ploiesti,
39 Bucuresti Blvd , Ploiesti, 100680, Romania
toader_florentina_alina@yahoo.com

Abstract: The Job Shop Scheduling Problem (JSSP) is regarded as one of the most challenging issues by the research community in this field due to its complexity. This paper presents a hybrid algorithm called H-PSO-SA for JSSP which is a mixture of two computational artificial intelligence algorithms: Particle Swarm Optimization and Simulated Annealing. In order to demonstrate efficiency of the proposed hybrid algorithm, a series of tests are conducted using a set of classical JSSP benchmarks. The schedule results are compared with outcomes well known in the scientific literature.

Keywords: Production Scheduling, Job Shop Scheduling Problem, Simulated Annealing, Particle Swarm Optimization

>Full text
CITE THIS PAPER AS:
Florentina Alina TOADER, A Hybrid Algorithm for Job Shop Scheduling Problem, Studies in Informatics and Control, ISSN 1220-1766, vol. 24 (2), pp. 171-180, 2015. https://doi.org/10.24846/v24i2y201505

  1. Introduction

The Job Shop Scheduling Problem (JSSP) represents one of the most difficult to solve problems in the industrial environment. This type of problem is categorized as NP-hard by Srinivas and Allada in 2004 [1]. Mesghouni et all mentioned in [2] that the complexity of this type of problem comes from the fact that consists of satisfying multiple goals. A set of resources needs to be allocated in a manner that satisfy the proposed goals, maximize the machine utilization and minimizes both the makespan and the total completion time of the entire process schedule.

The solution proposed most recently in the specific literature refers to the hybrid methods applied in this field that manages to combine the advantages of a local search technique (e.g. swarm intelligence which is based on collective intelligence models inspired by nature such as Ant Colony Optimization – ACO, Particle Swarm Optimization – PSO, Artificial Bee Colony –ABC, Wasp Behaviour Model – WBM, etc.) with the advantages of the global search techniques ( Simulated Annealing – SA, Tabu Search – TS, etc.).

This paper proposes a hybrid algorithm resulted by combining an artificial intelligence technique, Particle Swarm Optimization with a very popular metaheuristic, Simulated Annealing.

The goal of this research work is to identify an optimal solution for the JSSP by combining the strengths and minimizing the influence of each algorithm weak points.

REFERENCES

  1. SRINIVAS, M. K. T., V. ALLADA, Solving the Machine Loading Problem in a Flexible Manufacturing System using a Combinatorial Auction-based Approach, International Journal of Production Research, vol. 42, no. 9, 2004, pp. 1879-1893.
  2. MESGHOUNI, K., S. HAMMADI, P. BONE, Evolutionary Algorithms for Job Shop Scheduling, International Journal of Applied Mathematics and Computer Science, Vol. 14, No.1, 2004, pp. 91-103.
  3. HOLLAND, J. H., Adaptation in Natural and Artificial Systems, MIT Press, Cambridge, 1992
  4. SHA, D. Y., H. H. LIN, A multi-objective PSO for Job Shop Scheduling Problems, Expert Systems with Applications, Vol. 37, Issue 2, 2010, pp. 1065-1070.
  5. SHA, D. Y., C. Y. HSU, A Hybrid Particle Swarm Optimization Approach for the Job Shop Scheduling Problem, Computer and Industrial Engineering, 51, Issue 4, 2006, pp. 791-808.
  6. LI, J., Q. PAN, S. XIE, S. WANG, A Hybrid Artificial Bee Colony Algorithm for Flexible Job Shop Scheduling Problem, International Journal of Computers, Communications & Control, Vol. IV, No. 2, 2011, pp. 286-296.
  7. ESWARAMURTHY, V. P., A. TAMILARASI, Hybridizing Tabu Search with Ant Colony Optimization for Solving Job Shop Scheduling Problems, International Journal of Advanced Manufacturing Technology, Vol.40, Issue 9-10, 2010, pp. 1004-1015.
  8. BOZEJKO, W., J. PEMPERA, C. SMUNTNICKI, Parallel Simulated Annealing for the Job Shop Scheduling Problem, Lecture notes in computer science, Proceedings of the 9th International Conference on Computational Science, Vol. 5544, 2009, pp. 631-640.
  9. GE, H., W. DU, F. QIAN, A Hybrid Algorithm Based on Particle Swarm Optimization and Simulated Annealing for Job shop Scheduling, Proceedings of the Third International Conference on Natural Computation, Vol. 3, 2007, pp. 715-719.
  1. SHEN, J., F. YANO, T. SHOHDOHJI, Y. TOYODA, An Approach to Multi-objective Job Shop Scheduling using Hybrid Particle Swarm Optimization, Proceedings of the 38th International Conference on Computers and Industrial Engineering, Beijing, Republic of China, 2008, pp. 1836-1843.
  2. TOADER, F. A., Production Scheduling Using ACO and PSO Techniques, Proceedings of the International Conference on Development and Applied Systems, 2014, pp. 170-175.
  3. TAMILARASI, A., T. ANANTHA KUMAR, An Enhanced Genetic Algorithm with Simulated Annealing for Job Shop Scheduling, International Journal of Engineering, Science and Technology, Vol. 2, No. 1, 2010, pp. 144-151.
  4. SAWIK, T., Production Planning Scheduling in Flexible Assembly Systems, Springer, 1999
  5. PONGCHAIRERKS, P., V. KACHITVICHYANUKUL, A Particle Swarm Optimization Algorithm on Job Shop Scheduling Problem with Multi-Purpose Machine, Asia-Pacific Journal of Operational Research, Vol. 2, Issue 2, 2009, pp.161-184.
  6. ZOBOLAS, C. I., C. D. TRANTILIS, G. IOANNOU, A Hybrid Evolutionary Algorithm for the Job Shop Scheduling Problem, Journal of the Operational Research Society, Vol. 60, No. 2, 2009, pp. 221-235.
  7. ZHANG, R., WU, C., A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective, Computers & Operations Research, Vol. 38, No. 5, 2011, pp. 854-867.
  8. ZHANG, R., S. SONG, C. WU, A Two-stage Hybrid Particle Swarm Optimization Algorithm for the Stochastic Job Shop Scheduling Problem, Knowledge Based Systems, Vol. 27, 2012, pp. 393-206
  9. ZHU, Z. C., K. M. NG, H. L. ONG, A Modified Tabu Search Algorithm for Cost-based Job Shop Problem, Journal of the Operational Research Society, Vol. 61, No. 4, 2010, pp. 611-619.
  10. MICHALEWICZ, Z, D. B. FOGEL, How to Solve It: Modern Heuristics,   Springer, 2004.
  11. VAN LAARHOVEN, P. J., E. H. AARTS, Simulated Annealing: Theory and Application, Kluwer Academic Publishing, 1992.
  12. BONABEAU, E., M. DORIGO, T. THERAULAZ, From Natural to Artificial Swarm Intelligence, Oxford University Press, New York, 1999.
  13. JAMILI, A., M. A. SHAFIA, R. TAVAKKOLI-MOGHADDAM, A Hybrid Algorithm based on Particle Swarm Optimization and Simulated Annealing for Periodic Job Shop Scheduling Problem, The International Journal of Advanced Manufacturing Technology, ISSN 0268-3768, vol. 54 (1-4), 2010,     pp. 309-322.
  14. BOUKEF, H., M. BENREJEB, P. BORNE, Flexible Job-shop Scheduling Problems Resolution Inspired from Particle Swarm Optimization, Studies in Informatics and Control, ISSN 1220-1766, vol. 17 (3), 2008, pp. 241-252.
  15. SONG, X., Y. CAO, C. CHANG, A Hybrid Algorithm of PSO and SA for Solving JSP, Proceedings of the Fifth International Conference on Fuzzy Systems and Knowledge Discovery, ISBN 978-0-7695-3305-6, vol. 1, pp. 111-115.
  16. SONG, C. L., X. B. LIU, W. WANG, B. XIN, A Hybrid Particle Swarm Optimization Algorithm for Job Shop Scheduling Problem, International Journal of Advancements in Computing Technology, vol. 3 (4), pp. 79-88.
  17. WEIJUN, X., W. ZHIMING, Y. GENKE, A New Hybrid Optimization Algorithm for the Job Shop Scheduling Problem, Proceedings of the 2004 American Control Conference, ISBN 0-7803-8335-4, vol. 6, p. 5552-5557.
  18. ADAMS, J., E. BALAS, D. ZAWACK, The Shifting Bottleneck Procedure for Job Shop Scheduling, Management Science vol. 34 (3), 1988, pp. 391-401.
  19. FISHER, H., G. L. THOMPSON, Probabilistic Learning Combinations of Local Job-shop Scheduling Rules, F. Muth, G. L. Thompson (eds.), Industrial Scheduling, Prentice Hall, Englewood Cliffs, New Jersey, 1963, pp. 225-251.
  20. LAWRENCE, , Resource Constrained Project Scheduling: an Experimental Investigation of Heuristic Scheduling Techniques (Supplement), Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania, 1984
  21. APPLEGATE, D., W. COOK, A Computational Study of the Job-shop Scheduling Instance, ORSA Journal on Computing, vol. 3, 1991, pp. 149-156.
  22. Online document. CSP2SAT: JSS benchmark results, http://bach.istc.kobe-u.ac.jp/csp2sat/jss/, cited at 18.02.2015.
  23. NICOARA, E. S., F. G. FILIP, N. PARASCHIV, Simulation-based Optimization using Genetic Algorithms for multi-objective Flexible JSSP, Studies in Informatics and Control, ISSN 1220-1766, vol. 20 (4), 2011, pp. 333-344.
Designed by | ICI Bucharest
© Copyright 2024, All Rights Reserved