1 Introduction↩︎

Makespan Minimization is a well-established objective in the field of scheduling. In the standard case of identical machines, we are presented with \(m\) identical machines and \(n\) jobs that require scheduling. The objective is to assign each job to a specific machine to minimize the makespan, which corresponds to the last completion time among all machines. Traditional offline algorithm design focuses on accomplishing this task efficiently under the assumption that we know all the jobs’ information at the beginning. However, the assumption does not hold in many real-world applications, where we are required to make online decisions. Minimizing makespan in an online scenario has garnered significant attention since the 1960s [1]. There are two types of online formulations of makespan minimization problems.

• Sequential (list) formulation: jobs are all released at \(0\) but following an online order that the next job is revealed only after we decide irrevocably which machine is allocated for the current one.

• Over-time arrival formulation: Each job \(j\) is associated with a release time \(r_j\), and is revealed by the algorithm at \(r_j\). The algorithm can start processing a job at an idle machine after the job’s release time without preemption.

Our paper focuses on the second one, under the standard competitive analysis for online algorithms. An algorithm is said to be \(c\)-competitive, or achieves a competitive ratio of \(c\) if its makespan is at most \(c\) times the optimal makespan under all possible inputs.

Let us compare the two models from the perspective of motivation. The sequential formulation naturally fits scenarios involving short-term load balancing tasks, such as scheduling across multiple CPUs over a brief time window. In these cases, many tasks arrive almost simultaneously, so their release times can be treated as zero. Moreover, such settings typically require immediate dispatch, meaning that jobs must be scheduled in the order they arrive. In this context, minimizing the makespan serves as a reasonable objective, as it promotes balanced load distribution among the CPUs. On the other hand, the over-time formulation is more suitable for long-term manufacturing scenarios. In such settings, tasks arrive gradually over time, as part of a batch that must be completed together to trigger downstream operations. Here, the makespan becomes a natural objective, and release times play a crucial role, as jobs no longer arrive simultaneously. Given this long-term perspective, we no longer require immediate dispatch; instead, we can determine which jobs to process over time without adhering to a fixed decision order.

A common concern with using the makespan objective in the presence of release times is whether it still effectively captures load balancing across machines. In the offline setting, where all release times are known in advance, one might worry that the makespan could be dominated by the latest released jobs, potentially overlooking imbalances in scheduling earlier tasks. However, this concern is naturally mitigated under the worst-case competitive analysis framework for online algorithms. If an online algorithm allocates early jobs in an unbalanced manner, but performs well for later jobs, an adversary could exploit this by releasing only the early jobs, resulting in a poor competitive ratio. Consequently, any online algorithm with a good competitive ratio must inherently maintain balanced scheduling at all times. This makes the makespan objective with release times well-suited for long-term scheduling tasks, particularly when the underlying goal is to balance load across machines.

In 1997, Chen and Vestjens [2] proposed an online LPT (Longest Processing Time First) algorithm described as follows: at each time that there is an idle (not processing any job) machine and several released but not scheduled jobs, schedule the longest job on that machine. They prove that LPT is \(1.5\)-competitive, and the analysis is tight for \(m\geq 2\). The tightness is established by the following one-one-two hard instance: initially, two size-\(1\) jobs are released at time \(0\), and LPT immediately schedules them on two separate machines. Subsequently, just after the commencement of these two jobs, \(m-1\) jobs with a processing time of \(2\) are released. No other jobs are released later. LPT finishes these jobs at \(3\), while the optimal solution can complete them at \(2\) by placing the first two small jobs on the same machine. On the hardness side for general algorithms, they show that no deterministic online algorithm has a competitive ratio better than \((\frac{5-\sqrt{5}}{2})\approx 1.382\) for \(m=2\) and \(1.347\) for \(m\geq 3\), which is further improved to \(1.3596\) by Li and Zhang [3]. The most natural open question is: can we beat this simple LPT strategy in the over-time Online Makespan Minimization problem?

Let us begin by considering how to beat the competitive ratio of \(1.5\) in the classic one-one-two hard instance. When two size-1 jobs arrive at time 0, processing both immediately yields a competitive ratio of \(1.5\). This naturally suggests a strategy: process one job and delay the other. In 2001, Noga and Seiden [4] applied this insight and proposed an algorithm called \(\tt{SLEEPY}\) for the 2-machine case. Remarkably, they achieved the optimal competitive ratio of \((\frac{5 - \sqrt{5}}{2}) \approx 1.382\). However, when the number of machines becomes larger, there are more technical challenges. In 2018, Huang et al. [5] managed to break the \(1.5\) barrier for general \(m\) by utilizing an additional power called restart (which involves stopping the processing of a job but reprocessing the whole job later). Alongside this, they introduced a key analytical tool, the left-over lemma, which provides a bound comparing the total amount of work completed by the algorithm and by the optimal schedule over a given time interval. Despite these advances, whether LPT and its \(1.5\) competitive ratio can be outperformed in the original (non-restart) setting for any \(m \geq 3\) has remained an open question for decades, even for small constants such as \(m = 3\) or \(m = 4\).

We partially answer this long-standing open question on the positive end. We generalize the SLEEPY algorithm and propose the Generalized SLEEPY algorithm that works for general \(m\), along with a novel technique called dynamic locking. We prove that it is \(\left(1.5-\frac{1}{O(m^2)}\right)\)-competitive for general \(m\). In conclusion, we beat LPT for all the cases where \(m\) is a constant.

