Optimal Elimination Methods in the m × n Flow-Shop Scheduling Problem

For solving the flow-shop scheduling problem, this paper examines elimination techniques that reduce the set of solutions to a subset that must contain the optimal solution being sought. The paper shows (1) that the elimination method of Szwarc [Naval Res. Log. Quart. 18, 295–305 (1971)] removes at least as many solutions as any other method, and is therefore optimal, and (2) how to construct a general counterexample to any procedure that removes more sequences than this optimal method.