A variable block insertion heuristic for permutation flowshops with makespan criterion

Abstract

This paper proposes a populated variable block insertion heuristic (PVBIH) algorithm for solving the permutation flowshop scheduling problem with the makespan criterion. The PVBIH algorithm starts with a minimum block size being equal to one. It removes a block from the current solution and inserts it into the partial solution randomly with a predetermined move size. A local search is applied to the solution found after several block moves. If the new solution generated after the local search is better than the current solution it replaces the current solution. It retains the same block size as long as it improves. Otherwise the block size is incremented by one and a simulated annealing-type of acceptance criterion is used to accept the new solution. This process is repeated until the block size reaches at the maximum block size. In addition we present a randomized profile fitting heuristic with excellent results. Extensive computational results on the Taillard's well-known benchmark suite show that the proposed PVBIH algorithm substantially outperforms the differential evolution algorithm (NS-SGDE) recently proposed in the literature.