Publications of Vincenzo Bonifaci

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  2015, with author Bonifaci V., in the category IASI Research Reports (or show them all):


IASI Research Report n. 15-03  (Next)


Vincenzo Bonifaci, D'Angelo G., Marchetti Spaccamela A.

Hierarchical and semi-partitioned machine scheduling

ABSTRACT
We propose a new model for scheduling jobs in a parallel machine setting that takes into account the cost of migrations by assuming that the processing time of a job may depend on the specific set of machines among which the job is migrated. For the makespan minimization objective, the model generalizes well-known scheduling problems such as R||Cmax and P|pmtn|Cmax, as well as novel problems such as semi-partitioned and clustered scheduling. In the case of a k-level hierarchical family of machines, we prove an upper bound on the approximation ratio of the problem equal to 1 + Hk, where Hk is the kth harmonic number. When k = 2, an improved upper bound of 2 + 1/m is provided, where m is the number of machines.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -