Issue |
RAIRO-Oper. Res.
Volume 44, Number 1, January-March 2010
|
|
---|---|---|
Page(s) | 61 - 71 | |
DOI | https://doi.org/10.1051/ro/2010007 | |
Published online | 08 February 2010 |
An efficient ILP formulation for the single machine scheduling problem
1
CNRS, LAAS, 7 avenue du colonel Roche, 31077 Toulouse, France; briand@laas.fr
2
Université de Toulouse, UPS, INSA, INP, ISAE, LAAS, 31077 Toulouse, France; sourari@cdta.dz
3
CDTA, lotissement du 20
août 1956, Baba Hassen, Alger, Algeria; bbouzouia@cdta.dz
This paper considers the problem of scheduling n jobs on a single machine. A fixed processing time and an execution interval are associated with each job. Preemption is not allowed. On the basis of analytical and numerical dominance conditions, an efficient integer linear programming formulation is proposed for this problem, aiming at minimizing the maximum lateness (Lmax). Experiments have been performed by means of a commercial solver that show that this formulation is effective on large problem instances. A comparison with the branch-and-bound procedure of Carlier is provided.
Mathematics Subject Classification: 90B35
Key words: Single machine scheduling / integer linear programming / dominance conditions
© EDP Sciences, ROADEF, SMAI, 2010
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.