A Novel Non-Decreasing Temperature Based Simulated Annealing for Flow Shop Problems

Abstract:

The permutation flow shop problem (PFSP) is an NP-hard permutation sequencing scheduling problem, many meta-heuristics based schemes have been proposed for finding near optimal solutions. A simple insertion simulated annealing (SISA) scheme consisting of two phases is proposed for solving PFSP. First, to reduce the complexity, a simple insertion local search is conducted for constructing the solution. Second, to ensure continuous exploration in the search space, two non-decreasing temperature control mechanisms named Heating SA and Steady SA are introduced in a simulated annealing (SA) procedure. The Heating SA increases the exploration search ability and the Steady SA enhances the exploitation search ability. The most important feature of SISA is its simple implementation and low computation time complexity. Experimental results are compared with other state-of-the-art algorithms and reveal that SISA is able to efficiently yield good permutation schedule.

• Periodical: Applied Mechanics and Materials (Volumes 764-765)
• Pages: 1390-1394
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.764-765.1390
• Online since: May 2015
• Authors: Ruey Maw Chen*, Frode Eika Sandnes
• Keywords: Permutation Flow Shop Problem (PFSP), Scheduling, Simple Insertion Simulated Annealing (SISA), Simulated Annealing (SA), Steady Sa

References

[1] X. Xu, Z.H. Xu, X.S. Gu: An asynchronous genetic local search algorithm for the permutation flowshop scheduling problem with total flowtime minimization, Expert Systems with Applications 38 (2011) 7970-7979.

DOI: 10.1016/j.eswa.2010.12.075

[2] S.H. Chen, P.C. Chang, T.C.E. Cheng, Q.F. Zhang: A Self-guided Genetic Algorithm for permutation flowshop scheduling problems, Computers & Operations Research 39 (2012) 1450-1457.

DOI: 10.1016/j.cor.2011.08.016

[3] N. Javadian, A. Mozdgir, E.G. Kouhi, D. Qajar, M.E. Shiraqai: Solving assembly flowshop scheduling problem with parallel machines using Variable Neighborhood Search, International Conference on Computers & Industrial Engineering (2009).

DOI: 10.1109/iccie.2009.5223845

[4] S. Liu, J.H. Cui, Y. Li: Heuristic-Tabu Algorithm for Hybrid Flowshop Scheduling with Limited Waiting Time, International Symposium on Computational Intelligence and Design, ISCID '08.

DOI: 10.1109/iscid.2008.161

[5] F. Ahmadizar: A new ant colony algorithm for makespan minimization in permutation flow shops, Computers and Industrial Engineering 63 (2012) 355-361.

DOI: 10.1016/j.cie.2012.03.015

[6] X. Wang, L. Tang: A discrete particle swarm optimization algorithm with self-adaptive diversity control for the permutation flowshop problem with blocking, Applied Soft Computing 12 (2012) 652–662.

DOI: 10.1016/j.asoc.2011.09.021

[7] R. Ruiz, T. Stützle: A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research 177 (2007) 2033-(2049).

DOI: 10.1016/j.ejor.2005.12.009

[8] S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi: Optimization by Simulated Annealing, Science 220 (1983) 671 – 680.

DOI: 10.1126/science.220.4598.671

[9] R.M. Chen, F.R. Hsieh: An Exchange Local Search Heuristic Based Scheme for Permutation Flow Shop Problems, Applied Mathematics & Information Sciences 8 (2014) 209-215.

DOI: 10.12785/amis/081l26