No-wait scheduling for locks

Ward Passchyn (Corresponding author), Dirk Briskorn (Corresponding author), F.C.R. Spieksma (Corresponding author)

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Samenvatting

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.

Originele taal-2Engels
Pagina's (van-tot)413-428
Aantal pagina's16
TijdschriftINFORMS Journal on Computing
Volume31
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 2019

Vingerafdruk Duik in de onderzoeksthema's van 'No-wait scheduling for locks'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit