Online scheduling on a single machine with one restart for all jobs to minimize the weighted makespan

1.   Introduction

In this paper, we consider the online scheduling problem with restarts on a single machine, with the aim of minimizing the weighted makespan, which refers to the maximum weighted completion time of the jobs. For the majority of online scheduling problems, no online algorithm can generate a solution that is equally effective as an offline optimal solution because in the online scheduling, the exact data of each job is unknown until it arrives. In the offline scheduling, the decision maker could make better decisions since all information about the jobs are given in advance. The arrival of jobs can be categorized into two groups in online scheduling: Over time and over list. Jobs arriving over time means that each job has an arrival time, after which it can be processed, and the online algorithm does not have to schedule this job immediately. Jobs arriving over list means that the next job arrives after the current job has been scheduled on the machine. In this paper, all jobs arrive over time.

As far as we know, the concept of restarts was first proposed for online scheduling by Akker et al. ^[1]. Restart (Hoogeveen et al. ^[2]) means that a job being processed is interrupted and loses all the work already done on it. In other words, the processing time previously spent on the job is wasted. The interrupted job then becomes available again as an unprocessed job, which can be subsequently processed and restarted, and we call it a restarted job. As further jobs arrive over time, we obtain more information about the job instance. Allowing restarts actually prevents us from making wrong decisions, since we have the opportunity to reconsider the schedule. However, frequent restarts can result in resource waste and harm jobs in practice. "Limited restart" was first proposed by Fu et al. ^[3], in which "limited restart" means that each job can be restarted only once, and "$k$-limited restart" supposes that each job cannot be interrupted more than $k$ times, where $k$ can be either a positive integer or infinity. Different from the definition of "$k$-limited restart, " the problem we investigate in this paper is "1-restart", which means that the total number of restarts allowed for all jobs is 1.

A common approach for assessing the performance of an online algorithm is usually to calculate and analyze its competitive ratio. Assuming that the instance of an online scheduling problem under consideration is $I$, and $\mathcal A(I)$ is the objective function value obtained by running Algorithm $\mathcal A$, $OPT(I)$ signifies the offline optimal objective value. For the minimization problem, we say that Algorithm $\mathcal A$ is $\rho$-competitive if the inequality $\mathcal A(I)\leq \rho OPT(I)$ holds. That is, once an online algorithm can generate a schedule whose objective value is not lower than $\rho$ times the value of the offline optimal schedule, it will be considered as a $\rho$-competitive algorithm. The infimum of $\rho$ is regarded as the competitive ratio of Algorithm $\mathcal A$. For the online scheduling problem considered in our paper, the competitive ratio of the algorithm is the minimum value of $\rho$ such that it is $\rho$-competitive. Moreover, an online algorithm is the best possible if no algorithm can be discovered that possesses a smaller competitive ratio than it does.

Roughly speaking, over the past few decades, there has been a wealth of researches on restarts in the field of online scheduling. In the model of parallel batch machine, Liu et al. ^[4] studied the online scheduling problem with "$k$-limited restart" on a bounded parallel batch machine with the goal of minimizing the makespan, and the jobs are equal in length. Depending on the capacity of the parallel batch, they presented the best possible online algorithm for the corresponding problem when $k\geq1$. Furthermore, Liu et al. ^[5] investigated the online scheduling problem on an unbounded parallel batch machine with "limited restart", and the delivery time of each job is no longer than its processing time. The goal is to minimize the transportation completion time. They provided the best possible online algorithm with a competitive ratio of $\frac{3}{2}$. For the problem that minimizing the makespan using restarts on a parallel batch processing system, Fu et al. ^[6] showed that the lower bound is $\frac{5-\sqrt{5}}{2}$, and designed an online algorithm with a competitive ratio of $\frac{3}{2}$. The problem was further investigated and Yuan et al. ^[7] solved the gap and gave the best possible online algorithm. Additionally, for online scheduling problem on two parallel batch machines with "limited restart" to minimize the makespan, Fu et al. ^[8] presented the best possible online algorithm with a competitive ratio of $\frac{\sqrt{3}+1}{2}$ under the assumption of "second-restart". There are many other outcomes about restarts, details of which can be found in Tian et al. ^[9].

