On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation

Philippe Baptiste and Ruslan Sadykov

Naval Research Logistics (NRL), 2009, vol. 56, issue 6, 487-502

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

Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1002/nav.20352

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:56:y:2009:i:6:p:487-502

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().