|
 
|
[FFK18] Extreme points for scheduling around a common due date
Conférence Internationale avec comité de lecture : ISMP, July 2018, France,
motcle:
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.
BibTeX
| @inproceedings { | |||
| FFK18, | |||
| title | = | "{Extreme points for scheduling around a common due date}", | |
| author | = | " A. Falq and P. Fouilhoux and S. Kedad-Sidhoum ", | |
| booktitle | = | "{ISMP}", | |
| year | = | 2018, | |
| month | = | "July", | |
| address | = | " France", | |
| } | |||