In certain service systems, it is imperative to keep service costs low. Hence, this paper draws inspiration from customers' desires for lower costs. Customers' orders often arrive at the service provider at any time in practice, and the system aims to minimize the highest service costs as low as possible for each client, so the online scheduling problem discussed in this paper that minimizes the weighted makespan may also be used to assess the expenses associated with work-in-progress inventory and customer satisfaction. Therefore, considering the issue that minimizes the weighted makespan is of clear interest. Actually, there are fruitful achievements focused on the objective that minimize the weighted makespan. Li ^[10] demonstrated that no deterministic online algorithm has a competitive ratio of less than 2. Moreover, for the problem on a single machine, he offered a 3-competitive algorithm. For the problem on parallel machines and jobs with identical processing times, Li ^[10] presented the best possible online algorithm. The gap in Li ^[10] was later solved by Chai et al. ^[11]. Lu et al. ^[12] considered the problem that minimizes the weighted makespan plus the rejection cost and demonstrated that the problem is NP-hard, as well as provided a 2-approximation algorithm. For the online scheduling problem on identical bounded parallel batch machines to minimize the maximum weighted makespan, and the jobs with the same processing time arrive over time, Li et al. ^[13] presented the best possible online algorithm with the competitive ratio of $\frac{\sqrt{5}+1}{2}$. Furthermore, they also gave the best possible online dense algorithm with a competitive ratio of 2. Sun ^[14] considered the single machine scheduling problem with rejection to minimize the weighted makespan, and showed that the problem is fixed-parameter tractable with respect to some parameters.

For convenience, we present some notations that will be used subsequently. The problem addressed in our paper may be written as $1| r_{j}, online, 1\mbox{-}restart |WC_{\max}$ and $1| r_{j}, online, p_{j} = p, 1\mbox{-}restart |WC_{\max}$, where $WC_{\max} = \max\{w_{j}C_{j}:J_{j}\in I\}$ if the job instance $I$ is given. Unless ambiguity would result, we simplify the objective values of an online algorithm and an optimal algorithm by $WC_{\rm on}(I)$ and $WC_{\rm opt}(I)$ for instance $I$, respectively. In addition, we use $C_{j}$ to stand for the completion time of job $J_{j}$. In order to distinguish the online scheduling with restarts from the offline scheduling, we denote the $i$-th starting time of job $J_{j}$ by $S_{ji}$. Furthermore, since only one restart is considered in this paper, we abbreviate $S_{j1}$ as $S_{j}$. Let $\varepsilon$ be an infinitely small positive number, and $\beta\approx 0.4656$ is the positive root of equation $x(1+x)^{2} = 1$.

Throughout this paper, in Section 2, we consider problem $1| r_{j}, online, 1\mbox{-}restart |WC_{\max}$ and prove that there is no online algorithm with a competitive ratio of less than 2, which matches the lower bound of the problem without restart. That is, "$1$-restart" is invalid for improving the competitive ratio of problem $1| r_{j}, online|WC_{\max}$. In Section 3, we provide the best possible online algorithm with a competitive ratio of $1+\beta\approx1.4656$ for problem $1| r_{j}, online, p_{j} = p, 1\mbox{-}restart |WC_{\max}$. Li ^[8] presented the best possible online algorithm with a competitive ratio of $\frac{1+\sqrt{5}}{2}\approx1.618$ for problem $1| r_{j}, online, p_{j} = p|WC_{\max}$, so in our paper, we improve the result in Li ^[8]. In Section 4, we summarize the results of this paper and present some problems that can be investigated in the future.

2.   The general case with the arbitrary processing times

In this section, we consider the problem $1| r_{j}, online, 1\mbox{-}restart |WC_{\max}$. For the online scheduling problem to minimize the weighted makespan, i.e., $1|r_{j}, online |WC_{\max}$, Chai et al. ^[11] gave two best possible online algorithms with a competitive ratio of 2 based on the preemptive optimal schedule and the concept of delay, respectively.

It is obvious that the competitive ratio of problem $1|r_{j}, online|WC_{\max}$ is likely to be improved with the use of restarts. Hence, for problem $1| r_{j}, online, 1\mbox{-}restart |WC_{\max}$, its competitive ratio may be less than or equal to 2. In the following, we demonstrate that the lower bound for problem $1|r_{j}, online, 1\mbox{-}restart |WC_{\max}$ is still 2, which means that "$1$-restart" does not lead to a better competitive ratio for problem $1|r_{j}, online|WC_{\max}$.

