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.
Document type :
Conference papers
Complete list of metadatas

https://hal.univ-lorraine.fr/hal-01785935
Contributor : Lcoms Ul <>
Submitted on : Friday, May 4, 2018 - 5:14:24 PM
Last modification on : Tuesday, January 22, 2019 - 4:42:09 PM

Identifiers

  • HAL Id : hal-01785935, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

38