Permutation flowshop scheduling with periodic maintenance and makespan objective

Abstract

In this paper, we address the permutation flowshop scheduling problem with cyclical unavailability periods where no operation can be processed. Under this constraint, all machines must stop at the same time due to the shift calendar (shift changes, nights, weekends, etc.), or due to preventive deterministic and fixed maintenance activities. For this reason, this constraint is known in the literature as periodic maintenance. Although different decision problems dealing with the simultaneous scheduling of jobs and maintenance activities have been studied in the literature, scheduling with periodic maintenance has been only addressed for the single machine and parallel machines layouts, and we are not aware of references tackling the flowshop. In this layout, different scheduling problems arise depending on the assumptions about the preemption of the operations. Here we focus on scheduling jobs in a flowshop with the objective of minimising the makespan assuming that the preemption of operations is not allowed, and therefore, if an operation cannot be finished within the current availability period, then it should be scheduled in the next one. The structure and hardness of the problem depending on the size of the availability periods is studied using Mixed Integer Linear Programming and complete enumeration, in order to determine the range of values for the availability period that makes the problem under consideration to be substantially different than its classical (unconstrained) counterpart. For these cases, specific heuristics with different computational complexity are developed, and an extensive computational experience is carried out to establish the efficiency of the proposed heuristics.