[FFK18] Extreme points for scheduling around a common due date

Conférence Internationale avec comité de lecture : ISMP, July 2018, France,
Résumé: We study a single machine just-in-time scheduling problem with a polyhedral approach. The aim is to minimize the weighted sum of earliness and tardiness penalties around a common due date. An instance is considered unrestrictive if all the tasks can be scheduled before the due date. In this case, some dominance properties allows to efficiently solve some particular instances. In the general case, some of these dominance properties are not still valid. For the unrestrictive case, we provide both compact and non-compact formulations. The latter one is extended to the general case. For the non-compact formulations, a vector satisfying all the constraints can correspond to an unfeasible schedule. However, we ensure that the extreme points of the associated polyhedra correspond to feasible schedules satisfying dominance properties. We prove that the separation problem of these two formulations reduces to min-cut problem, leading to a polynomial time algorithm. Some experimental results will illustrate the effectiveness of these formulations.


@inproceedings {
title="{Extreme points for scheduling around a common due date}",
author=" A. Falq and P. Fouilhoux and S. Kedad-Sidhoum ",
address=" France",