Some results of the worst-case analysis for flow shop scheduling

Known approximation algorithms recommended for the permutation flow-shop problem with the weighted sum of completion times have a worst-case performance ratio which is unknown, or known but unlimited. We propose new algorithms with this ratio equal to ⌈m/k⌉ρk, where ρk is the worst-case performance ratio of an algorithm which solves an auxiliary k-machine problem. Worst-case analyses of other approximation algorithms for the mean completion time and the makespan criteria are also presented.