Skip to Main content Skip to Navigation

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
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


Version validated by the jury (STAR)


  • HAL Id : tel-03247744, version 1


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⟩



Record views


Files downloads