Valid inequalities for unrelated parallel machines scheduling with precedence constraints - Université de Lorraine Access content directly
Conference Papers Year : 2016

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

Dates and versions

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

Identifiers

Cite

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

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More