Interestingly, in the case \(m=3\), a good competitive ratio can be achieved more straightforwardly without the dynamic locking technique, which is \(1.482\). The result is formalized in the following theorem.

However, the dynamic locking strategy is crucial when \(m\) becomes large. In particular, we show that the competitive ratio becomes \(1.5\) without dynamic locking when \(m\geq 6\).

The following table summarizes the previous results and our contribution to the online (over-time) machine minimization problem.

1.1 Our Techniques↩︎

Most analyses of competitive or approximation ratios for makespan minimization rely on two fundamental techniques for upper-bounding the power of the optimal solution (OPT): the bin-packing argument and the efficiency argument. The bin-packing argument limits how many large jobs OPT can schedule; for example, it cannot process more than \(m\) jobs of size more than \(0.5 \cdot \texttt{OPT}\), as each machine can accommodate at most one such job. The efficiency argument, on the other hand, bounds the total workload OPT can complete in a time window; a basic form states that OPT cannot process more than \(tm\) units of work in \([0, t)\). To prove that an online algorithm is \(c\)-competitive, we typically argue by contradiction: if the algorithm’s makespan exceeds \(c \cdot \texttt{OPT}\), then either there are too many large jobs (violating bin-packing), or too much workload is completed by the algorithm (violating efficiency).

We build on the locking idea of the SLEEPY algorithm, which is proposed by Noga and Seiden [4], originally designed for \(m=2\). This algorithm follows the LPT strategy but, whenever it starts a job \(j\) at time \(s_j\), it locks the other machine until \(s_j + \alpha p_j\), where \(\alpha\) is the locking parameter and \(p_j\) is the processing time of job \(j\). In other words, no job may start on the other machine before the lock expires. Consider the classic one-one-two hard instance: LPT achieves a competitive ratio of \(1.5\), as the last large job is delayed from its release time \(r_n\) to its start time \(s_n\), with this delay amounting to \(0.5 \cdot \texttt{OPT}\) while both machines remain busy. The delayed interval \([r_n, s_n)\) must thus be a busy period on all machines. To create this busy delayed period, the adversary can release two size-1 jobs at time \(0\), prompting LPT to start them just before \(r_n = 0 + \epsilon\), whereas OPT can schedule both on a single machine. However, under the locking strategy of SLEEPY, a gap is introduced between the start times of these size-1 jobs. If the adversary still attempts to enforce a busy period at \(r_n\), the first job must start strictly before \(r_n\). As a result, the size of this first job must exceed the length of \([r_n, s_n)\), which is \(0.5 \cdot \texttt{OPT}\). This prevents OPT from assigning both jobs to the same machine, thereby breaking the hard instance. We extend this idea to \(m \geq 3\) by locking all other machines whenever a job starts.

However, locking comes with drawbacks. It can waste machine capacity by leaving machines idle, even when there are released jobs that have not yet started. This causes the algorithm to complete less total work in certain intervals, sometimes even less than LPT—which weakens efficiency arguments. For \(m = 2\), this is manageable, since at most one machine is locked. But for \(m \geq 3\), we must formally analyze the impact. We address this by combining our analysis framework with the left-over lemma from Huang et al. [5].

A deeper challenge is that the last job may be delayed either because machines are busy or because they are locked. This distinction complicates bin-packing arguments: the delayed interval \([r_n, s_n)\) is no longer purely a busy period—it may contain idle time caused by locking. For instance, if job \(n\) starts late because a larger job \(n'\) (with \(p_{n'} > p_n\) and \(r_{n'} = r_n\)) is locking machines, then \(s_n = s_{n'} + \alpha p_{n'}\). The interval \([r_n, s_{n'})\) may be busy, but \([s_{n'}, s_n)\) is idle. As a result, the effective busy period may be shorter than \(0.5 \cdot \texttt{OPT}\). Even if \(m\) jobs start before \(r_n\), and we can show gaps between their start times—making them larger than \([r_n, s_{n'})\)—it remains unclear whether two such jobs can fit on one machine in OPT, since the size increase may not offset the busy-period reduction.

For \(m = 2\), Noga and Seiden [4] showed that such locking-induced delays cannot happen, using an efficiency argument. We extend this insight to \(m = 3\). However, the approach fails when \(m\) becomes large (see [thm:dynamic32locking], proved in 8).

To resolve this, we introduce a novel technique called dynamic locking. Our idea is to assign larger locking parameters to jobs that start before \(r_n\) than to the job \(n'\). In an online setting, this is nontrivial, since we cannot know in advance which job will be the last to start before \(r_n\). To handle this, we set the locking parameter \(\alpha\) dynamically based on each job’s processing time \(p_j\) and start time \(s_j\), decreasing \(\alpha\) as \(s_j/p_j\) increases. This implicitly ensures that the job \(n'\) receives a smaller locking parameter than the jobs that start before \(r_n\), leading to a larger gap between their start times. This gap prevents OPT from fitting both jobs on a single machine.

1.2 Paper Organization↩︎

We first introduce some basic notations and our algorithms in 2. Then, we briefly introduce our analysis framework and some basic properties in 3. Next, we complete the proof of the main theorem ([thm:ratio95m623]) in 4, 5, and 6. The case for \(m=3\) (proof of 1) is discussed in 7. The hardness result ([thm:dynamic32locking]) is proved in 8.

1.3 Further Related Work↩︎

