Narrow Results

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³log² n) for parallel and identical processors and O(kn²) for a single processor, where k is the number of distinct w-weights.

In this paper, we consider two single-processor online scheduling problems with an unexpected breakdown. Speaking specifically, there is a group of nonresumable jobs being processed on the single processor. Note that the breakdown will emerge on the processor suddenly, which signifies that its beginning time and its length are unknown in advance. In this study, we are interested in scheduling the jobs so as to minimize the maximum weighted completion time. Most noticeably, when all jobs respect an agreeable condition, i.e., for each two jobs $J_a$ and $J_b$, $w_a\ge w_b$ means that $p_a\ge p_b$, we design an optimal online algorithm. In addition, for the general version, we propose an online algorithm with a competitive ratio of at most 2.