Randomized online algorithms for maximizing busy time interval scheduling

doi:10.1007/BF02309339

Randomized online algorithms for maximizing busy time interval scheduling

1996-06-01

11

PRE

AI

DOI：10.1007/BF02309339

原文链接

原文求助

摘要

En 中文

We consider the problem of scheduling tasks requiring certain processing times on one machine so that the busy time of the machine is maximized. The problem is to find a probabilistic online algorithm with reasonable worst case performance ratio. We answer an open problem of Lipton and Tompkins concerning the best possible ratio that can be achieved. Furthermore, we extend their results to an m-machine analogue. Finally, a variant of the problem is analyzed, in which the machine is provided with a buffer to store one job.

Keyword:

probabilistic algorithm

online scheduling

interval

busy time

Randomized online algorithms for maximizing busy time interval scheduling

摘要

期刊

机构

引用论文