Focusing on the over-time formulation of the online makespan minimization problem, Li et al. [6] studied a special case known as the kind release time (KRT) condition, where no jobs are released while all machines are busy. They showed that under this assumption, the classic LPT algorithm achieves a competitive ratio of \(\frac{5}{4}\) when \(m = 2\), complementing the general upper and lower bounds discussed earlier. In the preemptive setting, jobs’ processing may be interrupted and resumed later (without migration). An optimal preemptive algorithm for identical machines was presented by Chen et al. [7], who showed that the competitive ratio is \(1 / (1 - (1 - \frac{1}{m})^m)\), which equals \(\frac{4}{3}\) when \(m = 2\) and converges to \(\frac{e}{e - 1}\) as \(m \to \infty\).

Another commonly studied model is the sequential formulation, where all jobs are released at time zero but are revealed one by one in an online manner, requiring the algorithm to assign each job to a machine upon its arrival. This setting corresponds to the classical online load balancing problem. A foundational result was established by Graham [1], who showed that the greedy algorithm—assigning each job to the machine where it can start earliest—achieves a competitive ratio of \(2 - \frac{1}{m}\), which is optimal for \(m \leq 3\). Subsequent improvements for larger values of \(m\) have been explored by Bartal et al. and Karger et al. [8], [9]. A lower bound of \(1.88\) for deterministic algorithms in the non-preemptive setting was established by Rudin et al. [10]. Extensions of this problem to uniform and related machines have been investigated by Aspnes et al. and Jez et al. [11], [12]. The best known upper bound of \(5.828\) for this setting is achieved by the algorithm of Berman et al. [13], while a lower bound of \(2.564\) was established by Ebenlendr et al. [14]. Additional results and a broader overview of this setting can be found in the works of Albers et al., Galambos et al., and Dwibedy et al. [15]–[17].

In recent years, various extensions of these basic models have been proposed. One such extension includes the use of a reordering buffer, as studied in Englert et al. [18]. Another notable direction is the model of parallel schedules, where the online algorithm is permitted to construct several candidate schedules and select the best one at the end. This approach was analyzed in Albers et al. [19], where a \((\frac{4}{3} + \epsilon)\)-competitive algorithm was proposed for any \(0 < \epsilon \leq 1\), using \(\left(\frac{1}{\epsilon}\right)^{O(\log(1/\epsilon))}\) schedules. Additionally, a \((1 + \epsilon)\)-competitive algorithm that uses \(\left(\frac{m}{\epsilon}\right)^{O(\log(1/\epsilon)/\epsilon)}\) schedules was also presented.

2 Preliminaries↩︎

First, we formally define the model. We have \(m\) identical machines, and \(n\) jobs arrive online, where each job \(j\) is associated with a release time \(r_j\) and a processing time \(p_j\). The online algorithm has no information about job \(j\) before time \(r_j\). At any moment \(t\), it can choose to process one of the released jobs \(j\) on a machine non-preemptively. We denote the start time and completion time of job \(j\) by \(s_j\) and \(C_j = s_j + p_j\), respectively. The objective is to minimize the makespan, i.e., the maximum completion time among all jobs, \(\max_j C_j\).

In our context, \(\mathcal{J}\) denotes the set of jobs, while \(\mathcal{M}\) denotes the set of machines. The schedule produced by our algorithm, along with its corresponding makespan, is denoted by \(\sigma(\mathcal{J})\). Meanwhile, \(\pi(\mathcal{J})\) represents the optimal offline schedule for the given job set \(\mathcal{J}\), along with its makespan. When \(\mathcal{J}\) is clear from context, we may simplify the notation to \(\sigma\) and \(\pi\). We focus on the standard competitive analysis in our paper. We say that an algorithm is \((1+\gamma)\)-competitive if \(\frac{\sigma(\mathcal{J})}{\pi(\mathcal{J})} \leq 1+\gamma\) holds for all possible instances \(\mathcal{J}\).

2.1 The Generalized SLEEPY Algorithm↩︎

Our algorithm is an LPT-style algorithm embedded with a specific machine-locking strategy: whenever a job starts processing on a machine, all other machines are locked for a certain period. Before presenting our algorithm in detail, we first define the state of jobs and machines at a given time \(t\). \[\text{A job is} \begin{cases} \boldsymbol{released} & \text{if } t \geq r_j;\\ \boldsymbol{processing} & \text{if } s_j \le t < C_j = s_j + p_j; \\ \boldsymbol{finished} & \text{if } t \geq C_j ; \\ \boldsymbol{pending} & \text{if } r_j \le t < s_j. \end{cases}\]

\[\text{A machine is} \begin{cases} \boldsymbol{busy} & \text{if it is currently processing a job j;} \\ \boldsymbol{locked} & \text{if the algorithm does not allow it to start a new job;} \\ \boldsymbol{idle} & \text{if it is neither busy nor locked.}\\ \end{cases}\]

We now present the algorithm. Let \(\lambda \ge 1\) and \(\alpha \in [0, \gamma]\) be the locking parameters. The Generalized SLEEPY algorithm with dynamic locking operates as follows. At any moment \(t\), if there is at least one idle machine, the algorithm selects an arbitrary idle machine and performs the following two steps:

1. LPT Strategy: Assign the longest pending job \(j\) to the selected idle machine and start processing it.

