ORDINAL ALGORITHMS FOR PARALLEL MACHINE SCHEDULING

The minimization of maximum completion time for scheduling n jobs on m identical parallel machines is an NP-hard problem for which many exce llent heuristic algorithms have been developed. In this paper, the pro blem is investigated under the assumption that only limited informatio n about the jobs is available. Specifically, processing times are not known for the jobs; rather, the ordering of the jobs by processing tim e is known. For the cases of two and three parallel machines, algorith ms which cannot be improved upon with respect to worst case performanc e ratio are developed. For the case of four parallel machines, an algo rithm which is near optimal with respect to worst case performance rat io is developed. For arbitrary ill, an algorithm which produces soluti ons whose value is al most five-thirds times the optimal value is pres ented. Finally, it is shown that as the number of machines gets arbitr arily large, the best possible ordinal algorithm has worst case perfor mance ratio of at least 3/2.