A novel metaheuristic approach for the flow shop scheduling problem

作者：Nearchou AC^*

来源：Engineering Applications of Artificial Intelligence, 2004, 17(3): 289-300.

DOI：10.1016/j.engappai.2004.02.008

• flow shop scheduling
• meta-heuristics
• hybridization
• simulated annealing

Advances in modern manufacturing systems such as CAD/CAM, FMS, CIM, have increased the use of intelligent techniques for solving various combinatorial and NP-hard sequencing and scheduling problems. Production process in these systems consists of workshop problems such as grouping similar parts into manufacturing cells and proceeds by passing these parts on machines in the same order. This paper presents a new hybrid simulated annealing algorithm (hybrid SAA) for solving the flow-shop scheduling problem (FSSP); an NP-hard scheduling problem with a strong engineering background. The hybrid SAA integrates the basic structure of a SAA together with features borrowed from the fields of genetic algorithms (GAs) and local search techniques. Particularly, the algorithm works from a population of candidate schedules and generates new populations of neighbor schedules by applying suitable small perturbation schemes. Further, during the annealing process, an iterated hill climbing procedure is stochastically applied on the population of schedules with the hope to improve its performance.
The proposed approach is fast and easily implemented. Computational results on several public benchmarks of FSSP instances with up to 500 jobs and 20 machines show the effectiveness and the high quality performance of the approach. In comparison to the performance of previous SA and GA methods, the performance of the proposed one was found superior.

• 出版日期2004-4