Ordinal algorithms for parallel machine scheduling

Ordinal algorithms for parallel machine scheduling

0.00 Avg rating0 Votes
Article ID: iaor19971844
Country: Netherlands
Volume: 18
Issue: 5
Start Page Number: 223
End Page Number: 232
Publication Date: Mar 1996
Journal: Operations Research Letters
Authors: , ,
Abstract:

The minimization of maximum completion time for scheduling n jobs on m identical parallel machines is an NP-hard problem for which many excellent heuristic algorithms have been developed. In this paper, the problem is investigated under the assumption that only limited information about the jobs is available. Specifically, processing times are not known for the jobs; rather, the ordering of the jobs by processing time is known. For the cases of two and three parallel machines, algorithms which cannot be improved upon with respect to worst case performance ratio are developed. For the case of four parallel machines, an algorithm which is near optimal with respect to worst case performance ratio is developed. For arbitrary m, an algorithm which produces solutions whose value is at most five-thirds times the optimal value is presented. Finally, it is shown that as the number of machines gets arbitrarily large, the best possible ordinal algorithm has worst case performance ratio of at least 3/2.

Reviews

Required fields are marked *. Your email address will not be published.