On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation |
| |
Authors: | Philippe Baptiste Ruslan Sadykov |
| |
Affiliation: | LIX, UMR CNRS 7161, école Polytechnique, F‐91128 Palaiseau |
| |
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 ∑jFj where Fj(Cj) corresponds to the cost of the completion of job j at time Cj. 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. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009 |
| |
Keywords: | mixed integer program scheduling earliness tardiness |
|
|