Effective heuristics for permutation and non-permutation flow shop scheduling with missing operations

Abstract

In recent years, thanks to the fourth industrial revolution, there have been significant increases in the flexibility and agility of industrial processes. In this way, business models based on mass customization of production have gained presence in the industry. In terms of production scheduling in flow shop systems, customization affects production operations, in many cases giving rise to the problem of missing operations, that is, there are jobs that do not perform all operations. Modeling missing operations as zero-time operations, allows to find schedules, but wastes efficiency since zero-time operations lead to unnecessary waiting times. In this paper, we demonstrate that even in permutation flow shops treating missing operations as zero-time operations can make the makespan or the total flow time of optimal schedules arbitrarily worse. We show that a promising way to address missing operations is to consider limited non-permutation solutions over the sub-jobs of a job composed of regular operations. We introduce an efficient representation for such schedules and propose algorithms that allow to solve the problem based on iterated greedy methods. The computational results show that the proposed algorithms are superior to the state-of-the-art algorithms.