Ordinal on-line scheduling for maximizing the minimum machine completion time (Q1598882)

The article treats a parallel machine scheduling problem with \(m\) parallel machines and the objective of maximizing the minimal completion time. The data (job processing times) are not known in advance, only the order of the job processing times is known -- \(p1\geq p2\geq p3\geq\cdots\geq pn\). In the first part of the article an overview about ordinal scheduling and competitive analysis is presented with several references. Competitive analysis provides bounds for the performance of the solution computed only by using the ordinal information compared with the optimal solution using full information about the job processing times. In the following sections lower bounds are computed and an ordinal algorithm is developed for the stated problem. The competitive ratio reaches asymptotically \(O(\ln m)\) for a large number of machines \(m\).