Beam search-based heuristics for the mixed no-idle flowshop with total flowtime criterion

This paper addresses the mixed no-idle flowshop scheduling problem with flowtime minimization. In a mixed no-idle environment, machines are set in series and some machines do not allow idleness and require continuous processing. We approached a variant of this problem that analyses the total flowtime minimization criterion. As this is a new problem, novel high-performance heuristics and metaheuristics were presented. In order to assess the proposed algorithms, we evaluated well-known heuristics and metaheuristics from similar scheduling problems. Furthermore, we developed a speed-up procedure to increase the efficiency of the proposed methods. The presented algorithms were exhaustively tested in a well-known large benchmark with 1750 problem instances. Our results indicate that the novel heuristics and metaheuristics are computationally efficient and obtain high-quality solutions.