Name
Abstract | ||
|---|---|---|
AbstractWe introduce and investigate the problem of scheduling a single lock with parallel chambers. Special cases of this problem are related to interval scheduling. We focus on the existence of no-wait schedules and characterize their feasibility for a lock consisting of two chambers using new graph-theoretical concepts. We obtain a linear time algorithm for this special case. We also provide an efficient algorithm for the case where all chambers of the lock are identical. Furthermore, we describe a dynamic programming algorithm for the general case with arbitrary chambers. Finally, we indicate how our methods for the no-wait case can be applied to practical settings where waiting time is unavoidable. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1287/ijoc.2018.0848 | Periodicals |
Keywords | Field | DocType |
lock scheduling, algorithms, interval scheduling | Mathematical optimization,Fair-share scheduling,Lock (computer science),Scheduling (computing),Interval scheduling,Two-level scheduling,Rate-monotonic scheduling,Dynamic priority scheduling,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
31 | 3 | 1526-5528 |
Citations | PageRank | References |
1 | 0.37 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ward Passchyn | 1 | 14 | 1.67 |
| Dirk Briskorn | 2 | 508 | 35.26 |
| Frits C. R. Spieksma | 3 | 591 | 58.84 |