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

Philippe Baptiste 1, * Ruslan Sadykov 2, 3
* Corresponding author
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.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00387012
Contributor : Ruslan Sadykov <>
Submitted on : Friday, May 22, 2009 - 3:34:26 PM
Last modification on : Friday, July 26, 2019 - 1:48:03 PM

Links full text

Identifiers

Citation

Philippe Baptiste, Ruslan Sadykov. On Scheduling a Single Machine to Minimize a Piecewise Linear Objective Function : A Compact MIP Formulation. Naval Research Logistics, Wiley-Blackwell, 2009, 56 (6), pp.487--502. ⟨10.1002/nav.20352⟩. ⟨inria-00387012⟩

Share

Metrics

Record views

390