A Variable Block Insertion Heuristic for Single Machine with Release Dates and Sequence Dependent Setup Times for Makespan Minimization

Abstract

This paper is concerned with solving the single machine scheduling problem with release dates and sequence-dependent setup times in order to minimize the makespan. For this purpose a variable block insertion heuristic (VBIH) algorithm is applied to the problem. The VBIH algorithm performs block moves on a given solution. Mainly it removes a block of jobs with a given size from the solution and inserts the block into the best position of the partial solution. Furthermore we present a novel profile-fitting constructive heuristic for the problem. We evaluate the performance of the VBIH algorithm by comparisons with the beam search heuristic and the iterated greedy algorithm from the literature. Extensive computational results on the benchmark suite consisting of 900 instances from the literature show that the proposed VBIH algorithm is very competitive to the recent beam search heuristic and iterated greedy algorithm from the literature.