RANDOMIZED ONLINE ALGORITHMS FOR MAXIMIZING BUSY TIME-INTERVAL SCHEDULING

We consider the problem of scheduling tasks requiring certain processi ng times on one machine so that the busy time of the machine is maximi zed. The problem is to find a probabilistic online algorithm with reas onable worst case performance ratio. We answer an open problem of Lipt on and Tompkins concerning the best possible ratio that can be achieve d. Furthermore, we extend their results to an m-machine analogue. Fina lly, a variant of the problem is analyzed, in which the machine is pro vided with a buffer to store one job.