A note on the complexity of scheduling coupled tasks on a single processor
| Autor: | Michal Tanas, Tamás Kis, Jacek Blazewicz, Klaus H. Ecker |
|---|---|
| Předmět: |
coupled tasks
General Computer Science Scheduling Computer science General problem Dynamic priority scheduling Parallel computing Multiprocessor scheduling Fair-share scheduling law.invention Scheduling (computing) Fixed-priority pre-emptive scheduling law Nurse scheduling problem NP-hardness Radar Computer Science::Operating Systems |
| Zdroj: | Scopus-Elsevier Journal of the Brazilian Computer Society v.7 n.3 2001 Journal of the Brazilian Computer Society Sociedade Brasileira de Computação (SBC) instacron:UFRGS Journal of the Brazilian Computer Society, Volume: 7, Issue: 3, Pages: 23-26, Published: 2001 |
| Popis: | This paper considers a problem of coupled task scheduling on one processor, where all processing times are equal to 1, the gap has exact length h, precedence constraints are strict and the criterion is to minimise the schedule length. This problem is introduced e.g. in systems controlling radar operations. We show that the general problem is NP-hard. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|