Asymptotic optimality of shortest processing time-based algorithms for flow shop and open shop problems with nonlinear objective functions

Abstract

This article investigates the criterion of minimizing total k-power completion time (TKCT) in flow shop and open shop scheduling. For these NP-hard problems, the asymptotic optimality of the shortest processing time-based algorithms is proven for a sufficiently large problem scale. To numerically evaluate the convergence of the algorithms, new lower bounds with performance guarantees are presented for the flow shop TKCT problem. Computational results demonstrate the performance of the proposed algorithms and the effectiveness of the nonlinear objective. In addition, theoretical results on the single-machine TKCT problem are obtained for mathematical deduction.

Keywords:

• scheduling
• flow shop
• open shop
• total k-power completion time
• performance analysis of algorithms