An algorithm for online scheduling across multiple connected machines is described in this paper. This algorithm maximizes the total job length of all jobs completed before their deadline, as opposed to some other metric, like maximizing the total of the differences between the deadlines and the actual finish times. The domain of this problem is that of nonpreemptive jobs, whereas most of the work in this area has been done on preemptive jobs.

The algorithm is relatively easy to understand, and is clearly presented. It is a matter of seeing if the job can be scheduled on the current machine. If it cannot, a new current machine is selected that meets a couple of simple criteria related to the slack time of the job. For slack ratio k, and m machines, the algorithm is shown to be (m+1+m·k^{-1/m})-competitive, by way of a theorem proven in the text.

The incorrect usage of English grammar in the paper is a little distracting, but does not detract from its clarity, although, in the formal problem statement, the word “minimum” is used when “maximum” is clearly meant. The paper describes other approaches to this problem, but doesn’t provide much background information about the problem itself. This may be because this paper is an abstract of all the work that has been done on this project.