We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all possible scenarios. Each scenario is a subset of jobs that must be executed in that scenario and all scenarios are given explicitly. The two objectives that we consider are minimizing the maximum makespan over all scenarios and minimizing the sum of the makespans of all scenarios. For both versions, we give several approximation algorithms and lower bounds on their approximability. With this research into optimization problems over scenarios, we have opened a new and rich field of interesting problems. © 2014 Springer International Publishing Switzerland.
Scheduling over scenarios on two machines / Esteban, Feuerstein; MARCHETTI SPACCAMELA, Alberto; Frans, Schalekamp; Rene, Sitters; Suzanne Van Der, Ster; Leen, Stougie; Anke Van, Zuylen. - 8591 LNCS:(2014), pp. 559-571. (Intervento presentato al convegno 20th International Computing and Combinatorics Conference, COCOON 2014 tenutosi a Atlanta, GA nel 4 August 2014 through 6 August 2014) [10.1007/978-3-319-08783-2_48].
Scheduling over scenarios on two machines
MARCHETTI SPACCAMELA, Alberto;
2014
Abstract
We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all possible scenarios. Each scenario is a subset of jobs that must be executed in that scenario and all scenarios are given explicitly. The two objectives that we consider are minimizing the maximum makespan over all scenarios and minimizing the sum of the makespans of all scenarios. For both versions, we give several approximation algorithms and lower bounds on their approximability. With this research into optimization problems over scenarios, we have opened a new and rich field of interesting problems. © 2014 Springer International Publishing Switzerland.| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2014_11573-644990.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
219.66 kB
Formato
Adobe PDF
|
219.66 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
