New Task Domain Propagators with Polynomial Complexity for Resource-Constrained Project Scheduling Problem

Dmitry ARKHIPOV, Olga BATTAÏA, Alexander LAZAREV, German TARASOV, Ilia TARASOV

Abstract


We consider a classic Resource-Constrained Project Scheduling Problem (RCPSP) which is known to be NP-hard. For defined project deadline T , each task of the project can be associated with its temporal domain – a time interval in which this task can be processed. In this research, we adopt existing resource-based methods of task domain propagation to generalized statement with time-dependent resource capacity and show how to improve its propagation efficiency. We also present new polynomial-time algorithms (propagators) to tighten such temporal task domains in order to make the optimization problem easier to solve. Moreover, we show how these propagators can be used to calculate lower bound on project makespan.

Keywords


Project scheduling, Constraint programming, Scheduling, RCPSP, Task domain propagator


DOI
10.12783/dtcse/optim2018/27917

Full Text:

PDF

Refbacks

  • There are currently no refbacks.