Using Improved Particle Swarm Optimization to Solve Open Shop Scheduling Problem with Two Criteria

Abstract:

The shop-scheduling problem can be simply introduced as a problem of redistribution of resources or a problem of rearrangement of operation orders. Open shop scheduling problems (OSSP) are one of the most time-consuming works in scheduling problems. In other hand Optimization techniques have obtained much attention during the past decades. Particle Swarm Optimization (PSO) and Genetic Algorithm (GA) are the most important methods used to solve optimization problems such as Open Shop Scheduling. In this paper, a hybrid optimization algorithm (IPSO) is proposed to solve Open Shop Scheduling more efficiently and accurately. Most literature referring to OSSP focuses on the optimization of one single objective.This paper offered a mathematic model for OSSP with the goal of minimizing average completion time and the number of late jobs simultaneously. The proposed method was then compared whit the results of the LINGO software and GA. The results of this comparison show that IPSO can achieve better results for the solution in a faster time. Introduction

• Periodical: Advanced Materials Research (Volumes 433-440)
• Pages: 4936-4941
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.433-440.4936
• Online since: January 2012
• Authors: Mohammad Reza Kabarazad Ghadim, Behnam Bahrami, Arash Bayat
• Keywords: GA, IPSO, Open Shop Scheduling, Optimization Method

References

[1] D. Y. Shaa, H. Cheng-Yu : A new particle swarm optimization for the open shop scheduling problem, Computers & Operations Research Volume 35, Issue 10, (2008), Pages 3243-3261.

DOI: 10.1016/j.cor.2007.02.019

[2] C. Guéret , C. Prins: Classical and new heuristics for the open-shop problem a computational evaluation, European Journal of Operational Research 107 (2) (1998).

DOI: 10.1016/s0377-2217(97)00332-9

[3] U. Dorndorf, E. Pesch and T. Phan-Huy : Solving the open-shop scheduling problem, Journal of Scheduling, (2001), p.157–174.

DOI: 10.1002/jos.73

[4] L. Chinyao, Y. Yuling: Genetic algorithm-based heuristics for an open shop scheduling problem with setup, processing, and removal times separated, Robotics and Computer-Integrated Manufacturing Volume 25, Issue 2, (2009), Pages 314-322.

DOI: 10.1016/j.rcim.2007.07.017

[5] E. Cheng, T. C. Shakhlevich, V. Natalia : Minimizing non-decreasing separable objective functions for the unit- time open shop scheduling problem, European Journal of Operational Research Volume 165, Issue 2, (2005), Pages 444-456.

DOI: 10.1016/j.ejor.2004.04.014

[6] H. Panahi, R. Tavakkoli-Moghaddam : Solving a multi-objective open shop scheduling problem by a novel hybrid ant colony optimization, Expert Systems with Applications Volume 38, Issue 3, (2011), Pages 2817-2822.

DOI: 10.1016/j.eswa.2010.08.073

[7] A. Ghodratnamaa, M. Rabbani, R. Tavakkoli-Moghaddama , A. Baboli: Solving a single-machine scheduling problem with maintenance, job deterioration and learning effect by simulated annealing , "Journal of Manufacturing Systems Volume 29, Issue 1, (2010).

DOI: 10.1016/j.jmsy.2010.06.004

[8] L. Jun-qing, b. Quan-ke Pana and Liang. Yun-Chia : An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems , Computers & Industrial Engineering Volume 59, Issue 4, Pages 647-662 (2010).

DOI: 10.1016/j.cie.2010.07.014

[9] M. Matta : A genetic algorithm for the proportionate multiprocessor open shop, Computers & Operations Research Volume 36, Issue 9, ( 2009), Pages 2601-2618.

DOI: 10.1016/j.cor.2008.11.009

[10] C. Blum : Beam-ACO—hybridizing ant colony optimization with beam search, an application to open shop scheduling, Computers & Operations Research 32 (2005).

DOI: 10.1016/j.cor.2003.11.018

[11] P. Kennedy and R. Eberhart: Particle Swarm Optimization in Proceedings of IEEE international Conferarance 011 Neural Networks (ICNN'95), Vol. 1, Piscatawa: NJ, (1995), p.1942-(1948).

DOI: 10.1109/icnn.1995.488968

[12] M. Salazar-Lechuga and J. E. Rowe : Particle Swarm Optimization and Fitness Sharing to solve Multi-ObjectiveOptimization Problems, IEEE (2005), pp.1204-1211.

DOI: 10.1109/cec.2005.1554827

[13] M.V.F. Pereira and L.M.V.G. Pintoand : A New Computational Tool for Composite Reliability Evaluation, IEEE Trans. Power Sytems, vol. 7, no. 1, Feb (1992), pp.258-264.