This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  ALL, with author Dell'Olmo P., in the category IASI Research Reports (or show them all):

---

IASI Research Report n. 359  (Previous    Next) 


Dell'Olmo P., Speranza M.G., Tuza Zs.

Easy and hard cases of a scheduling problem on three dedicated processors

ABSTRACT

A set of tasks has to be scheduled on three processors and each task requires that a specified set of the processors be simultaneously available for a given processing time. The objective of the problem is to determine a nonpreemptive schedule with minimum makespan. In this paper a simpler proof of a known set of conditions which identify polynomial instances is given, based on a graph theoretical formulation of the problem and it is shown that, under a certain (uniform) probability distribution on the problem instances, more than 95% of the instances can be solved in polynomial time when the number of tasks grows to infinity. For the hard cases, the SPT and LPT heuristics are not effective for this problem, with a tight worst case relative error of 3. On the contrary, it is shown that the relative error produced by a simple heuristic, which schedules tasks requiring the same set of processors consecutively, is bounded by 5/4. This result improves the bound of 4/3 given by Blazewicz et al (1992) and the improved bound is shown to be tight.