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
Autores principales:	Feuerstein, E., Marchetti-Spaccamela, A., Schalekamp, F., Sitters, R., Van Der Ster, S., Stougie, L., Van Zuylen, A.
Formato:	SER
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:	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	todo:paper_03029743_v8591LNCS_n_p559_Feuerstein
record_format	dspace
spelling	todo:paper_03029743_v8591LNCS_n_p559_Feuerstein2023-10-03T15:19:37Z Scheduling over scenarios on two machines Feuerstein, E. Marchetti-Spaccamela, A. Schalekamp, F. Sitters, R. Van Der Ster, S. Stougie, L. Van Zuylen, A. 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. SER info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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 Feuerstein, E. Marchetti-Spaccamela, A. Schalekamp, F. Sitters, R. Van Der Ster, S. Stougie, L. Van Zuylen, A. 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.
format	SER
author	Feuerstein, E. Marchetti-Spaccamela, A. Schalekamp, F. Sitters, R. Van Der Ster, S. Stougie, L. Van Zuylen, A.
author_facet	Feuerstein, E. Marchetti-Spaccamela, A. Schalekamp, F. Sitters, R. Van Der Ster, S. Stougie, L. Van Zuylen, A.
author_sort	Feuerstein, E.
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
url	http://hdl.handle.net/20.500.12110/paper_03029743_v8591LNCS_n_p559_Feuerstein
work_keys_str_mv	AT feuersteine schedulingoverscenariosontwomachines AT marchettispaccamelaa schedulingoverscenariosontwomachines AT schalekampf schedulingoverscenariosontwomachines AT sittersr schedulingoverscenariosontwomachines AT vandersters schedulingoverscenariosontwomachines AT stougiel schedulingoverscenariosontwomachines AT vanzuylena schedulingoverscenariosontwomachines
_version_	1782029336972361728

Scheduling over scenarios on two machines

Ejemplares similares