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. 383  (Previous    Next) 


Bianco L., Dell'Olmo P., Giordani S.

An exact algorithm for the minimization of additional resources cost in scheduling tasks with fixed completion time

ABSTRACT

We consider the problem of scheduling a set of independent tasks within a given time limit in order to minimize the cost of required resources. Tasks have different processing times and are non-preemptable (i.e. cannot be interrupted and restarted later). Each task requires a set of dedicated processors and some additional resources of different costs simultaneously available for its processing. Given a fixed set of processors and unlimited resources availability, the problem is to find the minimum resources cost schedule respecting the time constraint. We study this problem by means of a graph model which represents compatibilities between tasks, as that of finding the optimal reduction to an interval graph. Results show that dominant schedules correspond to a family of graphs which is contained in the constraints structure of the problem. A dynamic programming algorithm that finds an optimal graph in that family is described. The search is performed by dynamically updating a data structure (MPQ-tree) which allows at each step of the process to obtain maximum completion time and performances of a large class performance equivalent schedules. Computational results on a set of randomly generated test problems are discussed.