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

EasyChair Preprint no. 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: caractérisation de solutions, Ordonnancement, 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 no. 2618},

  year = {EasyChair, 2020}}