Exact and heuristic methods for characterizing optimal solutions for the 1||Lmax

The 1||Lmax problem can be solved in O(nlog(n)) applying EDD rule. Still, as many scheduling problems,1||Lmax may have a huge number of optimal solutions. Our objective is to characterize easily a set of optimal solutions, without enumerating them. Such an approach is useful in a dynamic environment, to react in real time to unexpected events, or to data uncertainty. Some preliminary studies in this direction have been conducted using the lattice of permutations as support. In such a framework, it is assumed that jobs are renumbered in EDD order and due dates are transformed in deadlines so that sequence EDD is feasible and is the root sequence of the lattice. A property is that all the predecessors of a feasible sequence in the lattice are feasible as well, and therefore optimal sequences for the 1||Lmax. These predecessors can be characterized very easily by a partial order between jobs. The distance to the bottom sequence (reverse EDD sequence), also called “level”, is denoted by Sumj Nj. It is expected that a sequence with minimum level will characterize a lot of optimal solutions.

During the talk, we will present the problem 1|deadlinej|Sumj Nj of finding a sequence with minimum level, and we will introduce exact and heuristic resolution methods. Our results show that we improve state-of-the-art resolution approaches, solving to optimality new instances.