Time Indexed Formulations for Scheduling Chains on a Single Machine: An Application to Airborne Radars
| 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:34:00Z | |
| dc.date.available | 2024-04-04T02:34:00Z | |
| dc.date.issued | 2010 | |
| dc.identifier.issn | 0377-2217 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/190523 | |
| dc.description.abstractEn | Airborne radars are widely used to perform a large variety of tasks in an aircraft (searching, tracking, identifying targets, etc.) Such tasks play a crucial role for the aircraft and they are repeated in a ``more or less'' cyclic fashion. This defines a scheduling problem that impacts a lot on the quality of the radar output and on the overall safety of the aircraft. In our model, jointly defined with ``Thales Airborne Systems'', the radar executes the schedule of the current time frame while the schedule of the next frame is computed. The radar is a single machine and a radar task is a job to be scheduled on the machine. A job consists of a chain of operations with identical processing times. The operations of the same job should be ideally scheduled with a given frequency, and any deviation from this frequency is penalized using a V-shape function. Our objective is then to minimize the total penalty. In this paper, we present three time indexed formulations for the problem. Two of the formulations are compact and can be solved directly by a Mixed-Integer Programming solver. The third formulation relies on a Branch-and-Price algorithm. Theoretical and experimental comparisons of the formulations are reported. | |
| dc.description.sponsorship | ALgorithmique des Plates-formes A Grande Echelle - ANR-05-MMSA-0006 | |
| dc.language.iso | en | |
| dc.publisher | Elsevier | |
| dc.subject.en | Scheduling | |
| dc.subject.en | Integer Programming | |
| dc.subject.en | OR in Military | |
| dc.title.en | Time Indexed Formulations for Scheduling Chains on a Single Machine: An Application to Airborne Radars | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1016/j.ejor.2009.07.037 | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | European Journal of Operational Research | |
| bordeaux.page | 476-483 | |
| bordeaux.volume | 203 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 2 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | inria-00339639 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00339639v1 | |
| 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=2010&rft.volume=203&rft.issue=2&rft.spage=476-483&rft.epage=476-483&rft.eissn=0377-2217&rft.issn=0377-2217&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. |
|||