Advertisement
Published in:
2012 | OriginalPaper | Chapter
Complete Characterization of Near-Optimal Sequences for the Two-Machine Flow Shop Scheduling Problem
Authors : Jean-Charles Billaut, Emmanuel Hebrard, Pierre Lopez
Published in: Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 analysis 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 exploration of the lattice, traversing it by a simple tree search procedure, is proposed. Computational experiments are given to evaluate these methods and to illustrate the interest and the limits of such approaches.