Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM RESOURCE CONSTRAINED SCHEDULING

• INSTANCE: Set T of tasks each having length l(t), number m of processors, number r of resources, resource bounds $b_i$, $1 \leq i \leq r$, and resource requirement $r_i(t)$, $0 \leq r_i(t) \leq b_i$, for each task t and resource i.

• SOLUTION: An m processor schedule for T that obeys the resource constraints, i.e., a function $f : T \rightarrow Z$ such that for all $u \leq 0$, if S(u) is the set of tasks t for which $f(t) \leq u < f(t)+l(t)$, then $\vert S(u)\vert \leq m$ and for each resource i
  
  $$\sum_{t \in S(u)}r_i(t) \leq b_i.$$
  
  

• MEASURE: The makespan of the schedule, i.e., $\max_{t \in T}(f(t)+l(t))$.

  
  

• Good News: Approximable within 2 [181].

• Comment: Note that the restriction in which there is only one resource, i.e., the available processors, is identical to minimizing the makespan of the schedule of parallel tasks on m processors. In this case, minimizing the average response time, i.e., $\frac{1}{\vert T\vert }\sum_{t \in T}(f(t)+l(t))$ is approximable within 32 [454]. The further variation in which each task can be executed by any number of processors and the length of a task is a function of the number of processors allotted to it is also approximable [363]. Variation in which every task is of length 1 and has an integer ready-time, which means that it cannot be processed before its ready-time, is approximable [448].

• Garey and Johnson: SS10