The asymptotic convergence of some flow-shop scheduling heuristics

Heuristics are often used to provide solutions for flow-shop scheduling problems. The performance of a heuristic is usually judged by comparing solutions and run times on test cases. This paper proposes an analytical alternative, called Asymptotic Convergence, which tests the convergence of the heuristic to a lower bound as problem size grows. The test is a stronger variation of worst case performance analysis and is applied to heuristics for both the flow-shop makespan and maximum tardiness problems. Results show that first come first served based heuristics meet the test. How the test should be applied is also discussed, along with its application to other measures of due date performance.