2. Dynamic Locking Strategy: Lock all machines until time \(s_j + \alpha_j p_j\), where the locking parameter is given by \(\alpha_j = \lambda^{-\frac{s_j}{p_j}} \alpha \le \alpha\). Note that if another machine is already busy, we can still treat it as locked until \(s_j + \alpha_j p_j\); a machine can thus be marked as both busy and locked simultaneously.

Note that when we refer to the Generalized SLEEPY algorithm without dynamic locking, we mean that the locking parameter \(\alpha_j\) is set to a fixed constant \(\alpha\) (i.e., \(\lambda = 1\)). We show that even this simpler version can surpass the \(1.5\) barrier in the case of \(m=3\); the proof is provided in 7. The original SLEEPY algorithm [4] is in fact a special instance of our framework for \(m=2\), obtained by setting \(\lambda = 1\) (thus, no dynamic locking) and choosing \(\alpha = \frac{3 - \sqrt{5}}{2}\). As a result, Generalized SLEEPY attains the same optimal competitive ratio of \(\frac{5 - \sqrt{5}}{2}\) as SLEEPY when there are two machines.

To analyze the competitive ratio of the algorithm, we aim to show that no job set \(\mathcal{J}\) can cause the algorithm to produce a makespan satisfying \(\sigma(\mathcal{J}) > (1+\gamma)\pi(\mathcal{J})\). Without loss of generality, we assume for contradiction that there exists a smallest (in terms of the number of jobs) counterexample \(\mathcal{J}\) such that \(\pi(\mathcal{J}) = 1\) and \(\sigma(\mathcal{J}) > (1+\gamma)\pi(\mathcal{J}) = 1 + \gamma\). We label the jobs in \(\mathcal{J}\) by indices \(1, \dots, n\) according to their completion times in the schedule \(\sigma\), so that \(C_1 \le C_2 \le \dots \le C_n\).

To derive a contradiction, we focus on two types of arguments: bin-packing arguments and efficiency arguments. The goal of the bin-packing arguments is to identify a sufficiently large subset of large jobs, such as \(m+1\) jobs with processing time \(p_j > 0.5\), that cannot be feasibly scheduled within a makespan of \(1\), contradicting \(\pi(\mathcal{J}) = 1\). In contrast, the efficiency arguments aim to show that the algorithm processes a substantial amount of workload, such that it would be impossible for the optimal offline schedule to complete all that workload within \([0,1)\). As a simple example, if the total workload processed by the algorithm exceeds \(m\), then a contradiction arises. However, since not all jobs are released at time \(0\), the upper bound of processed workload by the optimal solution may be less than \(m\). We must employ more refined arguments that account for release times in our analysis.

2.2 Algorithm’s Efficiency↩︎

In this subsection, we introduce some useful notations to describe the efficiency of an algorithm, as preparation for applying efficiency arguments. Roughly speaking, efficiency measures the total workload completed by the algorithm within a given time interval. We also present a technical lemma from [5] that provides an upper bound on the efficiency gap between our algorithm and the optimal solution.

For convinence, we use \(P_\pi\) and \(P_\sigma\) denote \(P_\pi(0,1)\) and \(P_\sigma(0,C_n)\), which means the total processing time of \(\sigma\) and \(\pi\). Naturally, we have \(P_\pi = P_\sigma \leq m\).

The following lemma provides the basic efficiency argument for Generalized SLEEPY, with or without dynamic locking. It gives an upper bound on the total processing power wasted by the algorithm.

Finally, we compare the efficiency of the algorithm and the optimal solution over a specific time interval \([0, t)\). That is, we aim to compare \(P_\pi(0, t)\) and \(P_\sigma(0, t)\). \(P_\pi(0, t)\) can exceed \(P_\sigma(0, t)\) for two reasons. First, \(\sigma\) may waste time due to machines being locked. Second, some machines in \(\sigma\) may be idle simply because there are no pending jobs.

Intuitively, the first case can be bounded by \(W_\sigma(0, t)\), while the second case can occur only over limited portions of the interval \((0, t)\); otherwise, the efficiency of \(\pi\) would also be low. The following left-over lemma formalizes these two sources of inefficiency and provides an integrated upper bound on the difference \(P_\pi(0, t) - P_\sigma(0, t)\).

We remark that this lemma works for general scheduling algorithms. In their paper, the restart operation creates wasted time, which is produced by the locking strategy in our algorithm.

3 Overview of Our Analysis↩︎

Our analysis begins by examining why the last job \(n\) has such a large completion time, i.e., \(C_n > 1 + \gamma\). The only possible reason is that it experiences a significant delay between its release time \(r_n\) and its start time \(s_n\).

Next, we rule out the case where the last job \(n\) is too small. Roughly speaking, if \(p_n\) is small, \(s_n\) should be large, then the algorithm must have processed a substantial amount of workload over the long interval \([0, s_n)\), which leads to a contradiction via the efficiency arguments. This idea is formalized in the following lemma for the size of the last job.

To handle the remaining cases when \(p_n\) is large, our analysis establishes a series of inequalities involving the parameters \(\lambda\), \(\alpha\) (the locking parameters), and \(\gamma\). These properties play a key role in reaching a contradiction and impose specific constraints on the choice of \(\lambda\), \(\alpha\), and \(\gamma\). Ultimately, by setting \(\alpha = \frac{1}{4m^2}\), \(\lambda = 4^{25/6}\), and \(\gamma = \frac{1}{2} - \frac{1}{4^{20}m^2}\), we arrive at the desired contradiction. While some of these conditions may appear complex or unintuitive, and only a few turn out to be tight when the parameters are optimized, we have explicitly stated all such conditions within the corresponding properties in 6. This not only allows readers to verify the correctness of our analysis but also sets the stage for a more transparent discussion on parameter selection.

