Experimental analysis of online algorithms for the bicriteria scheduling problem ?
In this paper, we experimentally evaluate the performances of some natural online algorithms for the bicriteria version of the classical Graham's scheduling problem. In such a setting, jobs are characterized by a processing time and a memory size. Every job must be scheduled on one of the m processors so as to minimize the time makespan and the maximum memory occupation per processor simultaneously. We consider four fundamental classes of algorithms obtained by combining known single-criterion algorithms according to different strategies. The performances of such algorithms have been evaluated according to real world sequences of jobs and to sequences generated by fundamental probability distributions. As a conclusion of our investigation, three particular algorithms have been identified that seem to perform significantly better than the others. One has been presented in Bil et al. (18th International Parallel and Distributed Processing Symposium (IPDPS), IEEE Press, New York) and is the direct bicriteria extension of the basic Graham's greedy algorithm, while the other ones are given by two different combinations of the Graham's algorithm and the Albers' algorithm proposed in Albers (SIAM J. Comput. 29(2) (1999) 459).
online scheduling bicriteria optimization experimental performance evaluation