APPLYING PARTICLE SWARM OPTIMIZATION FOR SOLVING A JOB SHOP SCHEDULING PROBLEM
Article Sidebar
Main Article Content
Abstract
The purpose of this research is to present a particle swarm optimization (PSO) to solve a single-objective job-shop scheduling problem with the objective of minimizing a makespan. The process of particle swarm optimization consists of 1) problem representation of a particle that is encoded with a permutation of all operations on jobs. The operations are ordered by precedence constraints. 2) Evaluating a quality of each particle by the fitness function. The fitness value is represented by a makespan of scheduling. And 3) Finding suitable scheduling by the process of particle swarm optimization. The performance of proposed methodology is tested on 48 well-known benchmark problems from OR-library. The computational results demonstrate that 1) the proposed methodology could be applied to solve a job shop scheduling problem and performs well on the 48 benchmark problems with relative error between 0.0284 and 0.4183. 2) a particle swarm optimization is highly effective in a job shop scheduling problem with small size and also take less processing time although run on a personal computer.
Article Details
"The opinions and contents including the words in papers are responsibility by the authors."
"ข้อคิดเห็น เนื้อหา รวมทั้งการใช้ภาษาในบทความถือเป็นความรับผิดชอบของผู้เขียน"
References
[2] Songwut Egwutvongsa. 2557. A Study and Development of Vehicle Versatile Support Mission Forest Fire for Prevention Suppress and Control Forest Fires Office, Department of National Parks Wildlife and Plant Conservation. Journal of Industrial Education, 1(6), p. 55-62.
[3] Khwanruthai Roungtham, Walailak Atthirawong, and Nuttawut Rojniruttikul. 2556. Delivery efficiency of just-in-time production system for automotive part suppliers case study : Siam Hi-Tech Steel Center Co., Ltd. Journal of Industrial Education, 3(16), p. 124-132.
[4] Özgüven, C., Özbakır, L. and Yavuz, Y. 2010. Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Applied Mathematical Modelling, 34(6), p. 1539-1548.
[5] Brucker, P., Jurisch, B. and Sievers, B. 1994. A branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics, 49, p. 107- 127.
[6] PAN, C.H. 1997. A study of integer programming formulations for scheduling problems. International Journal of Systems Science, 28(1), p. 33-41.
[7] Ponnambalam, S. G., Aravindan, P. and Rajesh, S.V. 2000. A Tabu Search Algorithm for Job Shop Scheduling. Advanced Manufacturing Technology, 16(10), p. 765-771.
[8] Qing-dao-er-jia, R. and Wang, Y. 2012. A new hybrid genetic algorithm for job shop scheduling problem. Computers & Operations Research, 39(10), p. 2291– 2299.
[9] Turguner, C. and Sahingoz, O.K. 2014. Solving Job Shop Scheduling Problem with Ant Colony Optimization. In Proceedings of the 15th IEEE International Symposium on Computational Intelligence and Informatics. 19-21 November, p. 385-389.
[10] Lui, Z. 2007. Investigation of Particle Swarm Optimization for Job Shop Scheduling Algorithm. In Proceedings of the 3rd IEEE International Conference on Natural Computation (ICNC2007).24-27 August, p. 799- 803.
[11] Bratton, D. and Kennedy, J. 2007. Defining a Standard for Particle Swarm Optimization. in Proceeding of the 2007 IEEE Swarm Intelligence Symposium (SIS2007). 1-5 April, p. 120-127.
[12] Zhou, Y. and Tan, Y. 2009. GPU-based Parallel Particle Swarm Optimization. 2009 IEEE Congress on Evolutionary Computation, CEC 2009. p. 1493 - 1500.
[13] Chowdhury, S., Tong, W. Messac, A. and Zhang, J. 2013. A mixed-discrete Particle Swarm Optimization algorithm with explicit diversity-preservation. Structural and Multidisciplinary Optimization, 47(3), p. 367–388.
[14] Beasley, J.E. 1990. OR-Library: Distributing Test Problems by Electronic Mail. Journal of the Operations Research Society, 41(11), p. 1069-1072.