The next step in our analysis is to examine what happens in the algorithm after time \(r_n\), to understand why the last job \(n\) is delayed. We refer to this interval as the last scheduling period. In 4, we first build a structural understanding of this period within the algorithm’s schedule.

Roughly speaking, this period can be divided into two parts: a last locking chain and a busy period. The last locking chain consists of a sequence of jobs that lock the next one in a cascading manner, from \(n_1 = n\) to \(n_k\), until we reach a job \(n_k\) that is no longer delayed due to locking. We then show that \(s_{n_k}\) is still greater than \(r_n\), meaning there is a busy period \([r_n, s_{n_k})\) that delays job \(n_k\). Since all machines are busy during this interval, there must be \(m\) jobs processing on these machines. We refer to these \(m\) jobs, together with the \(k\) jobs in the last locking chain, as the critical jobs. Refer to 1 as an example.

We categorize these critical jobs into two types:

• early critical jobs, where \(s_j < r_n\);

• late critical jobs, where \(s_j \geq r_n\).

By proving that no three critical jobs can be scheduled on the same machine, we conclude, via the Pigeonhole Principle, that there must be \(k\) pairs of critical jobs scheduled on the same machine in \(\pi\). We then distinguish two cases:

• If all these \(k\) pairs consist solely of early critical jobs, we have \(k\) machines, each processing an early critical pair. We handle this case using a generalized bin-packing argument and resolve it by carefully setting the rescaling factor \(\lambda\) in 5.1. Roughly speaking, we show that the total processing time of these critical jobs is at least \(k\), so at least one machine must have a makespan exceeding \(1\), contradicting \(\pi = 1\).

• Otherwise, if at least one pair involves a late critical job, we apply the efficiency argument by comparing the efficiency of our algorithm with that of the optimal solution. This analysis is detailed in 5.2 and 5.3, where we derive a contradiction.

Finally, we conclude the proof of [thm:ratio95m623] with a sketch. Moreover, we also note why we can achieve a better ratio when \(m=3\) even without dynamic locking. Using an efficiency argument, we can show (in 10) that the last locking chain can consist only of the last job \(n\), which significantly simplifies the challenge posed by the last locking chain.

4 Basic Discussion: Last Scheduling Period↩︎

This section discusses the critical period in \(\sigma\), i.e., the period after \(r_n\). We aim to understand why the last job \(n\) is delayed until time \(s_n\). The delay of the last job in our setting can occur for two different reasons.

On the one hand, the job may be delayed because all machines are busy. In this case, we call it a pushed job. On the other hand, the delay may occur because machines are locked, and the job is scheduled immediately once a machine becomes unlocked. We refer to such jobs as locked jobs. Note that in a corner-case scenario where a job is released at the same moment a machine becomes unlocked and is immediately scheduled, we still classify it as a locked job.

Now, we scan backward starting from the last job, with the goal of finding the first job in this sequence that is not locked. If the last job \(n_1 = n\) is locked, we identify the job responsible for locking the machines, denoted as \(n_2\). If \(n_2\) is also a locked job, we repeat this process until we find a job \(n_k\) that is not a locked job (i.e., it is either pushed or scheduled immediately). We define the set \(S = \{n_1 = n, n_2, \dots, n_k\}\) as the last locking chain in \(\sigma\).

By the definition of the locking chain, we have the following claim.

Then, we have the following advanced property under a specific condition of the three parameters \(\lambda\), \(\alpha\), and \(\gamma\).

Then, we have the following corollaries.

Next, since \(s_{n_k} > r_n\) and \(n_k\) is not a locked job by definition, it follows that there must be \(m\) jobs being processed at time \(s_{n_k}\). Otherwise, it would be impossible to delay job \(n\) to a start time \(s_n > s_{n_k}\). We denote these jobs by \(j_1, j_2, \dots, j_m\) and refer to them as critical jobs, together with the jobs in the locking chain. That is, we define the critical job set as \[\mathcal{J}_C = \{j_1, \dots, j_m\} \cup \{n_1, \dots, n_k\}.\] Refer to 2 for illustration.

Now, we have completed the preparation for our analysis. In the critical period (\(t > r_n\)), we identify \(m + k\) critical jobs. By 7 and the pigeonhole principle, at least \(k\) pairs of these jobs must be executed on the same machine in \(\pi\). We refer to each such pair as a critical job pair.

5 Further Discussion of Critical Job Pairs↩︎

In this section, we analyze different cases among the \(k\) critical job pairs. We classify them into two types:

• Early Critical Pair: both jobs are early critical jobs.

• Late Critical Pair: at least one job is a late critical job.

We first eliminate the case where all critical pairs are early in 5.1, which is a key scenario for the dynamic locking technique. In this section, we will also fix the choice of \(\lambda\). Then, in 5.2 and 5.3, we analyze the efficiency of both our algorithm and the optimal solution in the presence of at least one late critical pair, ultimately leading to a contradiction.

5.1 Early Critical Pairs Only↩︎

This section eliminates the case that all critical job pairs consist of early critical jobs. First, we give a lower bound for \(\alpha_f\), which promises that the critical jobs will use a large enough locking parameter.

