The problem of competitive on-line scheduling in two-processor real-time environments is studied. The model of Koren and Shasha is followed: Every task has a deadline and a value that it obtains only if it completes b...
详细信息
The problem of competitive on-line scheduling in two-processor real-time environments is studied. The model of Koren and Shasha is followed: Every task has a deadline and a value that it obtains only if it completes by its deadline - the value being its computation time. The goal is to design, on-line schedulers with worst-case guarantees compared with a clairvoyant scheduler. Koren and Shasha gave algorithms for the migration and no-migration models, with competitive multipliers of 2 and 3, respectively. In this article, we give an algorithm for the no-migration model with an improved competitive multiplier of 2(1 + 1/root6). We also show that the competitive multiplier for the migration model can be lowered by using a fast processor and a slow processor, compared with using several parallel and identical processors with the same aggregate computing power.
We consider a hierarchical optimization problem for imprecise computation tasks, where each task is weighted with two weights, w and w'. The primary criterion is to minimize the total w-weighted error of all optio...
详细信息
We consider a hierarchical optimization problem for imprecise computation tasks, where each task is weighted with two weights, w and w'. The primary criterion is to minimize the total w-weighted error of all optional parts of tasks and the secondary criterion is to minimize the maximum w-weighted error. An algorithm is given with time complexity O(kn(3) log(2)n) for parallel and identical processors and O(kn(2)) for a single processor, where k is the number of distinct w-weights.
A fundamental problem in scheduling theory is that of scheduling a set of n tasks, with precedence constraints, on m >= 1 identical and parallelprocessors so as to minimize the makespan ( schedule length). In the ...
详细信息
A fundamental problem in scheduling theory is that of scheduling a set of n tasks, with precedence constraints, on m >= 1 identical and parallelprocessors so as to minimize the makespan ( schedule length). In the past, research has focused on the setting whereby all tasks are available for processing at the beginning (i.e., at time t = 0). In this article we consider the situation where tasks, along with their precedence constraints, are released at different times, and the scheduler has to make scheduling decisions without knowledge of future releases. In other words, the scheduler has to schedule tasks in an online fashion. We consider both preemptive and nonpreemptive schedules. We show that optimal online algorithms exist for some cases, while for others it is impossible to have one. Our results give a sharp boundary delineating the possible and the impossible cases.
暂无评论