On-line multi-threaded Scheduling

On-line scheduling problems are studied with jobs organized in a number of sequences called threads. Each job becomes available as soon as a scheduling decision is made on all preceding jobs in the same thread. We consider two different on-line paradigms. The first one models a sort of batch process...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Feuerstein, E., Mydlarz, M., Stougie, L.
Formato:	JOUR
Materias:	Competitive analysis Multiple threads On-line algorithms Scheduling problems Algorithms Constraint theory Decision making Information retrieval Mathematical models Problem solving Program processors Real time systems Scheduling Online systems
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_10946136_v6_n2_p167_Feuerstein
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_10946136_v6_n2_p167_Feuerstein
record_format	dspace
spelling	todo:paper_10946136_v6_n2_p167_Feuerstein2023-10-03T16:05:16Z On-line multi-threaded Scheduling Feuerstein, E. Mydlarz, M. Stougie, L. Competitive analysis Multiple threads On-line algorithms Scheduling problems Algorithms Constraint theory Decision making Information retrieval Mathematical models Problem solving Program processors Real time systems Scheduling Competitive analysis Multiple threads On-line algorithms Scheduling problems Online systems On-line scheduling problems are studied with jobs organized in a number of sequences called threads. Each job becomes available as soon as a scheduling decision is made on all preceding jobs in the same thread. We consider two different on-line paradigms. The first one models a sort of batch process: a schedule is constructed, in an on-line way, which is to be executed later. The other one models a real-time planning situation: jobs are immediately executed at the moment they are assigned to a machine. The classical objective functions of minimizing makespan and minimizing average completion time of the jobs are studied. We establish a fairly complete set of results for these problems. One of the highlights is that List Scheduling is a best possible algorithm for the makespan problem under the real-time model if the number of machines does not exceed the number of threads by more than 1. Another one is a polynomial time best possible algorithm for minimizing the average completion time on a single machine under both on-line paradigms. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_10946136_v6_n2_p167_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	Competitive analysis Multiple threads On-line algorithms Scheduling problems Algorithms Constraint theory Decision making Information retrieval Mathematical models Problem solving Program processors Real time systems Scheduling Competitive analysis Multiple threads On-line algorithms Scheduling problems Online systems
spellingShingle	Competitive analysis Multiple threads On-line algorithms Scheduling problems Algorithms Constraint theory Decision making Information retrieval Mathematical models Problem solving Program processors Real time systems Scheduling Competitive analysis Multiple threads On-line algorithms Scheduling problems Online systems Feuerstein, E. Mydlarz, M. Stougie, L. On-line multi-threaded Scheduling
topic_facet	Competitive analysis Multiple threads On-line algorithms Scheduling problems Algorithms Constraint theory Decision making Information retrieval Mathematical models Problem solving Program processors Real time systems Scheduling Competitive analysis Multiple threads On-line algorithms Scheduling problems Online systems
description	On-line scheduling problems are studied with jobs organized in a number of sequences called threads. Each job becomes available as soon as a scheduling decision is made on all preceding jobs in the same thread. We consider two different on-line paradigms. The first one models a sort of batch process: a schedule is constructed, in an on-line way, which is to be executed later. The other one models a real-time planning situation: jobs are immediately executed at the moment they are assigned to a machine. The classical objective functions of minimizing makespan and minimizing average completion time of the jobs are studied. We establish a fairly complete set of results for these problems. One of the highlights is that List Scheduling is a best possible algorithm for the makespan problem under the real-time model if the number of machines does not exceed the number of threads by more than 1. Another one is a polynomial time best possible algorithm for minimizing the average completion time on a single machine under both on-line paradigms.
format	JOUR
author	Feuerstein, E. Mydlarz, M. Stougie, L.
author_facet	Feuerstein, E. Mydlarz, M. Stougie, L.
author_sort	Feuerstein, E.
title	On-line multi-threaded Scheduling
title_short	On-line multi-threaded Scheduling
title_full	On-line multi-threaded Scheduling
title_fullStr	On-line multi-threaded Scheduling
title_full_unstemmed	On-line multi-threaded Scheduling
title_sort	on-line multi-threaded scheduling
url	http://hdl.handle.net/20.500.12110/paper_10946136_v6_n2_p167_Feuerstein
work_keys_str_mv	AT feuersteine onlinemultithreadedscheduling AT mydlarzm onlinemultithreadedscheduling AT stougiel onlinemultithreadedscheduling
_version_	1807316290360049664

On-line multi-threaded Scheduling

Ejemplares similares