A Hybrid Particle Swarm Optimization and Simulate Annealing (PSO-SA) Algorithm for Scheduling a Flowshop Manufacturing

cell with Sequence Dependent Setup Times

In cellular manufacturing systems, minimization of the completion time has a great impact on production

time, material flow, and productivity. An effective scheduling is crucial to attaining the

advantages of cellular manufacturing systems.

In this paper, a Hybrid Particle Swarm Optimization (PSO-SA) algorithm is proposed to solve a

cellular flowshop scheduling problem with family sequence-dependent setup time. The proposed

PSO-SA algorithm combines Particle Swarm Optimization (PSO) algorithm with Simulated Annealing

(SA) as a local search to balance between diversification and intensification. The objective

is to find the best sequence of families as well as jobs in each family in order to minimize total

flow time; the problem is classified as: Fm n f mls;Selki; prumn?Nj=1Cj.

The research problem is shown to be an NP-hard problem. PSO-SA is developed to improve the

effectiveness of the PSO algorithm and to reduce the average variation from the lower bounds.

The performance the proposed PSO-SA is evaluated based on the Relative Percentage Deviation

(RPD) from lower bounds and compared with the best available algorithm.

A Hybrid Particle Swarm Optimization and Simulate Annealing

(PSO-SA) Algorithm for Scheduling a Flowshop Manufacturing

cell with Sequence Dependent Setup Times

Results showed that the hybridization of the PSO with SA improves the quality of the PSO algorithm

and reduces the gap from the lower bounds especially for large problems.

[1] J. S. Neufeld, J. N. D. Gupta, and U. Buscher, “A comprehensive review of flowshop group

scheduling literature,” Computers and Operations Research, vol. 70, pp. 56–74, 2016.

[2] F. Zhao, J. Tang, and J. Wang, “An improved particle swarm optimization with decline disturbance

index (DDPSO) for multi-objective job-shop scheduling problem,” Comput. Oper.

Res., vol. 45, pp. 38–50, may 2014.

[3] M. Zandieh, B. Dorri, and a. R. Khamseh, “Robust metaheuristics for group scheduling with

sequence-dependent setup times in hybrid flexible flow shops,” Int. J. Adv. Manuf. Technol.,

vol. 43, no. 7-8, pp. 767–778, sep 2008.

[4] M. Pinedo, Scheduling: theory, algorithms, and systems. Springer, 2012.

[5] S. Lin, K. Ying, and Z. Lee, “Metaheuristics for scheduling a non-permutation flowline manufacturing

cell with sequence dependent family setup times,” Comput. Oper. Res., vol. 36,

no. 4, pp. 1110–1121, apr 2009.

[6] L.-Y. Tseng and Y.-T. Lin, “A genetic local search algorithm for minimizing total flowtime

in the permutation flowshop scheduling problem,” Int. J. Prod. Econ., vol. 127, no. 1, pp.

121–128, sep 2010.

[7] J. Schaller, J. N. D. Gupta, and A. J. Vakharia, “Scheduling a flowline manufacturing cell with

sequence dependent family setup times,” Eur. J. Oper. Res., vol. 125, no. 2, pp. 324–339, sep 2000.

[8] P. Franca, J. Gupta, A. Mendes, P. Moscato, and K. Veltink, “Evolutionary algorithms for

scheduling a flowshop manufacturing cell with sequence dependent family setups,” Comput.

Ind. Eng., vol. 48(3), pp. 491–506, 2005.

[9] S. Hamed Hendizadeh, H. Faramarzi, S. Mansouri, J. N. Gupta, and T. Y ElMekkawy, “Metaheuristics

for scheduling a flowline manufacturing cell with sequence dependent family setup

times,” Int. J. Prod. Econ., vol. 111, no. 2, pp. 593–605, feb 2008.

[10] S.-W. Lin, J. N. Gupta, K.-C. Ying, and Z.-J. Lee, “Using simulated annealing to schedule a

flowshop manufacturing cell with sequence-dependent family setup times,” Int. J. Prod. Res.,

vol. 47, no. 12, pp. 3205–3217, jun 2009.

[11] N. Salmasi, R. Logendran, and M. R. Skandari, “Makespan minimization of a flowshop

sequence-dependent group scheduling problem,” Int. J. Adv. Manuf. Technol., feb 2011.

[12] R. Bouabda, B. Jarboui, M. Eddaly, and A. Rebai, “A branch and bound enhanced genetic

algorithm for scheduling a flowline manufacturing cell with sequence dependent family setup

times,” Comput. Oper. Res., vol. 38, no. 1, pp. 387–393, 2011.

[13] M. Eddaly, B. Jarboui, R. Bouabda, and A. Rebai, “Hybrid Estimation of distribution algorithm

for permutation flowshop scheduling with dependent family setup times,” in 2009 Int.

Conf. Comput. Ind. Eng., 2009, pp. 217–220.

[14] S. Hamed Hendizadeh, H. Faramarzi, S. Mansouri, J. N. Gupta, and T. Y ElMekkawy, “Metaheuristics

for scheduling a flowline manufacturing cell with sequence dependent family setup

