Name
Abstract | ||
|---|---|---|
The coupled tasks scheduling problem is a class of scheduling problems introduced for beam steering software of sophisticated radar devices, called phased arrays. Due to increasing popularity of such radars, the importance of coupled tasks scheduling is constantly growing. Unfortunately, most of the coupled tasks problems are NP-hard, and only a few practically usable algorithms for such problems were found. This paper provides a survey of already known complexity results of various variants of coupled tasks problems. Then, it complements previous results by providing experimental results of two new polynomial algorithms for coupled tasks scheduling, which are: an exact algorithm for 1 vertical bar(1, 4, 1), strict chains vertical bar C-max problem, and a fast heuristic algorithm for more general 1 vertical bar(1, 2k, 1), strict chains vertical bar C-max problem, where k is an element of N. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1051/ro/2012020 | RAIRO-OPERATIONS RESEARCH |
Keywords | Field | DocType |
Coupled tasks,scheduling,complexity theory,heuristic algorithms | Fixed-priority pre-emptive scheduling,Job shop scheduling,Fair-share scheduling,Deadline-monotonic scheduling,Algorithm,Theoretical computer science,Two-level scheduling,Rate-monotonic scheduling,Dynamic priority scheduling,Round-robin scheduling,Mathematics | Journal |
Volume | Issue | ISSN |
46 | 4 | 0399-0559 |
Citations | PageRank | References |
4 | 0.43 | 15 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jacek Blazewicz | 1 | 1064 | 154.23 |
| Grzegorz Pawlak | 2 | 18 | 3.17 |
| Michal Tanas | 3 | 11 | 1.48 |
| Wojciech Wojciechowicz | 4 | 4 | 0.43 |