Theorem 1. For problem $1|r_{j}, online, 1\mbox{-}restart |WC_{\max}$, there is no online algorithm with a competitive ratio of less than 2.

Proof. For an arbitrary online algorithm $H$, we construct an online instance $I$, in which the jobs are presented by the adversary.

There are four jobs $J_{1}, J_{2}, J_{3}, J_{4}$ contained in $I$ and the jobs arrive in the non-decreasing order of weights, i.e., $w_{i}\leq w_{j}$ if job $J_{j}$ arrives after job $J_{i}$. We write $I_{m} = \{J_{j}:1\leq j\leq m\}$. At time $0$, job $J_{1}$ with processing time $1$ and weight $1$ comes, i.e., $(r_{1}, p_{1}, w_{1}) = (0, 1, 1)$.

Case 1. $S_{1}\geq1$.

If $S_{1}\geq1$, then no jobs arrive later. In this case, $WC_{\rm opt}(I_{1}) = w_{1}p_{1} = 1$ and the objective value of algorithm $H$ is $WC_{\rm on}(I_{1}) = w_{1}(S_{1}+1)\geq2 = 2WC_{\rm opt}$. Thus, in order to guarantee the competitive ratio, we assume that $S_{1} < 1$ in the following discussion.

Case 2. $S_{1} < 1$.

When algorithm $H$ processes job $J_{1}$ at time $S_{1}$, then job $J_{2}$ arrives at time $S_{1}+\varepsilon$, and $(r_{2}, p_{2}, w_{2}) = (S_{1}+\varepsilon, \varepsilon, M)$, where $M$ is a sufficiently large positive integer and $\varepsilon$ is a positive number that converges infinitely to $0$. In the following we discuss the scenarios according to the value of $S_{2}$. Note that $S_{1} < 2S_{1}+3\varepsilon\leq S_{1}+1$.

Case 2.1. $S_{2}\geq2S_{1}+3\varepsilon$.

If $S_{2}\geq2S_{1}+3\varepsilon$, then we have $WC_{\rm on}(I_{2})\geq w_{2}(S_{2}+p_{2}) = M(S_{2}+\varepsilon)$. In an optimal schedule, job $J_{2}$ has to be processed first at time $r_{2}$, then job ${J_{1}}$ is processed at the completion time of job $J_{2}$. So, we have $WC_{\rm opt}(I_{2}) = M(S_{1}+2\varepsilon)$, then we conclude that

Case 2.2. $S_{2} < 2S_{1}+3\varepsilon$.

We assume that $S_{2} < 2S_{1}+3\varepsilon\leq S_{1}+1$, then job $J_{3}$ arrives after jobs $J_{1}$ and $J_{2}$ are completed, i.e., $(r_{3}, p_{3}, w_{3}) = (S_{1}+2\varepsilon+1, M, M)$. In the following we discuss the scenarios according to the value of $S_{3}$.

Case 2.2.1. $S_{3}\geq M-1$.

If $S_{3}\geq M-1$, then no jobs arrive. Since all jobs are finished before job $J_{3}$ arrives, then we have $WC_{\rm on}(I_{3}) = w_{3}(S_{3}+p_{3})\geq w_{3}(M-1+M) = w_{3}(2M-1)$. However, for the instance $I_{3}$, the optimal schedule will process job $J_{3}$ at time $r_{3}$ and jobs $J_{1}$ and $J_{2}$ are finished before $r_{3}$. Thus, we have $WC_{\rm opt}(I_{3}) = w_{3}(r_{3}+p_{3}) = w_{3}(S_{1}+2\varepsilon+1+M)$. Furthermore,

when $M\rightarrow \infty, \ \varepsilon\rightarrow0^{+}$. As a result, we assume that $1 < r_{3} < S_{3} < M-1$ in the following discussion.

Case 2.2.2. $r_{3} < S_{3} < M-1$.

