In this paper, the problem of scheduling independent tasks with bottleneck resource constraints is investigated. There is a set of independent tasks $\mathcal{T} = \{T_{1}, \dotsc , T_{n}\}$ and a set of resources $\mathcal{R} = \{R_{1}, \dotsc , R_{m}\}$. The available amount of resource $R_{j}$, for $j = 1, \dotsc , m$, is (normalized to) 1. Each task $T_{i}$’s execution requires at least $\lambda_{(i,j)} \leq 1$ units of resource $R_{j} \in \mathcal{R}$, and with these minimal resources, the execution time of $T_{i}$, is $\tau_{i}$. If there is a resource $R_{\beta (i)}$ so that $T_{i}$ can use $\xi$ units $(\xi \geq \lambda_{(i,\beta (j))})$ and reduce the execution time to $\frac{{\lambda _{(i,\beta (i))} }}{\xi }\tau _i $, we say that $T_{i}$ can achieve linear speed-up with respect to $R_{\beta (i)}$. It is assumed that for each $T_{i}$, there is one, and only one, resource $R_{\beta (i)}$ that is $T_{i}$’s bottleneck resource: $T_{i}$ can use $\xi$ units of ${R_{(i,\beta (i))} }$ and achieve linear speed-up, where $\xi$ is between $\lambda _{(i,\beta (i))}$ and $\Lambda _{(i,\beta (i))} \leq 1$. The problem is to find a feasible schedule for all the tasks in $\mathcal{T}$ that has a shortest overall makespan. This problem is a combination of two previously studied problems—scheduling tasks with resource constraints [SIAM J. Comput., 4 (1975), pp. 187–200.] scheduling parallel tasks [SIAM J. Comput., 21 (1992), pp. 281–294]. A variant of this problem was studied in [J. Combin. Theory, 21 (1976), pp. 257–298]. Because the problem is NP-hard, we propose the ECT (earliest completion time) algorithm as a heuristic solution and show that the performance ratio of the ECT makespan $M_{\text{ECT}}$ to the optimal makespan $M_{\text{OPT}}$ is bounded by $2l + m + 1$, where l is the number of the bottleneck resources in $\mathcal{R}$. When $l = 0$, this is exactly the performance bound shown by Garey and Graham in [SIAM J. Comput., 4 (1975), pp. 187–200].

This paper investigates the problem of nonreconfigurable, nonpreemptive scheduling of parallel tasks in a homogeneous system of processors. Given a task precedence graph where each task T may be executed on up to $\delta (T)$ processors, the problem is to find a schedule such that the makespan is minimized. A scheduling policy is nonreconfigurable if when more processors become available after a task T has been scheduled on p processors, $p < \delta (T)$, they cannot join the execution of task T. It is nonpreemptive if each task is executed without interruption until completion once the task has started execution. The problem of scheduling parallel tasks is NP-hard. The performance ratio of the makespan produced by the original list scheduling algorithm proposed by Graham [SIAM J. Appl. Math., 17 (1969), pp. 416–429] to the optimal makespan is $\Delta + \frac{m - \Delta} {m}$ [Inform. Process. Lett., 37 (1991), pp. 291–297], where m and $\Delta $ are the number of processors in the system and the maximum degree of parallelism in any task, respectively. To provide a performance improvement, the Earliest Completion Time (ECT) algorithm is proposed; it is also shown that its performance ratio is bounded by $3-\frac{2}{m}$. In addition, an example is presented to demonstrate that the bound is at least 2.5.