Complete Characterization of Near-Optimal Sequences for the Two-Machine Flow Shop Scheduling Problem

Abstract. In a two-machine flow shop scheduling problem, the set of -approximate sequences (i.e., solutions within a factor 1+ of the optimal) can be mapped to the vertices of a permutation lattice. We introduce two approaches, based on properties derived from the anal-ysis of permutation lattices, for characterizing large sets of near-optimal solutions. In the first approach, we look for a sequence of minimum level in the lattice, since this solution is likely to cover many optimal or near-optimal solutions. In the second approach, we look for all sequences of minimal level, thus covering all -approximate sequences. Integer linear programming and constraint programming models are first proposed to solve the former problem. For the latter problem, a direct ex-ploration of the lattice, traversing it by a simple tree search procedure, is proposed. Computational experiments are given to evaluate these meth-ods and to illustrate the interest and the limits of such approaches.