Hereafter, we show that with a proper choice of \(\lambda\), we can eliminate the possibility of all critical job pairs consisting of early critical jobs.

From 8, we know that there exists at least one pair of critical jobs \(a\) and \(b\) such that either \(s_a\ge r_{n}\) or \(s_b\ge r_{n}\). Consider such a pair of critical jobs \(a\) and \(b\), called a Late Critical Pair.

By definition, we have a basic property for this idle period.

We will discuss the following two cases of the fixed late critical pair.

1. \(\min\{s^\pi_a,s^\pi_b\} < \theta^+\) in 5.2.

2. \(\min\{s^\pi_a,s^\pi_b\} \geq \theta^+\) in 5.3.

5.2 Late Critical Pair: \(\min \{s^\pi_a,s^\pi_b\} < \theta^+\)↩︎

In this section, we derive a contradiction that \(\sigma\) processes a workload exceeding \(m\) to show that this situation cannot occur. First, we eliminate cases where jobs \(a\) and \(b\) are late critical jobs.

Finally, additional restrictions on \(\alpha\) and \(\gamma\) are imposed to demonstrate a contradiction, reinforcing the infeasibility of this scenario.

5.3 Late Critical Pair: \(\min \{s^\pi_a,s^\pi_b\} \ge \theta^+\)↩︎

In this section, we derive a contradiction that the overall workload of our algorithm (i.e., \(p_\sigma\)) is larger than that of OPT (i.e., \(P_\pi\)). First, we prove two technical lemmas concerning the efficiency of our algorithm to derive a lower bound of \(P_{\sigma}- P_{\pi}\). Subsequently, we derive a contradiction by demonstrating that the lower bound is positive.

Then, we move towards two subcases of \(a\) and \(b\), based on the relationship between \(s_a\), \(s_b\), and \(r_{n}\). Recall that \(s_a\geq r_{n}\) or \(s_b\geq r_{n}\) is proved in 8. Without loss of generality, assuming \(s_b \geq s_a\), it remains to discuss the following two cases:

1. \(s_a < r_{n} \leq s_b\): \(a\) is early critical job and \(b\) is late.

2. \(r_{n} \leq s_a \leq s_b\): \(a\) and \(b\) are both late critical jobs.

6 Bound of \(\gamma\) and \(\alpha\)↩︎

Given the conditions concerning variables \(\lambda, \;\alpha, \;\gamma\) and \(m\) as mentioned earlier in the text, we prove that there does not exist a minimum size set of jobs \(\mathcal{J}\) with optimal makespan \(\pi(\mathcal{J})=1\) that makes our algorithm have a makespan \(\sigma(\mathcal{J})=C_n=s_n+p_n>1+\gamma\). In other words, for each job set \(\mathcal{J}\), our algorithm guarantees that \(\frac{\sigma(\mathcal{J})}{\pi(\mathcal{J})}\le 1+\gamma\). The conditions are systematically reorganized and presented below for clarity.

• Conditions on \(\alpha\) in terms of \(m\):

\[\begin{align} 1-\frac{m\alpha}{1+(m-1)\alpha}\ge0 \\ 1-(m-1)\alpha\ge0 \\ \frac{3}{4}m-1-m(m-1)\alpha\ge0 \\ 1+\alpha-2m\alpha(1-(m-1)\alpha)\ge 0 \\ -\frac{1}{2}m+(m-1)\alpha+1\le0 \\ 1-m\alpha(1-(m-1)\alpha)\ge 0 \end{align}\]

• Conditions on \(\gamma\) in terms of \(m\) and \(\alpha\):

\[\begin{align} \frac{\gamma}{\alpha} > m \\ \gamma-(m-1)\alpha\ge0.4 \\ \frac{m\gamma-\frac{m}{4}-m(m-1)\alpha}{\frac{3}{4}m-1-(m-1)\alpha}>\frac{1}{3} \\ \gamma\ge\frac{1+3.5(m-1)\alpha}{2.5} \\ 4\gamma-2(2m-3)\alpha-1\ge 0 \\ (2+4^{-17.75}\alpha)\gamma>1 \\ \frac{2\gamma}{1+(m-1)\alpha}+\frac{\gamma-\frac{1}{4}-(m-1)\alpha}{\frac{3}{4}m-1-(m-1)\alpha}\ge 1 \\ m(1-2\gamma)+(2m(m-1)\alpha+1)\gamma-1\le 0 \\ m(\frac{1}{2}-\gamma)+m(m-1)\alpha (\frac{1}{2}+\gamma)-\frac{1}{2}\le 0 \end{align}\] Due to Conditions 12 and 15, the value of \(\alpha\) needs to be on the order of \(\frac{1}{O(m^2)}\). We can see that all conditions on \(\alpha\) in terms of \(m\) are satisfied if \[\alpha\le\frac{1}{4m^2}.\] Set \(\alpha = \frac{1}{4m^2}\) and then consider those conditions on \(\gamma\) in terms of \(m\) and \(\alpha\). Note that [condition:2gamma1] is the tightest condition. Set \(\gamma = \frac{1}{2}-\frac{1}{4^{20}m^2}\) to satisfy [condition:2gamma1]. Then, substitute the values of \(\alpha\) and \(\gamma\), we can verify that all conditions on \(\gamma\) in terms of \(m\) and \(\alpha\) are satisfied, which proves our main theorem:

7 Further Discussion on \(m=3\)↩︎

Here, we fix \(\lambda = 1\). There is an interesting fact about this special case.