times,” International Journal of Production Economics, vol. 111(2), pp. 593–605, 2008.

[15] N. Salmasi, R. Logendran, and M. R. Skandari, “Total flow time minimization in a flowshop

sequence-dependent group scheduling problem,” Computers & Operations Research, vol. 37,

no. 1, pp. 199–212, jan 2010.

[16] B. Naderi and N. Salmasi, “Permutation flowshops in group scheduling with sequence- dependent

setup times,” Eur. J. Ind. Eng., vol. 6, no. 2, pp. 177–198, 2012.

[17] J. Kennedy and R. Eberhart, “Particle swarm optimization,” Proc. ICNN’95 - Int. Conf. Neural

Networks, vol. 4, pp. 1942–1948, 1995.

[18] R. Poli, J. Kennedy, and T. Blackwell, “Particle swarm optimization,” Swarm Intell., vol. 1,

no. 1, pp. 33–57, aug 2007.

[19] B. Liu, L. Wang, and Y.-H. Jin, “An effective PSO-based memetic algorithm for flow shop

scheduling.” IEEE Trans. Syst. Man. Cybern. B. Cybern., vol. 37, no. 1, pp. 18–27, mar 2007.

[20] Z. Lian, X. Gu, and B. Jiao, “A novel particle swarm optimization algorithm for permutation

flow-shop scheduling to minimize makespan,” Chaos, Solitons & Fractals, vol. 35, no. 5, pp.

851–861, mar 2008.

[21] C.-T. Tseng and C.-J. Liao, “A particle swarm optimization algorithm for hybrid flow-shop

scheduling with multiprocessor tasks,” Int. J. Prod. Res., vol. 46, no. 17, pp. 4655–4670, sep 2008.

[22] I.-H. Kuo, S.-J. Horng, T.-W. Kao, T.-L. Lin, C.-L. Lee, T. Terano, and Y. Pan, “An efficient

flow-shop scheduling algorithm based on a hybrid particle swarm optimization model,”

Expert Syst. Appl., vol. 36, no. 3, pp. 7027–7032, apr 2009.

[23] K. Rameshkumar, R. Suresh, and K. Mohanasundaram, “Discrete particle swarm optimization

(DPSO) algorithm for permutation flowshop scheduling to minimize makespan,” Adv.

Nat. Comput., pp. 572–581, 2005.

[24] T.-L. Lin, S.-J. Horng, T.-W. Kao, Y.-H. Chen, R.-S. Run, R.-J. Chen, J.-L. Lai, and I.-H.

Kuo, “An efficient job-shop scheduling algorithm based on particle swarm optimization,”

Expert Syst. Appl., vol. 37, no. 3, pp. 2629–2636, mar 2010.

[25] H. Liu, L. Gao, and Q. Pan, “A hybrid particle swarm optimization with estimation of distribution

algorithm for solving permutation flowshop scheduling problem,” Expert Syst. Appl.,

vol. 38, no. 4, pp. 4348–4360, apr 2011.

[26] S. Gohari and N. Salmasi, “Flexible flowline scheduling problem with constraints for the beginning

and terminating time of processing of jobs at stages,” Int. J. Comput. Integr. Manuf.,

pp. 1–14, 2014.

[27] B. Liu, L. Wang, and Y.-H. Jin, “An effective hybrid PSO-based algorithm for flow shop

scheduling with limited buffers,” Comput. Oper. Res., vol. 35, no. 9, pp. 2791–2806, sep

2008.

[28] E.-G. Talbi, Hybrid Metaheuristics, ser. Studies in Computational Intelligence, E.-G. Talbi,

Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013, vol. 434.

[29] S. Kirkpatrick, C. Gelatt, and M. Vecchi, “Optimization by simmulated annealing,” Science,

pp. 671–680, 1983.

[30] S. Ledesma, G. Avi?a, and R. Sanchez, “Practical considerations for simulated annealing

implementation,” Simulated Annealing, no. February, pp. 401–420, 2008.

[31] R. W. Eglese, “Simulated annealing: a tool for operational research,” Eur. J. Oper. Res.,

vol. 46, pp. 271–281, 1990.

[32] R. Rutenbar, “Simulated annealing algorithms: An overview,” Circuits Devices Mag. IEEE,

no. x, 1989.

[33] F. Busetti, “Simulated annealing overview,” World Wide Web URL www. geocities. com/

DOI10.1.1.66.5018, 2003.

[34] A. J. Vakharia and Y.-L. Chang, “A simulated annealing approach to scheduling a manufacturing

cell,” Nav. Res. Logist., vol. 37, no. 4, pp. 559–577, aug 1990.

[35] J. Sridhar and C. Rajendran, “Scheduling in a cellular manufacturing system: a simulated

annealing approach,” Int. J. Prod. Res., vol. 31, no. 12, pp. 2927–2945, dec 1993.

[36] A.-m. Ibrahem, T. Elmekkawy, and Q. Peng, “Robust Metaheuristics for Scheduling Cellular

Flowshop with Family Sequence- Dependent Setup Times,” Procedia CIRP, vol. 17C, pp.

428–433, 2014.