Once algorithm $H$ processes job $J_{3}$ at time $S_{3}$, job $J_{4}$ with processing time $\varepsilon$ and weight $2M^{2}$ comes at time $S_{3}+\varepsilon$, i.e., $(r_{4}, p_{4}, w_{4}) = (S_{3}+\varepsilon, \varepsilon, 2M^{2}).$ Due to the fact that all jobs are allowed to be restarted only once, then the processing of job $J_{3}$ cannot be interrupted. Therefore, job $J_{4}$ will be processed after the completion of job $J_{3}$ in algorithm $H$. We have $WC_{\rm on}(I_{4}) = \max\{w_{3}(S_{3}+p_{3}), w_{4}(S_{3}+p_{3}+\varepsilon)\} = w_{4}(S_{3}+p_{3}+\varepsilon) = 2M^{2}(S_{3}+M+\varepsilon)$. The optimal schedule for instance $I_{4}$ is to process all jobs in the order of $J_{2}, J_{1}, J_{4}, J_{3}$, and $WC_{\rm opt}(I_{4}) = \max\{w_{4}(S_{3}+2\varepsilon), w_{3}(S_{3}+p_{3}+2\varepsilon)\} = \max\{2M^{2}(S_{3}+2\varepsilon), M(S_{3}+M+2\varepsilon)\}$. Note that

thus, we have $WC_{\rm opt}(I_{4}) = 2M^{2}(S_{3}+2\varepsilon)$ and

when $M\rightarrow \infty, \ \varepsilon\rightarrow0^{+}$. This completes the proof of Theorem 1.

3.   A special case with the same processing time

In this section, we consider a special case of problem $1|r_{j}, online, 1\mbox{-}restart |WC_{\max}$, in which all jobs are of equal length. We denote the problem by $1|r_{j}, online, p_{j} = p, 1\mbox{-}restart |WC_{\max}$. Without loss of generality, it's feasible to consider the problem in which all jobs have the unit processing time. Thus, we study problem $1|r_{j}, online, p_{j} = 1, 1\mbox{-}restart |WC_{\max}$. For this problem, we present a lower bound of $1+\beta$, and the best possible online algorithm that matches the lower bound. For problem $1|r_{j}, online, p_{j} = p|WC_{\max}$, Li ^[10] gave the best possible online algorithm with a competitive ratio of $\frac{1+\sqrt{5}}{2}\approx1.618$. Hence we improve the result of Li ^[10] and this indicates that the competitive ratio of problem $1|r_{j}, online |WC_{\max}$ can be improved when all jobs have the same processing time and the number of restarts allowed for all jobs is 1.

3.1.   The lower bound

Recall that $\beta\approx0.4656$ is a positive real solution of equation $x(1+x)^{2} = 1$.

Theorem 2. There exists no online algorithm with a competitive ratio of less than $1+\beta$ for the scheduling problem $1|r_{j}, online, p_{j} = 1, 1\mbox{-}restart |WC_{\max}$.

Proof. By the contradiction, suppose that there exists an online algorithm $H$ with a competitive ratio of less than $1+\beta$. We consider the following job instance $I$ provided by the adversary.

At time $r_{1} = 0$, job $J_{1}$ with $w_{1} = 1$ arrives. Suppose that algorithm $H$ starts to process it at time $S_{1}$. In order to guarantee the competitive ratio of algorithm $H$, we discuss the value of $S_{1}$.

Case 1. $S_{1}\geq\beta$.

If $S_{1}\geq\beta$, then the adversary will inform us that no jobs arrive later, so $WC_{\rm opt} = w_{1}p_{1} = 1$ and $WC_{\rm on} = w_{1}C_{1} = S_{1}+p_{1}\geq1+\beta = (1+\beta)WC_{\rm opt}$.

Case 2. $S_{1} < \beta$.

In this case, job $J_{2}$ with $w_{2} = 2$ arrives at time $S_{1}+\varepsilon$. Suppose that algorithm $H$ starts to process it at time $S_{2}$.

Case 2.1. $S_{2}\geq S_{1}+1$.

If $S_{2}\geq S_{1}+1$, i.e., algorithm $H$ does not restart the job $J_{1}$, then no other jobs arrive. In this case, we have $WC_{\rm on} = w_{2}C_{2} = w_{2}(S_{2}+p_{2})\geq2(S_{1}+2)$. In the offline schedule, we can process job $J_{2}$ before job $J_{1}$ and $WC_{\rm opt}\leq \max\{w_{2}(r_{2}+p_{2}), w_{1}(r_{2}+p_{2}+p_{1})\} = \max\{2(S_{1}+\varepsilon+1), S_{1}+\varepsilon+2\} = 2(S_{1}+\varepsilon+1).$ Thus, we have

Case 2.2. $r_{2}\leq S_{2} < S_{1}+1 < 1+\beta$.

Consequently, in this case, algorithm $H$ restarts job $J_{1}$ at time $S_{2}$. In the following we discuss the scenarios according to the value of $S_{2}$.

