Minimization of maximum lateness in an m-machine permutation flow shop with a general exponential learning effect

• We model a flow shop scheduling problem with general learning effects.
• We show a special case that could be solved in polynomial time.
• Composite bounds and dominance rules are demonstrated.
• Branch-and-bound and several heuristic algorithms are proposed.
• A new Nest-Partition-based solution framework is developed.

In this paper, we consider the permutation flow shop scheduling problem with a general exponential learning effect. The objective is to minimize the maximum lateness. A special case that can be solved to optimality by EDD algorithm is provided. To form a hybrid solution framework, several heuristics, a branch-and-bound algorithm and a new Nested-Partition-based solution approach are proposed. Composite bounds and dominance rules are developed to reduce the searching region and to provide guidance on the lower bound. Finally, computational experiments are conducted to evaluate the performance of the algorithms.