10 implies that the job \(n\) is a pushed job. Thus, there will be exactly \(m\) processing jobs at time \(s_{n}\). Identify them by indices \(j_1,j_2,\dots,j_m\). Define \(\mathcal{J}_{C,m=3}=\{n,j_1,\dots,j_m\}\) as the critical set of tasks in this case. These \(m+1\) jobs in \(\mathcal{J}_{C,m=3}\) satisfy the following straightforward property.

By the pigeonhole principle, at least \(2\) of these \(m+1\) jobs in \(\mathcal{J}_{C,m=3}\) will be assigned to one machine in \(\pi\). We denote this pair of jobs as jobs \(a\) and \(b\). Firstly, we eliminate the case that jobs \(a\) and \(b\) are both early critical jobs. Remark that we do not require the dynamic locking factor \(\lambda\), because we do not have locked jobs.

From [claim:m613sasbrn], we know that either \(s_a\ge r_{n_k}\) or \(s_b\ge r_{n_k}\). By [lem:idle95basic], \(\theta^+ \leq r_{n}\). Similarly, as in the general analysis, we will discuss the following two cases of this pair of jobs.

1. \(\min\{s^\pi_a,s^\pi_b\} < \theta^+\).

2. \(\min\{s^\pi_a,s^\pi_b\} \geq \theta^+\).

For the first case, assume \(s_a^\pi<s_b^\pi\) without loss of generality. By [claim:pre95case1], \(s_a<r_n\) and \(p_a>\gamma\). Then \(s_a<r_n<s_b\). Similarly to the proof of [claim:sasbrnk95case1], we get \(s_a-r_a\ge s_a-s_a^\pi>\gamma\). We know that there won’t be idle machines during \([r_a,s_a)\) and \([r_n,s_n)\). Since \(C_a\geq s_n\), there is at least one busy machine during \((r_a, C_n)\). Assume the minimal release time is \(r_{min}\). Therefore, \(3(1-r_{min})\ge P_\pi=P_\sigma\ge s_n+p_n-r_{min}+2\gamma(\frac{3}{1+2\alpha}-1)>1+\gamma+2\gamma(\frac{3}{1+2\alpha}-1)-r_{min}\). Conditioned on

\(3>1+\gamma(\frac{6}{1+2\alpha}-1)+2r_{min}\ge3\), which is a contradiction. The illustration of the impossibility of the second case is the same as 5.3. Therefore, we should follow Conditions 9-15.

In conclusion, to prove 1, we need not discuss the property of the last locking chain because we prove \(|S|=1\) by a new condition of [conm613:1]. Therefore, Conditions 1-3 can be removed. On the other hand, it also becomes easier to handle early critical pairs. The proof of [claim:m613sasbrn] replaces Conditions 4-6 by [conm613:2]. Then, for late critical pairs, in the first case, we also replace Conditions 7-8 with a weaker one-[conm613:3]. In the second case, we keep the same proof as the general case. Therefore, we keep Conditions 9-15.

7.1 Conditions Required in This Special Case↩︎

\[\begin{align} 3\gamma-5\alpha-1 &> 0 \\ \frac{2-\alpha}{1-\alpha}\gamma&\ge1 \\ \gamma(\frac{6}{1+2\alpha}-1)&\geq2 \\ 1-2\alpha&\ge 0 \\ \frac{5}{4}-6\alpha&\ge0 \\ 1-5\alpha+12\alpha^2&\ge 0\;\text{(always holds)} \\ 3(1-2\gamma)+(12\alpha+1)\gamma-1&\le 0 \\ \frac{1}{2}-6\alpha&\ge0 \\ 1-3\alpha(1-2\alpha)&\ge 0\;\text{(always holds)} \\ 3(\frac{1}{2}-\gamma)+6\alpha (\frac{1}{2}+\gamma)-\frac{1}{2}&\le 0 \end{align}\]

First, it is straightforward to verify Conditions 9, 10, 11, 13, 14 hold if \(\alpha\le\frac{1}{12}\). For the remaining conditions, it can be checked that \(\alpha=0.07066\) and \(\gamma = 0.4817\) are feasible for all of them. We plot a figure for help verifying.

8 Hard Instance↩︎

Here, we prove the following theorem to demonstrate the necessity of introducing dynamic locking. We recall [thm:dynamic32locking]:

The proof is given by case-by-case analysis on the locking parameter \(\alpha\) in the Generalized SLEEPY.

8.1 Case 1: \(\alpha \geq \frac{1}{2(m-1)}\)↩︎

Consider the following instance: \(m\) jobs are released at time \(0\), with processing time \(1\). In the optimum schedule, by starting the \(m\) jobs at time 0, we obtain the optimum makespan of \(1\). In the Generalized SLEEPY algorithm’s schedule, the last started job of the \(m\) jobs would be \((m-1)\alpha\), so the completion time of the job is \((m-1)\alpha + 1 \geq 1.5\). In this case, the competitive ratio of Generalized SLEEPY is at least \(1.5\). Refer to Figure 4.

8.2 Case 2: \(\alpha < \frac{1}{2(m-1)}\) (\(m\geq6\))↩︎

Consider the following instance:

• \(6\) jobs labeled from \(1\) to \(6\), with \(\forall i \in [1, 6].~ r_i = 0\), \(p_1 = \frac{1}{1 + (1-\alpha)^5}\), and \(\forall i \in [2, 6].~ p_i = (1-\alpha)^{i-1} p_1\).

