Resolution methods for characterizing optimal solutions for the 1||Lmax

EasyChair Preprint 2618

Abstract

The 1||L_max problem can be solved in O(nlogn) applying EDD rule (Jackson 1955). Still, as many scheduling problems, 1||L_max 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. In this paper, we study the problem of finding a sequence with minimum level in a lattice of permutations. It is expected that this sequence will characterize a lot of optimal solutions.

Keyphrases: Ordonnancement, caractérisation de solutions, treillis de permutations

@booklet{EasyChair:2618,
  author    = {Tifenn Rault and Ronan Bocquillon and Jean-Charles Billaut},
  title     = {Resolution methods for characterizing optimal solutions for the 1||Lmax},
  howpublished = {EasyChair Preprint 2618},
  year      = {EasyChair, 2020}}