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
Place of PublicationEnschede
PublisherUniversity of Twente, Research School for Operations Management and Logistics (BETA)
Number of pages16
Publication statusPublished - 2006

Publication series

NameBETA publicaties. Preprints
PublisherBeta Research School for Operations Management and Logistics, University of Twente
No.WP-180
ISSN (Print)1386-9213

Keywords

  • METIS-238250
  • IR-63595
  • EWI-7618

Cite this

Guldemond, T. A., Hurink, J. L., Paulus, J. J., & Schutten, J. M. J. (2006). Time-Constrained Project Scheduling. (BETA publicaties. Preprints; No. WP-180). Enschede: University of Twente, Research School for Operations Management and Logistics (BETA).
Guldemond, T.A. ; Hurink, Johann L. ; Paulus, J.J. ; Schutten, Johannes M.J. / Time-Constrained Project Scheduling. Enschede : University of Twente, Research School for Operations Management and Logistics (BETA), 2006. 16 p. (BETA publicaties. Preprints; WP-180).
@book{b129d06d09e5466695dd37ea9c6e96c1,
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 = "METIS-238250, IR-63595, EWI-7618",
author = "T.A. Guldemond and Hurink, {Johann L.} and J.J. Paulus and Schutten, {Johannes M.J.}",
year = "2006",
language = "Undefined",
series = "BETA publicaties. Preprints",
publisher = "University of Twente, Research School for Operations Management and Logistics (BETA)",
number = "WP-180",
address = "Netherlands",

}

Guldemond, TA, Hurink, JL, Paulus, JJ & Schutten, JMJ 2006, Time-Constrained Project Scheduling. BETA publicaties. Preprints, no. WP-180, University of Twente, Research School for Operations Management and Logistics (BETA), Enschede.

Time-Constrained Project Scheduling. / Guldemond, T.A.; Hurink, Johann L.; Paulus, J.J.; Schutten, Johannes M.J.

Enschede : University of Twente, Research School for Operations Management and Logistics (BETA), 2006. 16 p. (BETA publicaties. Preprints; No. WP-180).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Time-Constrained Project Scheduling

AU - Guldemond, T.A.

AU - Hurink, Johann L.

AU - Paulus, J.J.

AU - Schutten, Johannes M.J.

PY - 2006

Y1 - 2006

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 - METIS-238250

KW - IR-63595

KW - EWI-7618

M3 - Report

T3 - BETA publicaties. Preprints

BT - Time-Constrained Project Scheduling

PB - University of Twente, Research School for Operations Management and Logistics (BETA)

CY - Enschede

ER -

Guldemond TA, Hurink JL, Paulus JJ, Schutten JMJ. Time-Constrained Project Scheduling. Enschede: University of Twente, Research School for Operations Management and Logistics (BETA), 2006. 16 p. (BETA publicaties. Preprints; WP-180).