Case 2.2.1. $S_{2}\geq (1+\beta)^{2}-1$.

If $S_{2}\geq (1+\beta)^{2}-1$, then no jobs appear subsequently because algorithm $H$ restarts job $J_{1}$ too late. Hence, we have $WC_{\rm on} = w_{2}C_{2} = w_{2}(S_{2}+p_{2})\geq2(1+\beta)^{2}$, and as mentioned above, $WC_{\rm opt}\leq2(S_{1}+\varepsilon+1)$. This implies that

Case 2.2.2. $r_{2}\leq S_{2} < (1+\beta)^{2}-1$.

If $r_{2}\leq S_{2} < (1+\beta)^{2}-1$, then job $J_{3}$ with $w_{3} = 4$ arrives at time $S_{2}+\varepsilon$. Job $J_{3}$ cannot start to be processed until job $J_{2}$ is completed, since all jobs are allowed to be restarted only once. Assume that the starting time of job $J_{3}$ under algorithm $H$ is $S_{3}$, then $S_{3} = S_{2}+1$ and $WC_{\rm on} = w_{3}C_{3} = 4(S_{2}+2)$. Note that the optimal schedule will process these jobs on the machine in the order of $J_{3}, J_{2}, J_{1}$, then by comparison, we can obtain $WC_{\rm opt} = 4(S_{2}+\varepsilon+1)$. Hence,

This completes the proof of Theorem 2.

3.2.   An online algorithm

In this subsection, we will present an online algorithm for problem $1|r_{j}, online, p_{j} = \; 1, \; 1\mbox{-}restart |WC_{\max}$ and analyze its competitive ratio.

In the present moment $t$, we use $U(t)$ to denote the set of jobs that have arrived but not yet been processed. Furthermore, if $U(t)\neq\emptyset$, we find the job with the largest weight in $U(t)$ and denote it as job $J_{k}$, i.e., $w_{k} = \max\{w_{j}:J_{j}\in U(t)\}$. The following algorithm $\mathcal{A}$ is provided to solve problem $1|r_{j}, online, p_{j} = 1, 1\mbox{-}restart |WC_{\max}$.

Algorithm $\mathcal{A}$

Step 1. Set $t: = \beta$ and the machine is idle in $[0, \beta)$.

Step 2. At time $t$, if $U(t)\neq\emptyset$ and the machine is idle, then schedule job $J_{k}$ non-preemptively on the machine. Otherwise, go to Step 4.

Step 3. In the time interval $(t, t+1)$, if no jobs arrive, then set $t : = t+1$ and go to Step 2. Otherwise, let $\mathcal{F}$ be the set of all jobs arrive in the time interval $(t, t+1)$, i.e., $\mathcal{F} = \{J_{j}\ |\ t < r_{j} < t+1\}$, then we write $r_{\min} = \min\{r_{j}\ |\ J_{j}\in \mathcal{F}\}$ and do the following:

Step 3.1. If $r_{\min} > (1+\beta)^2-1$, reset $t : = t+1$, go to Step 2.

Step 3.2. If $r_{\min}\leq (1+\beta)^2-1$, let $\tilde{\mathcal{F}} = \{J_{j}\ |\ t < r_{j}\leq(1+\beta)^2-1\}$. If there exists some jobs $J_{j}$ in $\tilde{\mathcal{F}}$ satisfying the condition $w_{j} > (1+\beta)w_{k}$, then find the job with the largest weight from these jobs and schedule it at time $(1+\beta)^2-1$, then go to Step 3. Otherwise, continue to process the job $J_{k}$ until it is completed, reset $t : = t+1$ and go to Step 2.

Step 4. If there are still some jobs arriving, set $t$ be the earliest arrival time of these jobs, go to Step 2. Otherwise, do nothing but wait.

From Algorithm $\mathcal{A}$, we have the following observations.

Observation 1. If job $i$ is restarted and job $i+1$ is processed at time $(1+\beta)^2-1$, then we write the job that is processed immediately after job $i+1$ as job $i+2$. If the arrival time of job $i+2$ is less than $\beta$, then job $i+2$ is job $i$. Otherwise, the arrival time of job $i+2$ is greater than $\beta$.

Observation 2. If the starting time of job $i$ satisfies that $S_{i} < (1+\beta)^2-1$, then we have $S_{i}\leq r_{i}+\beta$.

