Minimizing tardiness and maintenance costs in flow shop scheduling by a lower-bound-based GA

• We model a new extension of flow shop and maintenance scheduling as MILP.
• We propose a lower-bound-based genetic algorithm (LBGA) as a new solution approach.
• We conduct a factorial experiment and gap analysis for tuning the GA.
• Only population size is statistically significant in affecting quality of solutions.
• An optimal population size for one problem size is acceptable for all problem sizes.

A permutation flow shop scheduling problem is reformulated as a mixed-integer linear program after incorporating flexible and diverse maintenance activities for minimizing total tardiness and maintenance costs. The terms “flexible” and “diverse” mean that the maintenance activities are not required to perform following fixed and predetermined time intervals, and there can be different types of maintenance activities for each machine. The problem is proved to be NP-hard and a lower bound for the problem is proposed. A lower-bound-based genetic algorithm (LBGA) is presented, in which the algorithm parameters are first tested through a factorial experiment to identify the statistically significant parameters. The LBGA algorithm self-tunes these parameters for its performance improvement based on the solution gap from the lower bound. While it is experienced that only the population size is statistically significant in improving the quality of solutions, through a computational experiment it is also shown that an optimal population size for one problem size yields the same quality of solutions for larger sizes of problems and increasing the population size beyond the optimal size for larger sizes of problems will only negatively affects the efficiency of the algorithm. Computational results that show efficiency and effectiveness of the algorithm are also provided.