• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Препринт

On Lower and Upper Bounds for the Resource-Constrained Project Scheduling Problem

Gafarov E., Lazarev A. A., Werner F.
Problem RCPSP may be formulated as follows. Given a set $N=\{1,\dots,n\}$ of jobs. A constant amount (quantity) of $Q_k>0$ units of resource $k, k=1,\dots,K,$ is available at any time. Job $j\in N$has to be processed for $p_j\geq 0$ time units without preemption. During this period, a constant amount (quantity) of $q_{jk} \geq 0$ units of resource $k$ is occupied. Fur the rmore, finish-start precedence relations $i \rightarrow j$ are defined between the jobs according to an acyclic directed graph $G.$ The objective is to determine the starting times $S_j$ for each job $j=1,\dots,n,$ in such a way that: at each time $t$, the total resource demand is less than or equal to the resource availability for each resource type the given precedence constraints arefulfilled the makespan $C_{max} = \max_{j=1}^n C_j$, where $C_j=S_j+p_j,$ is minimized.