Asymptotic optimality of shortest processing time-based algorithms for flow shop and open shop problems with nonlinear objective functions |
| |
Authors: | Danyu Bai Zhihai Zhang |
| |
Affiliation: | 1. School of Economics and Management, Shenyang University of Chemical Technology, Shenyang, PR China;2. Department of Industrial Engineering, Tsinghua University, Beijing, PR China;3. Department of Industrial Engineering, Tsinghua University, Beijing, PR China |
| |
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 |
|
|