부산대학교 도서관

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jpdc.2005.07.006 Byline: Vittorio BilA[sup.2], Michele Flammini, Luca Moscardelli Abstract: In this paper, we consider the online bicriteria version of the classical Graham's scheduling problem in which two cost measures must be simultaneously minimized. We present a parametric family of online algorithms F.sub.m={A.sub.k|1a[c]1/2ka[c]1/2m}, such that, for each fixed integer k, A.sub.k is (2m-k/m-k+1,m+k-1/k)-competitive. Then we prove that, for m=2 and 3, the tradeoffs on the competitive ratios realized by the algorithms in F.sub.m correspond to the Pareto curve, that is they are all and only the optimal ones, while for m3 they give an r-approximation of the Pareto curve with r=5/4 for m=4, r=6/5 for m=5, r=1.186 for m=6 and so forth, with r always less than 1.295. Unfortunately, for m3, obtaining Pareto curves is not trivial, as they would yield optimal algorithms for the single criterion case in correspondence of the extremal tradeoffs. However, the situation seems more promising for the intermediate cases. In fact, we prove that for 5 processors the tradeoff (7/3,7/3) of A.sub.3[member of]F.sub.5 is optimal. Finally, we extend our results to the general d-dimensional case with corresponding applications to the Vector Scheduling problem. Author Affiliation: Dipartimento di Informatica, Universita di L'Aquila, Via Vetoio loc. Coppito, I-67100 L'Aquila, Italy Article History: Received 17 December 2004; Accepted 12 July 2005 Article Note: (footnote) [star] Work supported by the IST Programme of the EU under Contract No. IST-1999-14186 (ALCOM-FT), by the EU RTN project ARACNE, by the Italian Research Project REAL-WINE, partially funded by the Italian Ministry of Education, University and Research and by the Italian CNR project CNRG003EF8.