Flow Shop Scheduling Based on A Novel Cooling Temperature Driven Simulated Annealing Algorithm

Authors

1 Dept. Of Computer Science and Information Engineering, National Chin-Yi University of Technology No.57, Sec. 2, Zhongshan Rd., Taiping Dist., Taichung 41170, Taiwan, R.O.C.

2 Oslo and Akershus University College of Applied Sciences, P.O. Box 4, St. Olavs plass, N-0130 Oslo, Norway

Abstract

The permutation flow shop problem (PFSP) has been applied to many types of problems. The PFSP is an NPhard permutation sequencing scheduling problem. A local search with simulated annealing scheme involving two phases is proposed in this investigation for solving PFSP. First, for lowering computation complexity, a simple insertion local search is applied to generate the solution of the PFSP. Second, two non-decreasing cooling temperature driven simulated annealing (SA) named steady SA and reheating SA are employed to maintain successive exploration or exploitation in the solution space. The steady SA maintains the same temperature and keeps the same search behavior and thereby allows the neighbors of the worse solutions to be explored, consequently increasing the chances of finding better solutions, while the reheating SA increases the temperature and increases the exploration ability. The most important feature of the proposed method is its simple implementation and low computation time complexity. Experimental results are compared with other state-of-the-art algorithms and reveal that the proposed simple insertion with steady SA (SI-SSA) method is able to efficiently yield the best permutation schedules.

Keywords

Scientia Iranica
Volume 22, Issue 4 - Serial Number 4
Transactions on Mechanical Engineering (B)
August 2015
Pages 1545-1553

Files

History

  • Receive Date: 07 January 2015
  • Revise Date: 21 December 2024
  • Accept Date: 27 July 2017

Share

How to cite

Statistics