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

• Record Type: Journal Article
• Authors: Vélez-Gallego, Mario C.; Maya, Jairo; Montoya-Torres, Jairo R.
• Is Part Of: Computers & operations research. Volume 73(2016)
• Page Start: 132
• Page End: 140
• Publication Date: 2016-09
• Subjects: Single machine scheduling -- Release dates -- Sequence-dependent setup times -- Beam search -- Makespan; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.04.009
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Highlights: 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.