Time-constrained project scheduling

T.A. Guldemond, Johann L. Hurink, J.J. Paulus, Johannes M.J. Schutten

Research output: Contribution to journalArticleAcademicpeer-review

25 Citations (Scopus)
58 Downloads (Pure)

Abstract

We study the Time-Constrained Project Scheduling Problem (TCPSP), in which the scheduling of activities is subject to strict deadlines. To be able to meet these deadlines, it is possible to work in overtime or hire additional capacity in regular time or overtime. For this problem, we develop a two stage heuristic. The key of our approach lies in the first stage in which we construct partial schedules with a randomized sampling technique. In these partial schedules, jobs may be scheduled for a shorter duration than required. The second stage uses an ILP formulation of the problem to turn a partial schedule into a feasible schedule, and to perform a neighbourhood search. The developed heuristic is quite flexible and, therefore, suitable for practice. We present experimental results on modified RCPSP benchmark instances. The two stage heuristic solves many instances to optimality, and if we substantially decrease the deadline, the rise in cost is only small.
Original languageUndefined
Article number10.1007/s10951-008-0059-7
Pages (from-to)137-148
Number of pages12
JournalJournal of scheduling
Volume2008
Issue number11
DOIs
Publication statusPublished - 2008

Keywords

  • EWI-12284
  • METIS-246949
  • IR-64724

Cite this

Guldemond, T. A., Hurink, J. L., Paulus, J. J., & Schutten, J. M. J. (2008). Time-constrained project scheduling. Journal of scheduling, 2008(11), 137-148. [10.1007/s10951-008-0059-7]. https://doi.org/10.1007/s10951-008-0059-7
Guldemond, T.A. ; Hurink, Johann L. ; Paulus, J.J. ; Schutten, Johannes M.J. / Time-constrained project scheduling. In: Journal of scheduling. 2008 ; Vol. 2008, No. 11. pp. 137-148.
@article{a21f61a68c4a4efe8fb37e95e344b5bd,
title = "Time-constrained project scheduling",
abstract = "We study the Time-Constrained Project Scheduling Problem (TCPSP), in which the scheduling of activities is subject to strict deadlines. To be able to meet these deadlines, it is possible to work in overtime or hire additional capacity in regular time or overtime. For this problem, we develop a two stage heuristic. The key of our approach lies in the first stage in which we construct partial schedules with a randomized sampling technique. In these partial schedules, jobs may be scheduled for a shorter duration than required. The second stage uses an ILP formulation of the problem to turn a partial schedule into a feasible schedule, and to perform a neighbourhood search. The developed heuristic is quite flexible and, therefore, suitable for practice. We present experimental results on modified RCPSP benchmark instances. The two stage heuristic solves many instances to optimality, and if we substantially decrease the deadline, the rise in cost is only small.",
keywords = "EWI-12284, METIS-246949, IR-64724",
author = "T.A. Guldemond and Hurink, {Johann L.} and J.J. Paulus and Schutten, {Johannes M.J.}",
note = "DOI 10.1007/s10951-008-0059-7",
year = "2008",
doi = "10.1007/s10951-008-0059-7",
language = "Undefined",
volume = "2008",
pages = "137--148",
journal = "Journal of scheduling",
issn = "1094-6136",
publisher = "Springer",
number = "11",

}

Guldemond, TA, Hurink, JL, Paulus, JJ & Schutten, JMJ 2008, 'Time-constrained project scheduling', Journal of scheduling, vol. 2008, no. 11, 10.1007/s10951-008-0059-7, pp. 137-148. https://doi.org/10.1007/s10951-008-0059-7

Time-constrained project scheduling. / Guldemond, T.A.; Hurink, Johann L.; Paulus, J.J.; Schutten, Johannes M.J.

In: Journal of scheduling, Vol. 2008, No. 11, 10.1007/s10951-008-0059-7, 2008, p. 137-148.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Time-constrained project scheduling

AU - Guldemond, T.A.

AU - Hurink, Johann L.

AU - Paulus, J.J.

AU - Schutten, Johannes M.J.

N1 - DOI 10.1007/s10951-008-0059-7

PY - 2008

Y1 - 2008

N2 - We study the Time-Constrained Project Scheduling Problem (TCPSP), in which the scheduling of activities is subject to strict deadlines. To be able to meet these deadlines, it is possible to work in overtime or hire additional capacity in regular time or overtime. For this problem, we develop a two stage heuristic. The key of our approach lies in the first stage in which we construct partial schedules with a randomized sampling technique. In these partial schedules, jobs may be scheduled for a shorter duration than required. The second stage uses an ILP formulation of the problem to turn a partial schedule into a feasible schedule, and to perform a neighbourhood search. The developed heuristic is quite flexible and, therefore, suitable for practice. We present experimental results on modified RCPSP benchmark instances. The two stage heuristic solves many instances to optimality, and if we substantially decrease the deadline, the rise in cost is only small.

AB - We study the Time-Constrained Project Scheduling Problem (TCPSP), in which the scheduling of activities is subject to strict deadlines. To be able to meet these deadlines, it is possible to work in overtime or hire additional capacity in regular time or overtime. For this problem, we develop a two stage heuristic. The key of our approach lies in the first stage in which we construct partial schedules with a randomized sampling technique. In these partial schedules, jobs may be scheduled for a shorter duration than required. The second stage uses an ILP formulation of the problem to turn a partial schedule into a feasible schedule, and to perform a neighbourhood search. The developed heuristic is quite flexible and, therefore, suitable for practice. We present experimental results on modified RCPSP benchmark instances. The two stage heuristic solves many instances to optimality, and if we substantially decrease the deadline, the rise in cost is only small.

KW - EWI-12284

KW - METIS-246949

KW - IR-64724

U2 - 10.1007/s10951-008-0059-7

DO - 10.1007/s10951-008-0059-7

M3 - Article

VL - 2008

SP - 137

EP - 148

JO - Journal of scheduling

JF - Journal of scheduling

SN - 1094-6136

IS - 11

M1 - 10.1007/s10951-008-0059-7

ER -