Narrow Results

In this paper, we consider a semi-online preemptive scheduling problem on two uniform machines, where we assume that all jobs have sizes between p and rp for some p > 0 and r ≥ 1. The goal is to maximize the continuous period of time (starting from time zero) when both machines are busy. We present an optimal semi-online algorithm for any combination of the job size ratio r and machine speed ratio s.

This paper investigates two different semi-online versions of the machine covering, which is the problem of assigning a set of jobs to a system of m(m ≥ 3) identical parallel machines so as to maximize the earliest machine completion time. In the first case, we assume that the largest processing times is known in advance. In the second case, we assume that the total processing times of all jobs is known in advance. For each version we propose a semi-online algorithm and investigate its competitive ratio. The competitive ratio of each algorithm is , which is shown to be the best possible competitive ratio for each semi-online problem.

This paper investigates semi-online hierarchical scheduling problems on two identical machines, with the purpose of minimizing the $l_p$-norm of the machines’ loads. We consider two semi-online versions with knowing the total processing time $T$ of all jobs, or knowing the total processing time $T_i$ of the jobs of hierarchy $i$ for $i=1,2$ in advance. For the two semi-online versions, the best possible online algorithms are designed with competitive ratios of ${\phi }^{\ast }$ and $\left(\right.\frac{2^p+4^p}{2{(3)}^p}{\left)\right.}^{\frac{1}{p}}$, respectively, where ${\phi }^{\ast }$ is the maximum value of the function $\phi (x)=\left(\right.\frac{{(x+\frac{1}{2}(1-x))}^p+{(\frac{1}{2}(1-x))}^p}{x^p+{(1-x)}^p}{\left)\right.}^{\frac{1}{p}}$ in $x\in [\frac{1}{2},1]$. When $p=\infty$, our results cover the known results for minimizing the makespan.

Task scheduling between edge devices and remote servers is a common application scenario in edge computing or cloud computing, also known as computational offloading. A reasonable scheduling strategy can effectively shorten task completion time, reduce energy consumption, and improve user experience. However, the traditional offline task scheduling algorithm is NP-hard, and the decision requires obtaining all the information of the task and the device (such as task computing amount, data amount, device computing resources, etc.), which is challenging to meet in practical applications. The semi-online algorithm describes the task scheduling method when the system cannot obtain all the information. In this paper, we propose an Efficient Semi-online algorithm for Multi-users task offloading (ESaM), which includes two specific implementations: ESaM-I as known server-side idle time, and ESaM-O for known task computing amount. Because ESaM-I has obtained server information, it is better than ESaM-O in performance for most of the scenarios. The experimental results show that ESaM-I and ESaM-O are superior to the well-known semi-online scheduling algorithm SPaC in task completion time. As the remote processor computing ability increases, the average makespan converges to 0.875, 0.742, 0.782 for SPaC-M, ESaM-O, and ESaM-I in the simulation.

Online and semi-online scheduling problems on a single machine with an availability constraint are considered in this paper. The machine has one unavailable interval in which jobs cannot be processed. Preemption is not allowed. Jobs arrive over time. The objective is to minimize makespan. First we discuss the online version of the problem. After giving its lower bound, we prove that Earliest Release Date (ERD) algorithm is an optimal algorithm. Then we study some semi-online problems in which the largest processing time, the total processing time, the largest release date, or the optimal makespan is known in advance. For these semi-online problems, we give their lower bounds, design semi-online algorithms and prove their competitive ratios, respectively.