No-wait scheduling for locks

Ward Passchyn; Dirk Briskorn; F.C.R. Spieksma

doi:10.1287/ijoc.2018.0848

No-wait scheduling for locks

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

Research output: Contribution to journal › Article › Academic › peer-review

7 Citations (Scopus)

120 Downloads (Pure)

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.

Original language	English
Pages (from-to)	413-428
Number of pages	16
Journal	INFORMS Journal on Computing
Volume	31
Issue number	3
DOIs	https://doi.org/10.1287/ijoc.2018.0848
Publication status	Published - 2019

Funding

aFaculty of Economics and Business, ORSTAT, KU Leuven, 3000 Leuven, Belgium; bOM Partners, 2160 Wommelgem, Belgium; cLehrstuhl für Produktion und Logistik, Bergische Universität Wuppertal, 42119 Wuppertal, Germany; dDepartment of Mathematics and Computer Science, Eindhoven University of Technology, 5600 Eindhoven, Netherlands Contact: [email protected], https://orcid.org/0000-0002-5422-5526 (WP); [email protected], https://orcid.org/0000-0003-1829-8100 (DB); [email protected], https://orcid.org/0000-0002-2547-3782 (FCRS) History: Accepted by S. Raghavan, Area Editor for Network Optimization: Algorithms & Applications. Funding: This research was supported by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office.

Keywords

Algorithms
Interval scheduling
Lock scheduling
lock scheduling
algorithms
interval scheduling

Access to Document

10.1287/ijoc.2018.0848

published versionFinal published version, 0.98 MBLicence: TAVERNE

Cite this

@article{eae3223f98984fa2b4460b052c0ffb0d,

title = "No-wait scheduling for locks",

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 = "Algorithms, Interval scheduling, Lock scheduling, lock scheduling, algorithms, interval scheduling",

author = "Ward Passchyn and Dirk Briskorn and F.C.R. Spieksma",

year = "2019",

doi = "10.1287/ijoc.2018.0848",

language = "English",

volume = "31",

pages = "413--428",

journal = "INFORMS Journal on Computing",

issn = "1091-9856",

publisher = "INFORMS Institute for Operations Research and the Management Sciences",

number = "3",

}

TY - JOUR

T1 - No-wait scheduling for locks

AU - Passchyn, Ward

AU - Briskorn, Dirk

AU - Spieksma, F.C.R.

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Algorithms

KW - Interval scheduling

KW - Lock scheduling

KW - lock scheduling

KW - algorithms

KW - interval scheduling

UR - https://www.scopus.com/pages/publications/85070397137

U2 - 10.1287/ijoc.2018.0848

DO - 10.1287/ijoc.2018.0848

M3 - Article

AN - SCOPUS:85070397137

SN - 1091-9856

VL - 31

SP - 413

EP - 428

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

IS - 3

ER -

No-wait scheduling for locks

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this