No-Wait Scheduling for Locks

Ward Passchyn (), Dirk Briskorn () and Frits C. R. Spieksma ()
Additional contact information
Ward Passchyn: Faculty of Economics and Business, ORSTAT, KU Leuven, 3000 Leuven, Belgium; OM Partners, 2160 Wommelgem, Belgium;
Dirk Briskorn: Lehrstuhl für Produktion und Logistik, Bergische Universität Wuppertal, 42119 Wuppertal, Germany;
Frits C. R. Spieksma: Faculty of Economics and Business, ORSTAT, KU Leuven, 3000 Leuven, Belgium; Department of Mathematics and Computer Science, Eindhoven University of Technology, 5600 Eindhoven, Netherlands

INFORMS Journal on Computing, 2019, vol. 31, issue 3, 413–428

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 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0848 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:3:p:413-428

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().