No-wait scheduling for locks

Ward Passchyn, Dirk Briskorn and Frits Spieksma

No 533582, Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven

Abstract: We investigate a problem inspired by the practical setting of scheduling a lock with parallel chambers. We show how this problem relates to known interval scheduling problems, as well as to a particular graph coloring problem on multiple unit interval graphs. We explore the relationships between these problems and discuss the complexity of different problem variants. In particular, for a lock consisting of two chambers we are able to characterize the feasible instances and use this result to obtain efficient algorithms. We also provide an efficient algorithm for the special case with identical lock chambers. Furthermore, we describe a dynamic programming approach for the more general case with arbitrary chambers, and prove that the problem is strongly NP-complete when the number of chambers is part of the input.

Keywords: Lock scheduling; Graph coloring; Interval scheduling (search for similar items in EconPapers)
Date: 2016-03
References: Add references at CitEc
Citations:

Published in FEB Research Report KBI_1605

Downloads: (external link)
https://lirias.kuleuven.be/retrieve/376904 No-wait scheduling for locks (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:ete:kbiper:533582

Access Statistics for this paper

More papers in Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven
Bibliographic data for series maintained by library EBIB ().