Narrow Results

Parallel programs may be represented as a set of interrelated sequential tasks. When multiprocessors are used to execute such programs, the parallel portion of the application can be speeded up by an appropriate allocation of processors to the tasks of the application. Given a parallel application defined by a task precedence graph, the goal of task scheduling (or processor assignment) is thus the minimization of the makespan of the application. In a heterogeneous multiprocessor system, task scheduling consists of determining which tasks will be assigned to each processor, as well as the execution order of the tasks assigned to each processor. In this work, we apply the tabu search metaheuristic to the solution of the task scheduling problem on a heterogeneous multiprocessor environment under precedence constraints. The topology of the Mean Value Analysis solution package for product form queueing networks is used as the framework for performance evaluation. We show that tabu search obtains much better results, i.e., shorter completion times, improving from 20 to 30% the makespan obtained by the most appropriate algorithm previously published in the literature.

We consider the problem of preemptively scheduling n independent jobs {J₁, J₂, …, J_n} on m parallel machines {M₁, M₂, …, M_m}, where each job J_j can only be processed on a prespecified subset of machines called its processing set. The machines are linearly ordered, and the processing set of J_j is specified by two machine indexes a_j and b_j; i.e., . The processing sets are nested; i.e., for i ≠ j, we have , or , or . Our goal is to minimize the makespan. We first give an O(n log n)-time algorithm to find an optimal schedule. We then give an O(mn + n log n)-time algorithm to find a maximal schedule, where a schedule is said to be maximal if it processes as much work as any other schedule in any time interval [0, t], t > 0.