A Tabu Search Based Hyper-heuristic for Flexible Flowshop Scheduling Problems

Abstract

Scheduling is a problem that is often encountered in everyday life, including in manufacturing companies. One type of scheduling problem that is commonly found in the industrial world especially the textile industry is the Flow Shop Scheduling Problem (FSSP). Given a number of jobs that must be processed in a series of stages where at each stage there exists only one machine for processing the jobs, FSSP aims to find a sequence of jobs that meets certain optimal criteria. Flexible FSSP is a variant of FSSP that differs from the classical FSSP in the number of machines at each stage. In a Flexible FSSP, the number of machines at each stage can be more than one. Thus, in solving Flexible FSSP, not only the job ordering but also the machine selection should be considered. This paper presents an algorithm for solving Flexible FSSP. The proposed algorithm combines a hyper-heuristic and tabu search algorithm. Two kinds of heuristics are used in this work, namely heuristics for job selection and heuristics for machine selection. Tabu search algorithm is used twice: for selecting the job selection heuristics and for selecting the machine selection heuristics. The proposed algorithm is then compared with the other algorithm using a fixed combination of two kinds of heuristics. The experiments show that in general, the proposed algorithm performs better than the other algorithm.