A Mixed Integer Linear Programming approach to minimize the number of late jobs with and without machine availability constraints
hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
dc.contributor.author | DETIENNE, Boris | |
dc.date.accessioned | 2024-04-04T02:21:07Z | |
dc.date.available | 2024-04-04T02:21:07Z | |
dc.date.created | 2012-10-16 | |
dc.date.issued | 2014-06-16 | |
dc.identifier.issn | 0377-2217 | |
dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/189543 | |
dc.description.abstractEn | This study investigates scheduling problems that occur when the weighted number of late jobs that are subject to deterministic machine availability constraints have to be minimized. These problems can be modeled as a more general job selection problem. Cases with resumable, non-resumable, and semi-resumable jobs as well as cases without availability constraints are investigated. The proposed efficient mixed integer linear programming approach includes possible improvements to the model, notably specialized lifted knapsack cover cuts. The method proves to be competitive compared with existing dedicated methods: numerical experiments on randomly generated instances show that all 350-job instances of the test bed are closed for the well-known problem $1|r_i|\sum w_iU_i$. For all investigated problem types, 98.4% of $500$-job instances can be solved to optimality within one hour. | |
dc.language.iso | en | |
dc.publisher | Elsevier | |
dc.subject.en | Scheduling | |
dc.subject.en | Integer programming | |
dc.subject.en | Modeling | |
dc.subject.en | Availability constraints | |
dc.subject.en | Late jobs | |
dc.subject.en | Exact method | |
dc.title.en | A Mixed Integer Linear Programming approach to minimize the number of late jobs with and without machine availability constraints | |
dc.type | Article de revue | |
dc.identifier.doi | 10.1016/j.ejor.2013.10.052 | |
dc.subject.hal | Mathématiques [math]/Optimisation et contrôle [math.OC] | |
dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
bordeaux.journal | European Journal of Operational Research | |
bordeaux.page | 540--552 | |
bordeaux.volume | 235 | |
bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
bordeaux.issue | 3 | |
bordeaux.institution | Université de Bordeaux | |
bordeaux.institution | Bordeaux INP | |
bordeaux.institution | CNRS | |
bordeaux.peerReviewed | oui | |
hal.identifier | hal-00880908 | |
hal.version | 1 | |
hal.popular | non | |
hal.audience | Internationale | |
hal.origin.link | https://hal.archives-ouvertes.fr//hal-00880908v1 | |
bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=European%20Journal%20of%20Operational%20Research&rft.date=2014-06-16&rft.volume=235&rft.issue=3&rft.spage=540--552&rft.epage=540--552&rft.eissn=0377-2217&rft.issn=0377-2217&rft.au=DETIENNE,%20Boris&rft.genre=article |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |