On Scheduling a Single Machine to Minimize a Piecewise Linear Objective Function : A Compact MIP Formulation

Philippe Baptiste 1, * Ruslan Sadykov 2, 3
* Auteur correspondant
2 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : We study the scheduling situation in which a set of jobs subjected to release dates and deadlines are to be performed on a single machine. The objective is to minimize a piecewise linear objective function $\sum_j F_j$ where $F_j(C_j)$ corresponds to the cost of the completion of job $j$ at time $C_j$. This class of function is very large and thus interesting both from a theoretical and practical point of view: It can be used to model total (weighted) completion time, total (weighted) tardiness, earliness and tardiness, etc. We introduce a new Mixed Integer Program (MIP) based on time interval decomposition. Our MIP is closely related to the well-known time-indexed MIP formulation but uses much less variables and constraints. Experiments on academic benchmarks as well as on real-life industrial problems show that our generic MIP formulation is efficient.
Type de document :
Article dans une revue
Naval Research Logistics / Naval Research Logistics An International Journal, John Wiley & Sons, 2009, 56 (6), pp.487--502. 〈10.1002/nav.20352〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00387012
Contributeur : Ruslan Sadykov <>
Soumis le : vendredi 22 mai 2009 - 15:34:26
Dernière modification le : jeudi 12 avril 2018 - 01:48:01

Lien texte intégral

Identifiants

Collections

Citation

Philippe Baptiste, Ruslan Sadykov. On Scheduling a Single Machine to Minimize a Piecewise Linear Objective Function : A Compact MIP Formulation. Naval Research Logistics / Naval Research Logistics An International Journal, John Wiley & Sons, 2009, 56 (6), pp.487--502. 〈10.1002/nav.20352〉. 〈inria-00387012〉

Partager

Métriques

Consultations de la notice

322