No-Wait Scheduling for Locks
Ward Passchyn, Dirk Briskorn, Frits C. R. Spieksma
INFORMS Journal on Computing · 2019 · Volume 31 · Issue 3
Abstract
We 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.
Keywords
lock scheduling, algorithms, interval scheduling
Enable JavaScript for citation tools and additional paper interactions.