Unrelated Parallel Machine Scheduling Problem with Precedence Constraints: Polyhedral Analysis and Branch-and-Cut - Université de Lorraine Access content directly
Conference Papers Year : 2016

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

Abstract

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.
No file

Dates and versions

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

Identifiers

  • HAL Id : hal-01785935 , version 1

Cite

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 View
0 Download

Share

Gmail Facebook X LinkedIn More