Theorem 3. For problem $1|r_{j}, online, p_{j} = 1, 1\mbox{-}restart |WC_{\max}$, algorithm $\mathcal{A}$ is the best possible online algorithm with the competitive ratio of $1+\beta$.

Proof. Let $\sigma$ be the schedule obtained by algorithm $\mathcal{A}$, $S_{j}(\sigma)$ and $C_{j}(\sigma)$ be the starting time and the completion time of job $J_{j}$, respectively. Denote the offline optimal schedule as $\pi$, and we can use $WC_{\rm on}$ and $WC_{\rm opt}$ to represent the objective function values of schedule $\sigma$ and $\pi$, respectively.

For each $j = 1, \cdots, n$, we assume that $J_{\sigma[j]}$ is the $j\mbox{-}$th completed job in schedule $\sigma$. Moreover, in the following proof, we can suppose that $J_{\sigma[k]}$ is the critical job that assumes the objective value of schedule $\sigma$. That is,

In schedule $\sigma$, let job $J_{\sigma[i]}$ with $1\leq i\leq k$ be the job with the smallest index such that jobs $J_{\sigma[i]}, \cdots, J_{\sigma[k]}$ are processed consecutively. Similarly, let $S_{\sigma[i]}(\sigma)$ be the starting time of job $J_{\sigma[i]}$, then we have $C_{\sigma[k]}(\sigma) = S_{\sigma[i]}(\sigma)+\sum_{j = i}^k p_{\sigma[j]}$. In the following, we distinguish two cases in our discussion.

Case 1. $w_{\sigma[k]} = \min\{w_{\sigma[j]}:i\leq j \leq k\}$.

In this case, we assume that job $J_{\sigma[x]}$ with $i\leq x \leq k$ is the final completed job among $J_{\sigma[i]}, \cdots, J_{\sigma[k]}$ in an optimal schedule $\pi$. Hence, we have $C_{\sigma[x]}(\pi)\geq\sum_{j = i}^k p_{\sigma[j]}$, then $WC_{\rm opt}\geq w_{\sigma[x]}C_{\sigma[x]}(\pi)\geq w_{\sigma[k]}\sum_{j = i}^k p_{\sigma[j]}$. Since $WC_{\rm on} = w_{\sigma[k]}C_{\sigma[k]}(\sigma) = w_{\sigma[k]}(S_{\sigma[i]}(\sigma)+\sum_{j = i}^k p_{\sigma[j]})$, we can prove the competitive ratio of algorithm $\mathcal{A}$ by discussing the value of $S_{\sigma[i]}$ in the subcases. From algorithm $\mathcal{A}$, we have $S_{\sigma[i]}(\sigma)\geq\beta$.

Case 1.1. $S_{\sigma[i]}(\sigma) = \beta$.

Note that $S_{\sigma[i]}(\sigma) = \beta$ holds if and only if job $J_{\sigma[i]}$ arrives at and before time $\beta$, i.e., $0 \leq r_{\sigma[i]}\leq\beta$, then we have

thus,

Case 1.2. $S_{\sigma[i]}(\sigma) = (1+\beta)^2-1$.

There are two possible reasons for $S_{\sigma[i]}(\sigma) = (1+\beta)^2-1$: One in which a restart occurs at time $(1+\beta)^2-1$ and the other in which there is no restart occurance and the arrival time of job $J_{\sigma[i]}$ is $(1+\beta)^2-1$.

Case 1.2.1. A restart occurs at time $S_{\sigma[i]}(\sigma)$.

We can assume that job $J_{\sigma[h]}$ is the one that being processed when job $J_{\sigma[i]}$ arrives, and it is easy to find that $r_{\sigma[i]} > \beta$. By algorithm $\mathcal{A}$, we conclude that the restart occurs when condition $w_{\sigma[i]} > w_{\sigma[h]}(1+\beta)$ holds. In this case, we have

then we estimate the optimal objective function value $WC_{\rm opt}$.

If $|\{J_{\sigma[j]}:i\leq j\leq k\}| = 2$ and $h\in\{i+1, \cdots, k\}$, then we have $h = i+1 = k$ and $w_{\sigma[h]} = w_{\sigma[k]}$. In an optimal schedule $\pi$, if job $J_{\sigma[k]}$ is scheduled before job $J_{\sigma[i]}$, we can conclude that

If job $J_{\sigma[i]}$ is scheduled before job $J_{\sigma[k]}$, then we have

