On Scheduling a Single Machine to Minimize a Piecewise Linear Objective Function : A Compact MIP Formulation
| hal.structure.identifier | Laboratoire d'informatique de l'École polytechnique [Palaiseau] [LIX] | |
| dc.contributor.author | BAPTISTE, Philippe | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | SADYKOV, Ruslan | |
| dc.date.accessioned | 2024-04-04T02:38:20Z | |
| dc.date.available | 2024-04-04T02:38:20Z | |
| dc.date.issued | 2009 | |
| dc.identifier.issn | 0894-069X | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/190867 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.publisher | Wiley-Blackwell | |
| dc.title.en | On Scheduling a Single Machine to Minimize a Piecewise Linear Objective Function : A Compact MIP Formulation | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1002/nav.20352 | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | Naval Research Logistics | |
| bordeaux.page | 487--502 | |
| bordeaux.volume | 56 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 6 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | inria-00387012 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00387012v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Naval%20Research%20Logistics&rft.date=2009&rft.volume=56&rft.issue=6&rft.spage=487--502&rft.epage=487--502&rft.eissn=0894-069X&rft.issn=0894-069X&rft.au=BAPTISTE,%20Philippe&SADYKOV,%20Ruslan&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||