New efficient constructive heuristics for the two-stage multi-machine assembly scheduling problem

Abstract

In this paper, we address the two-stage multi-machine assembly scheduling problem, a layout consisting of several dedicated parallel machines in the first stage and identical parallel machines in the second stage. The objective considered is the minimisation of the total completion time. Despite its relevance in practice and its NP-hard nature, this problem has not received much attention so far in the literature. In our paper, we propose two new efficient heuristics. The first heuristic constructs a solution taking into account some specific knowledge of the problem domain. This algorithm is embedded into a beam search-based constructive heuristic and its behaviour when the beam width takes different values is analysed. The computational experiments carried out show that the proposals are more efficient than the existing heuristics for the problem and also the adaptations of heuristics from related problems.