Unrelated Parallel Machine Scheduling Problem with Precedence Constraints: Polyhedral Analysis and Branch-and-Cut - Université de Lorraine Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Unrelated Parallel Machine Scheduling Problem with Precedence Constraints: Polyhedral Analysis and Branch-and-Cut

Résumé

We consider the problem of unrelated parallel machines with precedence constraints (UPMPC), with the aim of minimizing the makespan. Each task has to be assigned to a unique machine and no preemption is allowed. In this paper, we show the relation between the interval graph and the UPMSPC problem. We propose valid inequalities and study the facial structure of their polytope. Facets are presented to strength the associated integer linear program formulation to help in solving the global problem. We develop a Branch and Cut algorithm for solving the problem and present some experimental results.
Fichier non déposé

Dates et versions

hal-01785935 , version 1 (04-05-2018)

Identifiants

  • HAL Id : hal-01785935 , version 1

Citer

Mohammed-Albarra Hassan, Imed Kacem, Sébastien Martin, Izzeldin Osman. Unrelated Parallel Machine Scheduling Problem with Precedence Constraints: Polyhedral Analysis and Branch-and-Cut. International Symposium on Combinatorial Optimization ISCO 2016: Combinatorial Optimization , May 2016, Salerne, Italy. pp.308-319. ⟨hal-01785935⟩
54 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More