All in all, we can find that $WC_{\rm opt} > w_{\sigma[k]}(2+\beta),$ then

If $|\{J_{\sigma[j]}:i\leq j\leq k\}| = 2$ and $h\notin\{i+1, \cdots, k\}$, then by Observation 1, job $J_{\sigma[i]}$ and job $J_{\sigma[k]}$ arrive after time $\beta$. Thus, we can obtain $WC_{\rm opt}\geq w_{\sigma[x]}C_{\sigma[x]}(\pi)\geq w_{\sigma[k]}(\beta+\sum_{j = i}^k p_{\sigma[j]}) = w_{\sigma[k]}(\beta+ 2),$ then

If $|\{J_{\sigma[j]}:i\leq j\leq k\}|\geq3$, i.e., the number of jobs in $\{J_{\sigma[i]}, \cdots, J_{\sigma[k]}\}$ is at least 3 and $w_{\sigma[j]}\geq w_{\sigma[k]}$ holds for each $i\leq j\leq k$, then we can obtain that $WC_{\rm opt}\geq 3w_{\sigma[k]} > w_{\sigma[k]}(2+\beta);$ thus,

Case 1.2.2. No restart occurs at time $S_{\sigma[i]}(\sigma)$.

If no restart occurs at time $S_{\sigma[i]}(\sigma)$, which indicates that $S_{\sigma[i]}(\sigma) = r_{\sigma[i]},$ then it can be seen that job $J_{\sigma[i]}$ is the first job that arrives among $J_{\sigma[i]}, \cdots, J_{\sigma[k]}$. Therefore,

In this case, schedule $\sigma$ is obviously the optimal schedule.

Case 1.3. $S_{\sigma[i]}(\sigma) > (1+\beta)^2-1$ or $\beta < S_{\sigma[i]}(\sigma) < (1+\beta)^2-1$.

In either situation, we have $S_{\sigma[i]}(\sigma) = r_{\sigma[i]}.$ Similar to Case 1.2.2, we can deduce that $\sigma$ is indeed the optimal schedule.

Case 2. $w_{\sigma[k]} > \min\{w_{\sigma[j]}:i\leq j \leq k\}$.

In this case, we suppose that job $J_{\sigma[y]}$ with $i\leq y\leq k$ is the last one such that $w_{\sigma[y]} < w_{\sigma[k]}$. From the definition of $J_{\sigma[y]}$, we have $w_{\sigma[j]}\geq w_{\sigma[k]} > w_{\sigma[y]}$ for each $j = y+1, \cdots, k$. By algorithm $\mathcal{A}$, job $J_{\sigma[y]}$ is picked out and processed at time $S_{\sigma[y]}(\sigma)$, then job $J_{\sigma[y]}$ must have the largest weight in $U(t)$, where $t = S_{\sigma[y]}(\sigma)$. Furthermore, since $w_{\sigma[j]}\geq w_{\sigma[k]} > w_{\sigma[y]}$, then we have $r_{\sigma[j]} > S_{\sigma[y]}(\sigma)\geq\beta$. Otherwise, job $J_{\sigma[y]}$ will be processed after job $J_{\sigma[j]}$ for each $j = y+1, \cdots, k$. We assume that job $J_{\sigma[z]}$ with $y+1\leq z \leq k$ is the last finished job among $J_{\sigma[y+1]}, \cdots, J_{\sigma[k]}$ in an optimal schedule $\pi$, then we have $C_{\sigma[z]}(\pi)\geq S_{\sigma[y]}(\sigma)+\sum_{j = y+1}^k p_{\sigma[j]}$ and

If $S_{\sigma[y]}(\sigma)\geq(1+\beta)^2-1$ or at least one job from set $\{J_{\sigma[j]}:j = y+1, \cdots, k\}$ has an arrival time of greater than or equal to $(1+\beta)^2-1$, we can estimate that

As a result, the objective value of schedule $\sigma$ satisfies

So, we only need to consider the case that $S_{\sigma[y]}(\sigma) < (1+\beta)^2-1$ and the arrival time of all jobs in set $\{J_{\sigma[j]}:j = y+1, \cdots, k\}$ is less than $(1+\beta)^2-1$. In this case, we can deduce that no restart occurs at time $(1+\beta)^{2}-1$ and the condition $w_{\sigma[j]} > (1+\beta)w_{\sigma[y]}$ in algorithm $\mathcal{A}$ is not satisfied, i.e., $w_{\sigma[j]}\leq(1+\beta)w_{\sigma[y]}$ for each $j = y+1, \cdots, k$. Let $\Gamma = \{J_{j}:w_{\sigma[j]} > w_{\sigma[y]}, j = y+1, \cdots, k \}$, and we have the following two cases.

