Skip to Main content Skip to Navigation
Conference papers

Valid inequalities for unrelated parallel machines scheduling with precedence constraints

Abstract : This paper deals with the mathematical modeling of a scheduling problem for unrelated parallel machines with precedence constraints in order to minimize the makespan (Cmax). This study was motivated by the quality of the Integer Program based on the interval graph. Three families of inequalities are proposed. The first two inequalities based on the idea of the precedence jobs and the third based on the shortest processing time(SPT). We studied the validity of the new inequalities and strength them by checking the linear combination. After an exhaustive computational and statistical analysis we can conclude that the addition of these inequalities decreases the computational requirements to obtain the optimal solution in many cases.
Document type :
Conference papers
Complete list of metadata

https://hal.univ-lorraine.fr/hal-01785913
Contributor : Lcoms Ul <>
Submitted on : Friday, May 4, 2018 - 4:50:35 PM
Last modification on : Wednesday, September 23, 2020 - 4:30:06 AM

Identifiers

Citation

Mohammed-Albarra Hassan, Imed Kacem, Sébastien Martin, Izzeldin Osman. Valid inequalities for unrelated parallel machines scheduling with precedence constraints. 2016 International Conference on Control, Decision and Information Technologies (CoDIT), Apr 2016, Saint Julian's, Malta. ⟨10.1109/CoDIT.2016.7593644⟩. ⟨hal-01785913⟩

Share

Metrics

Record views

83