Skip to Main content Skip to Navigation
Theses

Dominances in linear programming : scheduling around a common due date

Abstract : Scheduling problems are combinatorial optimization problems arising in project management: the aim is to schedule tasks execution under resource constraints or precedence constraints so as to minimize a cost or maximize a gain. An integer linear programm (ILP° consists in optimizing a linear objective function over the integer points satisfying linear constraints. A lot of operation research problems can be formulated as ILP, and then be solved by commercial ILP. This thesis focuses on a single machine scheduling problem where earliness and tardiness with respect to a common due date have to be minimized. Thanks to so-called dominance properties used in the scheduling field, we propose several ILP formulation for this problem. First formulations, which are based on continuous variables similar to completion times variables (natural variables), use non-overlapping inequalities. Last formulations, which are based on binary partition variables, rely on a new type of linear inequalities that translate dominance properties.
Complete list of metadata

https://tel.archives-ouvertes.fr/tel-03247744
Contributor : Abes Star :  Contact
Submitted on : Thursday, June 3, 2021 - 11:32:08 AM
Last modification on : Saturday, June 5, 2021 - 3:38:40 AM

File

FALQ_Anne_Elisabeth_2020.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-03247744, version 1

Citation

Anne-Elisabeth Falq. Dominances in linear programming : scheduling around a common due date. Discrete Mathematics [cs.DM]. Sorbonne Université, 2020. English. ⟨NNT : 2020SORUS128⟩. ⟨tel-03247744⟩

Share

Metrics

Record views

75

Files downloads

39