Case 2.1. $\Gamma = \{J_{\sigma[k]}\}$.

If $\Gamma = \{J_{\sigma[k]}\}$, then we have $WC_{\rm on} = w_{\sigma[k]}(S_{\sigma[y]}+2)$.

When job $J_{\sigma[y]}$ is scheduled before job $J_{\sigma[k]}$ in an optimal schedule $\pi$, we have $WC_{\rm opt}\geq w_{\sigma[k]}(r_{\sigma[y]} +\; 2)$. If $r_{\sigma[y]} = S_{\sigma[y]}(\sigma)$, it is clear that $\sigma$ is the optimal schedule. If $r_{\sigma[y]}\neq S_{\sigma[y]}(\sigma)$, because $S_{\sigma[y]}(\sigma) < (1+\beta)^2-1$, then from Observation 2 we have $S_{\sigma[y]}(\sigma)\leq r_{\sigma[y]}+\beta$. Thus,

When job $J_{\sigma[k]}$ is scheduled before job $J_{\sigma[y]}$ in an optimal schedule $\pi$, we have $WC_{\rm opt}\geq w_{\sigma[y]}(r_{\sigma[k]}+\; 2)$. Note that $r_{\sigma[k]} > S_{\sigma[y]}(\sigma)$ and $w_{\sigma[k]}\leq(1+\beta)w_{\sigma[y]}$, then we have

Case 2.2. $\Gamma\neq\{J_{\sigma[k]}\}$.

If $\Gamma\neq\{J_{\sigma[k]}\}$, in this situation, there exists at least one job that satisfies $w_{\sigma[j]}\geq w_{\sigma[k]}$ for each $j = y+1, \cdots, k-1$. Moreover, at least two jobs have arrival times that are larger than $\beta$, so we have

and

From the above discussion, we complete the proof of Theorem 3.

Next, we present a numerical example to demonstrate the working of Algorithm $\mathcal A$. The details of this example can be found in Table 1.

Note that algorithm $\mathcal A$ will process job $J_{1}$ at time $\beta$. When job $J_{1}$ is being processed, job $J_{2}$ arrives at time 1 and $w_{2} > (1+\beta)w_{1}$, then job $J_{2}$ will interrupt the processing of job $J_{1}$ and starts at time $(1+\beta)^{2}-1$. Thus, job $J_{1}$ will become a restarted job. After the completion of job $J_{2}$, the machine is idle and only job $J_{1}$ is currently available, so algorithm $\mathcal A$ will process job $J_{1}$ at time $(1+\beta)^{2}$, and process job $J_{3}$ at time $(1+\beta)^{2}+1$. We then deduce that the objective value of algorithm $\mathcal A$ is $w_{3}C_{3} = 20\times[(1+\beta)^{2}+2]\approx83.$ The optimal schedule is to process job $J_{1}$ at time 0, then process job $J_{2}$ and job $J_{3}$ in turn. Thus, the optimal objective value is $w_{3}(r_{3}+1) = 20\times4 = 80,$ and the competitive ratio is $\frac{83}{80}\approx1.0375 < 1+\beta.$

4.   Conclusions

In this paper, we have shown that allowing all jobs to be restarted only once will not improve the competitive ratio of problem $1|r_{j}, online|WC_{\max}$. However, when all jobs are of equal length, the competitive ratio can be revised from $\frac{1+\sqrt{5}}{2}\approx1.618$ to $1+\beta\approx1.4656$ by using "1-restart". In subsequent investigations, the problem with "$k$-restart"($k\geq2$) and the jobs with the same processing time is still open. As proposed by Fu et al. ^[8] and Nouinou et al. ^[15], the same problem with "limited restart" or "semi-online" is worthy of further research. It is also interesting to consider the online scheduling problem with other kinds of objectives.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

We are grateful to the editor and three anonymous reviewers for their constructive comments and helpful suggestions.

This work was supported by the National Natural Science Foundation of China under Grant Numbers 12271491 and 11971443.

Conflict of interest

The authors declare that they have no competing interests.