New results in the worst-case analysis for flow-shop scheduling

AbstractThe worst-case analysis of the approximation algorithm proposed by Palmer and the algorithm RAES (the best of algorithms proposed by Dannenbring) for m-machine permutation flow-shop problem are presented. The worst-case performance ratios equal approximately m2 for each of the algorithms are found. An evaluation of the worst-case performance ratio of Nawaz's algorithm N is shown. Proposed are a few modifications improving the speed of the algorithms RAES and N