Abstract
In various flow shop scheduling problems, it is very common that a machine suffers from breakdowns. Under these situations, a robust and stable sub-optimal scheduling solution is of much more practical interest than a global optimal solution that is sensitive to environmental changes. However, blocking lotstreaming flow shop scheduling problems with machine breakdowns have not yet been well studied up to date. This paper presents, for the first time, a multi-objective formulation of the above problem including robustness and stability criteria. Based on this formulation, an evolutionary multi-objective robust scheduling algorithm (REMO, for short) is suggested, in which solutions obtained by a variant of single-objective heuristic algorithm are incorporated in population initialization and two novel crossover operators are proposed to take advantage of nondominated solutions. In addition, a rescheduling strategy based on the local search is introduced to further reduce the influence resulting from machine breakdowns.The proposed algorithm is applied to 22 test sets, and compared with the state-of-theart algorithms without machine breakdowns. Our empirical results demonstrate that the proposed algorithm can effectively tackle blocking lot-streaming flow shop scheduling problems in the presence of machine breakdowns by obtaining scheduling strategies that are robust and stable.