Agility in two-stage hybrid flow shop parallel machine scheduling through simulated annealing

The problem of flexible hybrid flow shop scheduling with identical and nonidentical parallel machines in one or more stages has been considered with the objective of minimising the makespan. A Simulated Annealing (SA) approach has been developed to select the best solutions in a flexible hybrid flow shop scheduling. The SA approach identifies the best sequences for the given set of jobs in 2-stage/2-machine and 2-stage/3-machine hybrid flow shop problems. The extent of deviation of the performance measures owing to the flexibility in the arrangement of machines in the two stages has been analysed. The proposed SA algorithm has been applied to benchmark problems taken from Taillard. A comparison of the solutions yielded by the ant-colony algorithm by Stuetzle, called Max–Min Ant System (MMAS) and the SA algorithm developed in this paper, with the heuristic solutions given by Taillard is undertaken with respect to the minimisation of makespan. The comparison shows that the proposed SA algorithm performs better on the average, than the MMAS.