Permutation flow shop scheduling problem to minimize nonlinear objective function with release dates

•B&B algorithm with release-date-based branching rule for small-scale problems.•DDE algorithm with multi-point insertion scheme for moderate-scale problems.•A lower bound with performance guarantee for large-scale problems.•Worst-case analysis for the SPTA-based heuristic under the consistency condition.

In a dynamic flow shop scheduling model, each released job has to be executed on a set of machines in series following the identical route. The criterion of optimality, total k-power completion time (k ≥ 2) is addressed for this problem. Given its NP-hardness, a branch and bound (B&B) algorithm is designed to obtain the optimal solutions for small-scale problems. On the basis of an initial population generated by the upper bounds of the B&B algorithm, a discrete differential evolution algorithm is introduced to solve medium-scale problems. As the by-product of the B&B algorithm, a sequence-independent lower bound with performance guarantee is presented as a substitute of the optimal solution for large-scale problems. Moreover, the worst-case ratio of the shortest-processing-time-based rule under a consistency condition is provided for the problem. The numerical experiments demonstrate the effectiveness of the proposed algorithms and the new lower bound.