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...
Guardado en:
| Publicado: |
2003
|
|---|---|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10946136_v6_n2_p167_Feuerstein http://hdl.handle.net/20.500.12110/paper_10946136_v6_n2_p167_Feuerstein |
| Aporte de: |
| id |
paper:paper_10946136_v6_n2_p167_Feuerstein |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_10946136_v6_n2_p167_Feuerstein2023-06-08T16:06:57Z On-line multi-threaded Scheduling 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. 2003 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10946136_v6_n2_p167_Feuerstein 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 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. |
| 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 |
| publishDate |
2003 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10946136_v6_n2_p167_Feuerstein http://hdl.handle.net/20.500.12110/paper_10946136_v6_n2_p167_Feuerstein |
| _version_ |
1768545105928519680 |