• \(m - 3\) jobs labeled from \(7\) to \(m + 3\), with \(\forall i\in [7,m+3].~ r_i = (1 - (1-\alpha)^5)p_1+\varepsilon\), where \(\varepsilon \rightarrow 0\), and \(p_i = 1 - (1 - (1-\alpha)^5)p_1\).

8.2.1 OPT’s Schedule.↩︎

The \(i\)-th machine processes the \(i\)-th and the \(7-i\)-th jobs in the first three machines and the completion time is \(p_i + p_{7-i} = p_1 \cdot ((1-\alpha)^{i-1} + (1-\alpha)^{6-i}) \leq p_1 \cdot (1 + (1-\alpha)^{5}) = 1\). In the last \(m-3\) machines, each of them processes one job labeled from \([7, m+3]\), the finish time is \((1 - (1-\alpha)^{5})p_1+\varepsilon + (1 - (1 - (1-\alpha)^{5})p_1)= 1+\varepsilon \rightarrow 1\). Refer to 5 below.

8.2.2 Generalized SLEEPY’s Schedule.↩︎

For \(1 \leq i \leq 6\), because the processing time decreases from \(1\) to \(6\), the jobs would be placed in this order and processed in different machines. Formally, we have \(s_1=0\) and for all \(2 \leq i \leq 6\), \(s_i = \sum_{j = 1}^{i-1} \alpha p_j\). Therefore, for all \(1 \leq i \leq 6\), \[\begin{align} C_i = s_i + p_i &= \sum_{j = 1}^{i-1} \alpha p_j + (1-\alpha)^{i-1} p_1\\ &= \sum_{j = 1}^{i-2}\alpha p_j + \alpha (1 - \alpha)^{i-2}p_1 + (1 - \alpha)^{i-1}p_1 \\ &= \sum_{j = 1}^{i-2}\alpha p_j + (1 - \alpha)^{i-2}p_1 \\ &= \dots = p_1. \end{align}\] Note that \(s_{6} = p_1 - p_{6} = p_1 (1 - (1-\alpha)^{5}) = r_{7}-\varepsilon<r_7\), the last \(m - 3\) jobs are released just after the start of the job \(6\). Because only \(m-6\) machines are free before \(p_1\), three of the last \(m-6\) jobs must be scheduled after \(p_1\) or even after \(r_7+p_7=1 > p_1\). Without loss of generality, we call them \(m+1\), \(m+2\), and \(m+3\). By the definition of Generalized SLEEPY, the start time of the last job \(s_{m+3}\) must be large, where \[s_{m+3} = s_{m+1}+ 2\alpha (1- (1 - (1-\alpha)^{5})p_1) = p_1 + 2\alpha (1- (1 - (1-\alpha)^{5})p_1).\] Therefore, \[\begin{align} C_{m+3} &= p_1 + 2\alpha (1- (1 - (1-\alpha)^{5})p_1) + p_{m+3}\\ &= \frac{1}{1 + (1-\alpha)^5} + (1+2\alpha) (1-\frac{1 - (1-\alpha)^{5}}{1 + (1-\alpha)^5})\\ &= p_1+(1+2\alpha)p_7. \end{align}\] Refer to 6 below.

Let \(f(\alpha) = \frac{1}{1 + (1-\alpha)^5} + (1+2\alpha) (1-\frac{1 - (1-\alpha)^{5}}{1 + (1-\alpha)^5})\). We observe that for all \(\alpha \leq \frac{1}{2(m-1)}\), \(f(\alpha)\geq 1.5\). We plot the function in the following 7 for verification. The competitive ratio of Generalized SLEEPY is at least \(1.5\) in this case.

9 Conclusion↩︎

In conclusion, our main contribution is to show that we can beat the \(1.5\)-competitive ratio of LPT for every constant \(m\), marking an important step toward understanding whether LPT is the optimal algorithm for this over-time online makespan minimization problem. We believe that our results and techniques can inspire further work toward fully resolving this open question:

• If we believe that LPT is indeed optimal when \(m\) becomes large, then it would be necessary to construct a counterexample involving an infinite number of machines. This is because, for any constant number of machines, our algorithm achieves a competitive ratio strictly below \(1.5\). Prior to our results, many researchers may have believed that a counterexample with some constant \(m\), for example \(m=4\), could already demonstrate the tight bound of \(1.5\).

• On the other hand, if we believe that there exists a better algorithm that can beat \(1.5\) for general \(m\), then several challenges must be addressed. In our paper, we use a \(o(1)\) locking parameter; otherwise, the algorithm could waste too much processing power, making it difficult to use efficiency arguments. To improve beyond \(1.5\) for general \(m\), one would need to apply an \(\Omega(1)\) locking parameter and resolve the associated efficiency issues by designing a more refined version of the left-over lemma. Furthermore, the complications arising from the last locking chain become even more severe, suggesting that a similar idea to dynamic locking must also be incorporated.

On the other hand, we also believe that our algorithmic idea is not merely a theoretical trick for analysis. In this over-time model, locking machines for a period to wait for more future information can play an important role in improving LPT. Our dynamic locking rule suggests that a dynamic locking strategy may outperform a static one. Although in practice the locking parameter and the locking strategy may not be set exactly as in our work, it is an interesting direction to investigate whether there exists a suitable way to lock machines that can enhance the performance of LPT in practical settings.

References↩︎