An optimal online algorithm for scheduling with general machine cost functions

We present two deterministic online algorithms for the problem of scheduling with a general machine cost function. In this problem, every machine has a cost that is given by a nonnegative cost function, and the objective function is the sum of makespan and the cost of the purchased machines. In previous work by Imreh, it was shown that no deterministic algorithm has competitive ratio below 2, and an algorithm whose competitive ratio does not exceed (3+5)/2≈2.618\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(3+\sqrt{5})/2 \approx 2.618$$\end{document} was presented. Our first algorithm imitates an optimal offline solution with respect to the number of machines used, and we show that its competitive ratio is exactly 2.5. Then, we modify our algorithm by imitating a preemptive optimal offline solution instead of a non-preemptive one. This leads to the design of a 2-competitive algorithm, which is the best possible.