Generating improved dominance conditions for the flowshop problem (Q580164)

This paper proposes a class of functions that generates new dominance conditions for the flowship scheduling problem and shows that the use of these conditions will eliminate more partial sequences than the existing conditions. While the problem is in the NP-complete category, the use of the proposed dominance conditions reduces the number of active partial schedules to be examined and stored. These improvements are useful in solving the flowshop scheduling problems through the branch-and-bound and elimination procedures.