Scheduling over scenarios on two machines

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 objective...

Descripción completa

Guardado en:
Detalles Bibliográficos
Publicado: 2014
Materias:
approximation
job scheduling
makespan minimization
scenarios
Approximation algorithms
Combinatorial mathematics
Optimization
Scheduling algorithms
Scheduling
Approximability
Job scheduling
Makespan minimization
Optimization problems
Scheduling problem
Two machines
Approximation
Lower bounds
Scenarios
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8591LNCS_n_p559_Feuerstein
http://hdl.handle.net/20.500.12110/paper_03029743_v8591LNCS_n_p559_Feuerstein
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_03029743_v8591LNCS_n_p559_Feuerstein
record_format dspace
spelling paper:paper_03029743_v8591LNCS_n_p559_Feuerstein2023-06-08T15:28:54Z Scheduling over scenarios on two machines approximation job scheduling makespan minimization scenarios Approximation algorithms Combinatorial mathematics Optimization Scheduling algorithms Combinatorial mathematics Optimization Scheduling Approximability approximation Job scheduling Makespan minimization Optimization problems scenarios Scheduling problem Two machines Approximation Lower bounds Scenarios Scheduling Approximation algorithms 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. 2014 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8591LNCS_n_p559_Feuerstein http://hdl.handle.net/20.500.12110/paper_03029743_v8591LNCS_n_p559_Feuerstein
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic approximation
job scheduling
makespan minimization
scenarios
Approximation algorithms
Combinatorial mathematics
Optimization
Scheduling algorithms
Combinatorial mathematics
Optimization
Scheduling
Approximability
approximation
Job scheduling
Makespan minimization
Optimization problems
scenarios
Scheduling problem
Two machines
Approximation
Lower bounds
Scenarios
Scheduling
Approximation algorithms
spellingShingle approximation
job scheduling
makespan minimization
scenarios
Approximation algorithms
Combinatorial mathematics
Optimization
Scheduling algorithms
Combinatorial mathematics
Optimization
Scheduling
Approximability
approximation
Job scheduling
Makespan minimization
Optimization problems
scenarios
Scheduling problem
Two machines
Approximation
Lower bounds
Scenarios
Scheduling
Approximation algorithms
Scheduling over scenarios on two machines
topic_facet approximation
job scheduling
makespan minimization
scenarios
Approximation algorithms
Combinatorial mathematics
Optimization
Scheduling algorithms
Combinatorial mathematics
Optimization
Scheduling
Approximability
approximation
Job scheduling
Makespan minimization
Optimization problems
scenarios
Scheduling problem
Two machines
Approximation
Lower bounds
Scenarios
Scheduling
Approximation algorithms
description 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.
title Scheduling over scenarios on two machines
title_short Scheduling over scenarios on two machines
title_full Scheduling over scenarios on two machines
title_fullStr Scheduling over scenarios on two machines
title_full_unstemmed Scheduling over scenarios on two machines
title_sort scheduling over scenarios on two machines
publishDate 2014
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8591LNCS_n_p559_Feuerstein
http://hdl.handle.net/20.500.12110/paper_03029743_v8591LNCS_n_p559_Feuerstein
_version_ 1768541610063167488

Ejemplares similares