BAPTISTE, Philippe; SADYKOV, Ruslan

doi:10.1002/nav.20352

Métadonnées

Licence d’utilisation du document

BAPTISTE, Philippe
Laboratoire d'informatique de l'École polytechnique [Palaiseau] [LIX]

SADYKOV, Ruslan
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]

Langue

Article de revue

Ce document a été publié dans

Naval Research Logistics. 2009, vol. 56, n° 6, p. 487--502

Wiley-Blackwell

Résumé en anglais

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.< Réduire

Métadonnées

Partager cette publication !

Licence d’utilisation du document

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

Langue

Ce document a été publié dans

Résumé en anglais

URI

DOI

Origine

Unités de recherche