A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan

•A novel mixed integer linear program is proposed for the scheduling problem.•Experiments showed that a commercial solver can only solve small instances.•A beam search (BS) heuristic is proposed to solve larger instances.•Experiments showed that the BS heuristic finds high quality solutions at low cost.

This paper considers the problem of scheduling a set of jobs subject to arbitrary release dates and sequence-dependent setup times on a single machine with the objective of minimizing the maximum completion of all the jobs, or makespan. This problem is often found in manufacturing processes such as painting and metalworking. A new mixed integer linear program (MILP) is firstly proposed. Because the problem is known to be NP-hard, a beam search heuristic is developed. Computational experiments are carried out using a well-known set of instances from the literature. Our results show that the proposed heuristic is effective in finding high quality solutions at low computational cost.