betaFeedback

WorksComputer Science

An Optimal Online Algorithm for Single-machine Scheduling with Two Agents

Abstract

This paper addresses the online two-agent scheduling problem on a single machine, where jobs arrive over time. The objective is to minimize the weighted sum of the agents' makespans, denoted as Cmax⁡A+θCmax⁡BC_{\max}^A + θC_{\max}^B, for a given priority weight θ≥1θ\ge 1. A significant gap has persisted between the established theoretical lower bound on the competitive ratio and the performance of the best-known online algorithms. For the parameter range 1≤θ≤1+521 \leq θ\leq \tfrac{1+\sqrt{5}}{2}, we propose novel online algorithm which achieves a competitive ratio of 1+θ1+θ1+\tfracθ{1+θ}. This result matches the theoretical lower bound.

Introduction

The multi-agent scheduling problem is a modern extension of classical scheduling theory, capturing scenarios where multiple self-interested entities compete for shared resources. Originating from seminal works by Baker and Smith [3] and Agnetis et al. [2], this domain addresses the challenge of coordinating jobs owned by different agents on common machines. Unlike traditional single-objective problems, multi-agent scheduling requires constructing schedules that balance the potentially conflicting performance objectives of all agents. The growing relevance of multi-agent scheduling is driven by practical demands in distributed systems, flexible manufacturing, and cloud computing, where the efficient coordination of shared resources across multiple users or clients is essential. The increasing complexity of such systems has elevated multi-agent scheduling from a specialized topic to an important area of research, as documented by Agnetis et al. [1].

The early works of Baker and Smith [3] and Agnetis et al. [2], in the early 2000s, formally introduced two-agent scheduling problems, laying the groundwork for a vibrant and expanding research field. Since then, numerous models have been developed to capture the intricate interactions between agents. Broadly speaking, as described by Agnetis et al.[2], there are three main classes of models: Constrained model, Linear combination model and Pareto optimization model.

Over the years, these models have been enriched to incorporate increasingly realistic features. Variants with release dates [7] [14], deadlines [12][13], and learning effects [11] have been explored to better represent practical production environments. Further extensions include problems with rate-modifying activities [9, 10] and multi-objective formulations considering criteria such as minimizing late work and production cost [5]. Collectively, these contributions demonstrate the continuous effort to bridge theoretical scheduling formulations with real-world applications.

This paper focuses on a problem within the linear combination model, namely the online two-agent single-machine scheduling problem with the objective of minimizing the weighted sum of makespans. In the online setting, jobs arrive sequentially over time, and scheduling decisions must be made immediately and irrevocably without any knowledge of future arrivals. This absence of future information introduces substantial complexity compared to the offline counterpart, which Ding and Sun [4] proved to be NP-hard. For the online version, Ding and Sun [4] established a competitive ratio lower bound of 1+θ1+θ1+\frac{\theta}{1+\theta} but proposed an algorithm achieving only a ratio of 2+1θ2+\frac{1}{\theta}, thereby creating a considerable gap between the best-known algorithm and the theoretical optimum. More recently, Lu et al. [8] improved the upper bound to 1+2θ+θ22+2θ+θ2\frac{1+2\theta+\theta^2}{2+2\theta+\theta^2}; however, this result still does not attain the lower bound, leaving the development of an optimal online algorithm as an open challenge.

Our contribution. In this paper, we resolve this long-standing open problem. We propose a novel online algorithm for the problem 1∣rj, online∣Cmax⁡A+θCmax⁡B1\mid r_j,\ \mathrm{online}\mid C_{\max}^{A}+\theta C_{\max}^{B}, focusing on the challenging parameter range 1≤θ≤1+521\le\theta\le\frac{1+\sqrt{5}}{2}. The proposed algorithm is designed to strategically balance the conflicting objectives of the two agents under the uncertainty inherent in the online environment. We provide a rigorous proof that our algorithm achieves a competitive ratio of 1+θ1+θ1+\frac{\theta}{1+\theta}, thereby matching the established lower bound. This result closes the research gap identified by Ding and Sun [4] and improves upon the work of Lu et al. [8], providing a definitive and best possible solution for this class of online multi-agent scheduling problems.

The rest of the paper is organized as follows. Section 2 gives a formal statement of the problem and introduces notations. Section 3 presents our online algorithm for the case 1≤θ≤1+521\le\theta\le\frac{1+\sqrt{5}}{2}. Section 4 provides a detailed analysis of its competitive ratio and proves its optimality. Finally, Section 5 concludes with a summary of our findings and discusses potential avenues for future research.

Problem formulation and definitions

Problem formulation

We consider a single-machine scheduling problem involving two competing agents, namely Agent A and Agent B. Let JA\mathcal{J}^{A} and JB\mathcal{J}^{B} denote the sets of jobs belonging to Agent A and Agent B, respectively. For simplicity, jobs in JA\mathcal{J}^{A} and JB\mathcal{J}^{B} are referred to as A-jobs and B-jobs. These two job sets are disjoint, i.e., JA∩JB=∅\mathcal{J}^{A}\cap\mathcal{J}^{B}=\varnothing. Each job JjX∈JXJ_{j}^{X}\in\mathcal{J}^{X} (for X∈{A,B}X\in\{A,B\}) is characterized by a processing time pjXp_{j}^{X} and a release date rjXr_{j}^{X}. All jobs are to be processed non-preemptively on a single machine.

Each agent X∈{A,B}X\in\{A,B\} seeks to minimize its makespan, defined as Cmax⁡X=max⁡j∈JX{CjX}C_{\max}^{X}=\max_{j\in\mathcal{J}^{X}}\{C_{j}^{X}\}, where CjXC_{j}^{X} is the completion time of job JjXJ_{j}^{X}. The overall objective is to find a schedule that minimizes a weighted sum of the two agents’ makespans. The objective function is formulated as: min⁡Cmax⁡A+θCmax⁡B\min C_{\max}^{A}+\theta C_{\max}^{B}, where θ≥1\theta\ge1 is a constant representing the relative importance of Agent B’s objective.

This problem is studied in an online setting, where the existence and characteristics of any JjXJ_{j}^{X} are unknown until its release date rjXr_{j}^{X}. At any time tt, an online algorithm can either schedule an available job (one that has been released but not yet processed) or leave the machine idle. Decisions are irrevocable. Following the standard three-field notation [6], the problem under study is denoted as 1∣rj, online∣Cmax⁡A+θCmax⁡B1\mid r_j,\ \mathrm{online}\mid C_{\max}^{A}+\theta C_{\max}^{B}.

Definitions and Notations

We begin by introducing the key notations used throughout the analysis. A decision point tt is defined as any time at which the machine is idle and at least one job is available. A job is available at time tt if it has been released (rjX≤tr_j^X \le t) but not yet processed.

For clarity, notations are often presented for Agent A only; analogous definitions apply to Agent B.

  • UtXU_t^X: The set of available jobs for agent X∈{A,B}X \in\{A,B\} at time tt.

  • UtU_t: The set of all available jobs at time tt, i.e., Ut=UtA∪UtBU_t = U_t^A \cup U_t^B.

  • Js(t)AJ_{s(t)}^A and Jl(t)AJ_{l(t)}^A: The available A-jobs in UtAU_t^A with the shortest and longest processing times, respectively. Ties are broken arbitrarily.

  • TtT_t: The start time of the last contiguous block of jobs that was completed at time tt. If the machine has been continuously busy since time 0, then Tt=0T_t = 0.

  • LtAL_t^A: The set of A-jobs that were processed within the time interval [Tt,t][T_t,t].

  • P(S)P(S): The total processing time of jobs in job set SS, i.e., P(S)=∑Jj∈SpjP(S) = \sum_{J_j \in S} p_j.

  • rmin⁡(S)r_{\min}(S): The minimum release date among jobs in job set SS, i.e., rmin⁡(S)=min⁡Jj∈S{rj}r_{\min}(S) = \min_{J_j \in S}\{r_j\}.

Figure 1 provides a graphical illustration of these notations.

Figure 1. An example of the notations defined at time tt.

An online algorithm

In this section, we propose a novel online algorithm for the considered problem. Our method, referred to as AOSA (Agent-Based Online Scheduling Algorithm), is designed to exploit the inherent trade-off between the makespans of the two agents. The algorithm dynamically adapts its scheduling decisions according to the composition of available jobs and the relative priority parameter θ\theta.

When jobs from only one agent are available, AOSA postpones execution until a threshold time proportional to the job’s processing time and the weight θ\theta is reached. This delay prevents premature scheduling that could otherwise lead to an imbalance between the agents’ objectives.

When both agents have pending jobs, the algorithm compares their earliest release times and evaluates workload balance to decide whether to process a job from Agent A or Agent B. The decision rules are based on the cumulative processing requirements of both agents, adjusted by θ\theta and the start time of the current block. This mechanism ensures that machine time is allocated efficiently while respecting the relative priority encoded by θ\theta.

Procedures A and B implement a selective strategy between the smallest and largest available jobs of the chosen agent. Scheduling the smallest job accelerates progress for the active agent, while scheduling the largest job prevents excessive postponement of long tasks that could dominate the makespan. The threshold inequalities in each procedure ensure that the choice aligns with minimizing the weighted objective Cmax⁡A+θCmax⁡BC_{\max}^A + \theta C_{\max}^B.

Algorithm AOSA (Agent-Based Online Scheduling Algorithm)

Require: Priority weight θ≥1\theta\ge1; sequence of jobs arriving over time Ensure: Feasible schedule minimizing Cmax⁡A+θCmax⁡BC_{\max}^{A}+\theta C_{\max}^{B}

  1. while there are unscheduled jobs do

  2.     Determine UtU_t (set of available unscheduled jobs at time tt)

  3.     if Ut=UtAU_t=U_t^{A} then

  4.         if t≥θ1+θps(t)At \ge\frac{\theta}{1+\theta}p_{s(t)}^{A} then

  5.             Run Procedure A

  6.         else

  7.             Wait until θ1+θps(t)A\frac{\theta}{1+\theta}p_{s(t)}^{A} or a new job arrives

  8.         end if

  9.     else if Ut=UtBU_t=U_t^{B} then

  10.         if t≥11+θps(t)Bt \ge\frac{1}{1+\theta}p_{s(t)}^{B} then

  11.             Run Procedure B

  12.         else

  13.             Wait until 11+θps(t)B\frac{1}{1+\theta}p_{s(t)}^{B} or a new job arrives

  14.         end if

  15.     else if UtA≠∅U_t^{A}\ne\varnothing and UtB≠∅U_t^{B}\ne\varnothing then

  16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if rmin⁡(LtA∪UtA)<rmin⁡(LtB∪UtB)r_{\min}(L_t^{A}\cup U_t^{A})<r_{\min}(L_t^{B}\cup U_t^{B}) then

  17. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if P(LtB∪UtB)≥θP(LtA∪UtA)−(1+θ)TMP(L_t^{B}\cup U_t^{B})\ge\theta P(L_t^{A}\cup U_t^{A})-(1+\theta)T_M then

  18. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Run Procedure A

  19. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else

  20. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Run Procedure B

  21. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end if

  22. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else

  23. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if P(LtB∪UtB)≥θP(LtA∪UtA)+(1+θ)TMP(L_t^{B}\cup U_t^{B})\ge\theta P(L_t^{A}\cup U_t^{A})+(1+\theta)T_M then

  24. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Run Procedure A

  25. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else

  26. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Run Procedure B

  27. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end if

  28. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end if

  29. &nbsp;&nbsp;&nbsp;&nbsp;end if

  30. end while

Procedure A

  1. if Tt+P(LtA)+ps(t)A≤pl(t)AT_t+P(L_t^{A})+p_{s(t)}^{A}\le p_{l(t)}^{A} then

  2. &nbsp;&nbsp;&nbsp;&nbsp;if (1+θ)Tt+θ21+θ(P(LtA)+ps(t)A)≤θpl(t)A(1+\theta)T_t+\frac{\theta^2}{1+\theta}(P(L_t^{A})+p_{s(t)}^{A})\le\theta p_{l(t)}^{A} then

  3. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Schedule Js(t)AJ_{s(t)}^{A}

  4. &nbsp;&nbsp;&nbsp;&nbsp;else

  5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Schedule Jl(t)AJ_{l(t)}^{A}

  6. &nbsp;&nbsp;&nbsp;&nbsp;end if

  7. else

  8. &nbsp;&nbsp;&nbsp;&nbsp;if (1−θ21+θ)Tt+θ21+θpl(t)A≤θ(P(LtA)+ps(t)A)\left(1-\frac{\theta^2}{1+\theta}\right)T_t+\frac{\theta^2}{1+\theta}p_{l(t)}^{A}\le\theta(P(L_t^{A})+p_{s(t)}^{A}) then

  9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Schedule Js(t)AJ_{s(t)}^{A}

  10. &nbsp;&nbsp;&nbsp;&nbsp;else

  11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Schedule Jl(t)AJ_{l(t)}^{A}

  12. &nbsp;&nbsp;&nbsp;&nbsp;end if

  13. end if

Procedure B

1: if Tt+P(LtB)+ps(t)B≤pl(t)BT_t + P(L_t^B) + p_{s(t)}^B \le p_{l(t)}^B then 2: &nbsp;&nbsp;&nbsp;&nbsp;if (1+θ)Tt+11+θ(P(LtB)+ps(t)B)≤pl(t)B(1+\theta)T_t + \frac{1}{1+\theta}(P(L_t^B) + p_{s(t)}^B) \le p_{l(t)}^B then 3: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Schedule Js(t)BJ_{s(t)}^B 4: &nbsp;&nbsp;&nbsp;&nbsp;else 5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Schedule Jl(t)BJ_{l(t)}^B 6: &nbsp;&nbsp;&nbsp;&nbsp;end if 7: else 8: &nbsp;&nbsp;&nbsp;&nbsp;if (θ−11+θ)Tt+11+θpl(t)B≤P(LtB)+ps(t)B\left(\theta-\frac{1}{1+\theta}\right)T_t + \frac{1}{1+\theta}p_{l(t)}^B \le P(L_t^B) + p_{s(t)}^B then 9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Schedule Js(t)BJ_{s(t)}^B 10: &nbsp;&nbsp;&nbsp;&nbsp;else 11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Schedule Jl(t)BJ_{l(t)}^B 12: &nbsp;&nbsp;&nbsp;&nbsp;end if 13: end if

Competitive Analysis

In this section, we analyze the performance guarantee of Algorithm AOSA under the condition 1≤θ≤5+121 \le\theta\le\frac{\sqrt{5}+1}{2}, which is equivalent to

θ2≤θ+1(1)\theta^2 \le\theta+ 1 \tag*{(1)}

For the competitive analysis, let σ\boldsymbol{\sigma} denote the schedule generated by the online algorithm, with objective value Z(σ)=Cmax⁡A(σ)+θCmax⁡B(σ)Z(\boldsymbol{\sigma}) = C_{\max}^{A}(\boldsymbol{\sigma}) + \theta C_{\max}^{B}(\boldsymbol{\sigma}). We compare Z(σ)Z(\boldsymbol{\sigma}) with the value of an optimal offline schedule, denoted by π\boldsymbol{\pi}, which has objective value Z(π)=Cmax⁡A(π)+θCmax⁡B(π)Z(\boldsymbol{\pi}) = C_{\max}^{A}(\boldsymbol{\pi}) + \theta C_{\max}^{B}(\boldsymbol{\pi}).

Our analysis focuses on the structural properties of σ\boldsymbol{\sigma}. The schedule σ\boldsymbol{\sigma} can be partitioned into one or more blocks:

  • A block is a maximal set of jobs processed contiguously with no intervening idle time.

  • A block is pure if it contains jobs from a single agent and mixed otherwise.

The following notations are introduced to analyze the structure of the last mixed block of σ\boldsymbol{\sigma}, denoted by M\mathcal{M}.

  • A\mathcal{A} (resp. B\mathcal{B}): the final contiguous sequence of A-jobs (resp. B-jobs) in σ\boldsymbol{\sigma}. Note that A\mathcal{A} may lie outside M\mathcal{M} and thus form a pure block.

  • A′\mathcal{A}' (resp. B′\mathcal{B}'): the set of A-jobs (resp. B-jobs) in M\mathcal{M} that are scheduled before all jobs in A∪B\mathcal{A} \cup\mathcal{B}. Either A′\mathcal{A}' or B′\mathcal{B}' may be empty.

  • JuAJ_u^A (resp. JvBJ_v^B): the A-job (resp. B-job) in M\mathcal{M} scheduled immediately before B\mathcal{B} (resp. A\mathcal{A}).

  • A‾=A′∖{JuA}\overline{\mathcal{A}} = \mathcal{A}' \setminus\{J_u^A\} if JuA∈A′J_u^A \in\mathcal{A}' and B‾=B′∖{JvB}\overline{\mathcal{B}} = \mathcal{B}' \setminus\{J_v^B\} if JvB∈B′J_v^B \in\mathcal{B}'.

Figure 2 illustrates the structure of the last mixed block M\mathcal{M} and the associated notations. We will now prove that the competitive ratio of Algorithm AOSA is 1+θ1+θ1+\frac{\theta}{1+\theta}. The proof is by contradiction. Assume, to the contrary, that there exists an instance for which the competitive ratio of Algorithm AOSA exceeds this value. Let I\mathcal{I} be a minimal counterexample instance—that is, an instance with the minimum number of jobs that violates the bound. Let σ\boldsymbol{\sigma} be the schedule produced by AOSA and π\boldsymbol{\pi} be an optimal schedule for instance I\mathcal{I}. Thus, we have:

Figure 2. An example of notations defined for σ\sigma.

Z(σ)−Z(π)>θ1+θZ(π).(2)Z(\boldsymbol{\sigma}) - Z(\boldsymbol{\pi}) > \frac{\theta}{1+\theta} Z(\boldsymbol{\pi}). \tag*{(2)}

In the remainder of this section, we analyze the smallest counterexample by deriving a collection of structural properties of the schedule σ\sigma. We then employ these properties to show that I\mathcal{I} cannot constitute a valid counterexample. We begin by presenting a series of fundamental observations about σ\sigma.

Observation 1. Let T0T_0 be the start time of a block in the schedule σ\sigma produced by Algorithm AOSA. Then the following properties hold:

(i) All jobs arriving before T0T_0 in the block belong to the same agent.

(ii) For each A-job JjAJ_j^A with release time rjA<T0r_j^A < T_0, we have

T0≤θ1+θpjA.T_0 \le\frac{\theta}{1+\theta}p_j^A.

(iii) For each B-job JjBJ_j^B with release time rjB<T0r_j^B < T_0, we have

T0≤11+θpjB.T_0 \le\frac{1}{1+\theta}p_j^B.

Observation 2. If the final contiguous A-job block A\mathcal{A} in the schedule σ\sigma begins immediately after an idle interval, then

Cmax⁡A(σ)≤(1+θ1+θ)Cmax⁡A(π).(3)C_{\max}^{A}(\sigma) \le\left(1+\frac{\theta}{1+\theta}\right)C_{\max}^{A}(\pi). \tag*{(3)}

Observation 3. If the final contiguous B-job block B\mathcal{B} in the schedule σ\sigma begins immediately after an idle interval, then

Cmax⁡B(σ)≤(1+θ1+θ)Cmax⁡B(π).(4)C_{\max}^{B}(\sigma) \le\left(1+\frac{\theta}{1+\theta}\right)C_{\max}^{B}(\pi). \tag*{(4)}

Lemma 1. Both A\mathcal{A} and B\mathcal{B} belong to the mixed block M\mathcal{M} in the schedule σ\sigma.

Proof. We prove the lemma by contradiction. Assume, without loss of generality, that A\mathcal{A} does not belong to M\mathcal{M}. This implies that A\mathcal{A} must constitute a pure A-block that starts after an idle time. By Observation 2, this leads to inequality (3).

Under this assumption, the set B\mathcal{B} cannot start after an idle interval. If it did, Observation 3 would yield inequality (4), and combining this with (3) would contradict our initial assumption (2). Therefore, B\mathcal{B} must be preceded by an A-job, denoted by JuAJ_u^A. Note that JuA∈MJ_u^A \in\mathcal{M} and JuA∉AJ_u^A \notin\mathcal{A}. This structural arrangement is illustrated in the Gantt chart in Figure 3.

Figure 3. A\mathcal{A} is a pure lock in σ\sigma.

From this schedule structure, we can establish the following makespans in σ\sigma:

Cmax⁡A(σ)=TA+P(A),(5)C_{\max}^{A}(\sigma) = T_A + P(\mathcal{A}), \tag*{(5)}
Cmax⁡B(σ)=TM+P(A′∪B′∪B).(6)C_{\max}^{B}(\sigma) = T_M + P(\mathcal{A}' \cup\mathcal{B}' \cup\mathcal{B}). \tag*{(6)}

Furthermore, any feasible schedule, including the optimal offline schedule π\pi, must process these jobs. Thus, we have the trivial lower bounds:

Cmax⁡A(π)≥P(A′∪A),(7)C_{\max}^{A}(\pi) \ge P(\mathcal A' \cup\mathcal A), \tag*{(7)}
Cmax⁡B(π)≥P(B′∪B).(8)C_{\max}^{B}(\pi) \ge P(\mathcal B' \cup\mathcal B). \tag*{(8)}

We now analyze the schedule structure by considering two cases based on the minimal release time of jobs in B\mathcal B.

Case 1. rmin⁡(B)≤tur_{\min}(\mathcal B) \le t_u.

At decision time tut_u (the start of job JuAJ_u^A) there are available jobs from both agents. We distinguish two subcases according to the ordering of rmin⁡(A′∪UtuA)r_{\min}(\mathcal A' \cup U_{t_u}^A) and rmin⁡(B′∪UtuB)r_{\min}(\mathcal B' \cup U_{t_u}^B).

  • rmin⁡(A′∪UtuA)≤rmin⁡(B′∪UtuB)r_{\min}(\mathcal A' \cup U_{t_u}^A) \le r_{\min}(\mathcal B' \cup U_{t_u}^B).

By Observation 1 every BB-job in M\mathcal M arrives no earlier than TMT_M, hence

Cmax⁡B(π)≥TM+P(B′∪B).(9)C_{\max}^{B}(\pi) \ge T_M + P(\mathcal B' \cup\mathcal B). \tag*{(9)}

Since Algorithm AOSA chooses an A-job to be processed at the decision point tut_u, we obtain

TM+P(B′∪B)>θ(P(A′)−TM).(10)T_M + P(\mathcal B' \cup\mathcal B) > \theta\bigl(P(\mathcal A') - T_M\bigr). \tag*{(10)}

Combining (9) and (10), regardless of whether TM≤θ1+θP(A′)T_M \le\frac{\theta}{1+\theta}P(\mathcal A') holds or not, we deduce that

Cmax⁡B(π)≥θ1+θP(A′).(11)C_{\max}^{B}(\pi) \ge\frac{\theta}{1+\theta}P(\mathcal A'). \tag*{(11)}

Together with (7), this yields

Z(π)≥θP(A′)+P(A).(12)Z(\pi) \ge\theta P(\mathcal A') + P(\mathcal A). \tag*{(12)}

If rmin⁡(A)<TAr_{\min}(\mathcal A) < T_A, then by Observation 1 we have TA≤θ1+θP(A)T_A \le\frac{\theta}{1+\theta}P(\mathcal A). Together with (5), (6), (7), and (9), this implies

Z(σ)−Z(π)≤TA+(θ−1)P(A′)≤θ1+θP(A)+θ21+θP(A′).\begin{aligned} Z(\sigma) - Z(\pi) \le T_A + (\theta- 1)P(\mathcal A') \\ &\le\frac{\theta}{1+\theta}P(\mathcal A) + \frac{\theta^2}{1+\theta}P(\mathcal A'). \end{aligned}

In view of (12), this contradicts (2).

If rmin⁡(A)≥TAr_{\min}(\mathcal A) \ge T_A, then

Cmax⁡A(π)≥TA+P(A).(13)C_{\max}^{A}(\pi) \ge T_A + P(\mathcal A). \tag*{(13)}

Combining this with (5), (6), and (9), we obtain

Z(σ)−Z(π)≤θP(A′).(14)Z(\sigma) - Z(\pi) \le\theta P(\mathcal A'). \tag*{(14)}

Moreover, since TA≥TM+P(A′)+P(B′∪B)T_A \ge T_M + P(\mathcal A') + P(\mathcal B' \cup\mathcal B), it follows from (9), (10), and (13) that

Z(π)≥(1+θ)P(A′).Z(\pi) \ge(1+\theta)P(\mathcal A').

Together with (14), this again contradicts (2).

  • rmin⁡(A′‾∪UtuA)>rmin⁡(B′‾∪UtuB)r_{\min}(\overline{\mathcal{A}'} \cup U_{t_u}^{A}) > r_{\min}(\overline{\mathcal{B}'} \cup U_{t_u}^{B}).

In this case, by Observation 1, all AA-jobs in M\mathcal{M} must have release times no earlier than TMT_M. This implies

Cmax⁡A(π)≥TM+P(A′∪A).(15)C_{\max}^{A}(\pi) \ge T_M + P(\mathcal{A}' \cup\mathcal{A}). \tag*{(15)}

Moreover, since Algorithm AOSA schedules job JuAJ_u^A at time tut_u, we further obtain

P(B′∪B)−TM>θ(TM+P(A′)).(16)P(\mathcal{B}' \cup\mathcal{B}) - T_M > \theta(T_M + P(\mathcal{A}')). \tag*{(16)}

Together with (5), (6), (8), (15), this yields

Z(σ)−Z(π)≤TA+(θ−1)(TM+P(A′))≤TA+θ−1θP(B′∪B).(17)\begin{aligned} Z(\sigma) - Z(\pi) &\le T_A + (\theta- 1)(T_M + P(\mathcal{A}'))\\ &\le T_A + \frac{\theta-1}{\theta}P(\mathcal{B}' \cup\mathcal{B}). \tag*{(17)} \end{aligned}

If rmin⁡(A)<TAr_{\min}(\mathcal{A}) < T_A, then by Observation 1 we have TA≤θ1+θP(A)T_A \le\frac{\theta}{1+\theta}P(\mathcal{A}). Combining this with (17), we obtain that

Z(σ)−Z(π)≤θ1+θ(P(A)+P(B′∪B)).Z(\sigma) - Z(\pi) \le\frac{\theta}{1+\theta}(P(\mathcal{A}) + P(\mathcal{B}' \cup\mathcal{B})).

In view of (7) and (8), this contradicts (2).

If rmin⁡(A)≥TAr_{\min}(\mathcal{A}) \ge T_A, then by combining (5), (6), (8), and (13), we obtain

Z(σ)−Z(π)≤θ(TM+P(A′)).(18)Z(\sigma) - Z(\pi) \le\theta(T_M + P(\mathcal{A}')). \tag*{(18)}

Moreover, since Cmax⁡A(π)≥TA≥TM+P(A′)+P(B′∪B)C_{\max}^{A}(\pi) \ge T_A \ge T_M + P(\mathcal{A}') + P(\mathcal{B}' \cup\mathcal{B}), it follows from (16) that Z(π)≥(1+θ)(TM+P(A′))Z(\pi) \ge(1+\theta)(T_M + P(\mathcal{A}')). Together with (18), this again contradicts (2).

Case 2. rmin⁡(B)>tur_{\min}(\mathcal{B}) > t_u. In this case, all jobs in B\mathcal{B} arrive strictly after tut_u, and thus UtuB=∅U_{t_u}^{B} = \varnothing. Consequently,

Cmax⁡B(π)≥tu+P(B).(19)C_{\max}^{B}(\pi) \ge t_u + P(\mathcal{B}). \tag*{(19)}

We further show that

tu≥θ1+θpuA.(20)t_u \ge\frac{\theta}{1+\theta}p_u^A. \tag*{(20)}

Indeed, rmin⁡(B)>tur_{\min}(\mathcal{B}) > t_u implies that UtuB=∅U_{t_u}^{B} = \varnothing. If inequality (20) were violated, then by Algorithm AOSA (which schedules JuAJ_u^A at tut_u), there would be at least one other available AA-job at that time, with JuAJ_u^A being the largest. In that case, all available AA-jobs other than JuAJ_u^A belong to A\mathcal{A}, and JuAJ_u^A and the remaining available AA-jobs would be scheduled within the same block, contradicting the assumption that A\mathcal{A} is a pure block.

Again, we consider two subcases based on the value of rmin⁡(A)r_{\min}(\mathcal{A}).

  • rmin⁡(A)<TAr_{\min}(\mathcal{A}) < T_A, then by Observation 1 we have TA≤θ1+θP(A)T_A \le\frac{\theta}{1+\theta}P(\mathcal{A}). Combining this with (5), (6), (7), and (19), we deduce

Z(σ)−Z(π)≤TA−P(A′)+θpuA≤θ1+θ(P(A)+θpuA).(21)\begin{aligned} Z(\sigma) - Z(\pi) &\le T_A - P(\mathcal{A}') + \theta p_u^A\\ &\le\frac{\theta}{1+\theta}(P(\mathcal{A}) + \theta p_u^A). \tag*{(21)} \end{aligned}

The last inequality follows from P(A′)≥puAP(\mathcal{A}') \ge p_u^A and θ−1≤θ21+θ\theta- 1 \le\frac{\theta^2}{1+\theta}.

Furthermore, noting that P(A′)≥puAP(\mathcal{A}') \ge p_u^A and Cmax⁡A(π)≥P(A′∪A)C_{\max}^{A}(\pi) \ge P(\mathcal{A}' \cup\mathcal{A}), and combining (19) with (20), we obtain

Z(π)≥P(A)+θpuA.Z(\pi) \ge P(\mathcal{A}) + \theta p_u^A.

Together with (21), this leads to a contradiction with (2).

  • rmin⁡(A)≥TAr_{\min}(\mathcal{A}) \ge T_{\mathcal{A}}. Combining (5), (6), (13), and (19), we obtain

Z(σ)−Z(π)≤θpuA.Z(\sigma)-Z(\pi)\le\theta p_u^{\mathcal{A}}.

Furthermore, noting that TA≥tu+puAT_{\mathcal{A}} \ge t_u+p_u^{\mathcal{A}}, and combining (13), (19), and (20), we deduce

Z(π)≥TA+θtu≥(1+θ)puA.Z(\pi)\ge T_{\mathcal{A}}+\theta t_u\ge(1+\theta)p_u^{\mathcal{A}}.

These inequalities again contradict (2).

Therefore, A\mathcal{A} must be contained in the block M\mathcal{M}. By a similar argument, B\mathcal{B} also belongs to the mixed block in σ\sigma.

This completes the proof of the lemma. □\square

By Lemma 1, both A\mathcal{A} and B\mathcal{B} must belong to the same mixed block M\mathcal{M}. Hence, the jobs in A∪B\mathcal{A}\cup\mathcal{B} are processed consecutively in σ\sigma. It follows that at least one of JuAJ_u^{\mathcal{A}} and JvBJ_v^{\mathcal{B}} exists. In fact, we shall prove in the subsequent lemmas that if I\mathcal{I} is a counterexample, then both JuAJ_u^{\mathcal{A}} and JvBJ_v^{\mathcal{B}} must exist.

Suppose next that B\mathcal{B} is scheduled immediately after an idle interval in σ\sigma. In this case, JvBJ_v^{\mathcal{B}} necessarily exists. The corresponding Gantt chart is illustrated in Figure 4. With respect to σ\sigma, we then obtain

Figure 4. B\mathcal{B} is scheduled immediately after an idle interval in σ\sigma.

Cmax⁡A(σ)=TB+P(B)+P(A),(22)C_{\max}^{\mathcal{A}}(\sigma)=T_{\mathcal{B}}+P(\mathcal{B})+P(\mathcal{A}), \tag*{(22)}
Cmax⁡B(σ)=TB+P(B).(23)C_{\max}^{\mathcal{B}}(\sigma)=T_{\mathcal{B}}+P(\mathcal{B}). \tag*{(23)}

Lemma 2. If B\mathcal{B} starts immediately after an idle interval in σ\sigma, then Cmax⁡A(π)<Cmax⁡B(π)C_{\max}^{\mathcal{A}}(\pi)<C_{\max}^{\mathcal{B}}(\pi) must hold.

Proof. Suppose, for the sake of contradiction, that in σ\sigma B\mathcal{B} starts immediately after an idle interval and Cmax⁡A(π)≥Cmax⁡B(π)C_{\max}^{\mathcal{A}}(\pi)\ge C_{\max}^{\mathcal{B}}(\pi). We will derive a contradiction to (2).

To derive lower bounds for the optimal schedule π\pi, let ToptT_{\mathrm{opt}} denote the earliest start time, under π\pi, of any job in M\mathcal{M}. Then we obtain

Cmax⁡A(π)≥Topt+P(A∪B)(24)C_{\max}^{\mathcal{A}}(\pi)\ge T_{\mathrm{opt}}+P(\mathcal{A}\cup\mathcal{B}) \tag*{(24)}
Cmax⁡B(π)≥Topt+P(B)(25)C_{\max}^{\mathcal{B}}(\pi)\ge T_{\mathrm{opt}}+P(\mathcal{B}) \tag*{(25)}

We distinguish two cases, depending on whether Topt≤TBT_{\mathrm{opt}}\le T_{\mathcal{B}} or not.

  • Topt≥TBT_{\mathrm{opt}}\ge T_{\mathcal{B}}. Substituting the condition Topt≥TBT_{\mathrm{opt}}\ge T_{\mathcal{B}} into the lower bounds from (24) and (25) and comparing them with the makespans in σ\sigma (from (22) and (23)), we can obtain that Z(σ)≤Z(π)Z(\sigma)\le Z(\pi). This directly contradicts (2).

  • Topt<TBT_{\mathrm{opt}}<T_{\mathcal{B}}. This condition implies that at least one job in A∪B\mathcal{A}\cup\mathcal{B} is released and starts before time TBT_{\mathcal{B}}.

If the job starting before TBT_{\mathcal{B}} belongs to B\mathcal{B}, then, by Observation 1,

P(B)≥(1+θ)TB.P(\mathcal{B})\ge(1+\theta)T_{\mathcal{B}}.

Combining this with (22), (23), (24), and (25) yields

Z(σ)−Z(π)≤P(B).Z(\sigma) - Z(\pi) \le P(\mathcal{B}).

Together with (24) and (25), this contradicts (2).

If the job starting before TBT_B belongs to A\mathcal{A}, by Observation 1, its processing time is at least (1+1θ)TB(1+\frac{1}{\theta})T_B. In π\pi, all B\mathcal{B}-jobs start after this A\mathcal{A}-job. Thus,

Cmax⁡B(π)≥(1+1θ)TB+P(B).C_{\max}^{\mathcal{B}}(\pi) \ge\left(1+\frac{1}{\theta}\right)T_B+P(\mathcal{B}).

Combining this with (22), (23), and (24) yields Z(σ)≤Z(π)Z(\sigma) \le Z(\pi), contradicting (2).

This completes the proof.

Lemma 2 shows that Cmax⁡A(π)<Cmax⁡B(π)C_{\max}^{\mathcal{A}}(\pi)<C_{\max}^{\mathcal{B}}(\pi). Consequently, we obtain the following lower bounds on the optimal schedule π\pi:

Cmax⁡A(π)≥Topt+P(A),(26)C_{\max}^{\mathcal{A}}(\pi) \ge T_{\mathrm{opt}}+P(\mathcal{A}), \tag*{(26)}
Cmax⁡B(π)≥Topt+P(A)+P(B),(27)C_{\max}^{\mathcal{B}}(\pi) \ge T_{\mathrm{opt}}+P(\mathcal{A})+P(\mathcal{B}), \tag*{(27)}

where ToptT_{\mathrm{opt}} denotes the earliest starting time of the jobs in M\mathcal{M} under π\pi.

Lemma 3. If B\mathcal{B} is scheduled immediately after an idle interval in σ\sigma, then it holds that rmin⁡(A)>tvr_{\min}(\mathcal{A})>t_v.

Proof. We argue by contradiction. Assume, for the sake of contradiction, that rmin⁡(A)≤tvr_{\min}(\mathcal{A})\le t_v. We distinguish two cases depending on whether rmin⁡(A)<rmin⁡(B)r_{\min}(\mathcal{A})<r_{\min}(\mathcal{B}) holds.

Case 1: rmin⁡(A)<rmin⁡(B)r_{\min}(\mathcal{A})<r_{\min}(\mathcal{B}).

At time tvt_v, both some A\mathcal{A}-jobs and job JvBJ_v^{\mathcal{B}} are available. Since Algorithm AOSA gives priority to B\mathcal{B}-jobs, we obtain

θP(A)≥(1+θ)TB+P(B).\theta P(\mathcal{A}) \ge(1+\theta)T_B+P(\mathcal{B}).

By combining this inequality with (26) and (27), we obtain

Z(π)≥(1+θ)TB+θP(B)+P(A)+P(B).Z(\pi) \ge(1+\theta)T_B+\theta P(\mathcal{B})+P(\mathcal{A})+P(\mathcal{B}).

This bound, together with (22) and (23), contradicts (2).

Case 2: rmin⁡(A)≥rmin⁡(B)r_{\min}(\mathcal{A})\ge r_{\min}(\mathcal{B}).

Again, at time tvt_v, both A\mathcal{A}-jobs and JvBJ_v^{\mathcal{B}} are available, and Algorithm AOSA prioritizes B\mathcal{B}-jobs. Hence,

θP(A)>P(B)−(1+θ)TB.(28)\theta P(\mathcal{A}) > P(\mathcal{B})-(1+\theta)T_B. \tag*{(28)}

We claim that

Z(π)≥(1+θ)TB+(1+θ)P(A)+θP(B).(29)Z(\pi) \ge(1+\theta)T_B+(1+\theta)P(\mathcal{A})+\theta P(\mathcal{B}). \tag*{(29)}

If Topt≥TBT_{\mathrm{opt}}\ge T_B, then (29) follows directly from (22) and (23). Otherwise, there must exist a B\mathcal{B}-job starting before TBT_B in π\pi. By Observation 1, that job has processing time at least (1+θ)TB(1+\theta)T_B. Since all A\mathcal{A}-jobs start after this B\mathcal{B}-job in π\pi, we have

Cmax⁡A(π)≥(1+θ)TB+P(A).C_{\max}^{\mathcal{A}}(\pi) \ge(1+\theta)T_B+P(\mathcal{A}).

Combining this bound with (27) yields (29).

Finally, using (22), (23), and (29), we obtain

Z(σ)−Z(π)≤θP(B).Z(\sigma)-Z(\pi) \le\theta P(\mathcal{B}).

Together with (28) and (29), this contradicts (2). This completes the proof.

Now we are ready to establish the existence of both JuAJ^{A}_{u} and JvBJ^{B}_{v}.

Lemma 4. In schedule σ\sigma, there exists an A-job that immediately precedes B, and, by symmetry, there exists a B-job that immediately precedes A.

Proof. We argue by contradiction. Assume, to the contrary, that B is scheduled immediately after an idle interval in σ\sigma. Then A must follow B consecutively in σ\sigma. In this case, the corresponding Gantt chart of the schedule is illustrated in Figure 4.

From Lemmas 2,3, we have Cmax⁡A(π)<Cmax⁡B(π)C^{A}_{\max}(\pi) < C^{B}_{\max}(\pi) and rmin⁡(A)>tvr_{\min}(\mathcal{A}) > t_v. Since rmin⁡(A)>tvr_{\min}(\mathcal{A}) > t_v, it follows that

Cmax⁡A(π)≥tv+P(A).(30)C^{A}_{\max}(\pi) \ge t_v + P(\mathcal{A}). \tag*{(30)}

Combining this with (22), (23), and (27), we obtain

Z(σ)−Z(π)≤θ(TB−Topt)+pvB.(31)Z(\sigma) - Z(\pi) \le\theta(T_B - T_{\mathrm{opt}}) + p^{B}_{v}. \tag*{(31)}

Since JvBJ^{B}_{v} is the last B-job and no A-jobs are available at time tvt_v, it follows directly from Observation 1 that

tv≥11+θpvB.(32)t_v \ge\frac{1}{1+\theta}p^{B}_{v}. \tag*{(32)}

We now distinguish two cases according to the value of Cmax⁡B(π)C^{B}_{\max}(\pi).

Case 1: Cmax⁡B(π)≥tv+pvBC^{B}_{\max}(\pi) \ge t_v + p^{B}_{v}. Combining this with (22), (23), and (30), we deduce that

Z(σ)−Z(π)≤pvB.Z(\sigma) - Z(\pi) \le p^{B}_{v}.

Moreover, together with Cmax⁡B(π)≥tv+pvBC^{B}_{\max}(\pi) \ge t_v + p^{B}_{v}, (30), and (32), this leads to a contradiction with (2).

Case 2: Cmax⁡B(π)<tv+pvBC^{B}_{\max}(\pi) < t_v + p^{B}_{v}. In this case, job JvBJ^{B}_{v} must start before tvt_v in π\pi. We claim that

Cmax⁡A(π)<TB+pvB.(33)C^{A}_{\max}(\pi) < T_B + p^{B}_{v}. \tag*{(33)}

Otherwise, if Cmax⁡A(π)≥TB+pvBC^{A}_{\max}(\pi) \ge T_B + p^{B}_{v}, then together with Cmax⁡B(π)≥Cmax⁡A(π)C^{B}_{\max}(\pi) \ge C^{A}_{\max}(\pi) and (31), we obtain a contradiction with (2).

Since JvBJ^{B}_{v} starts before tvt_v and rmin⁡(A)>tvr_{\min}(\mathcal{A}) > t_v, i.e., all jobs in A\mathcal{A} are scheduled after JvBJ^{B}_{v} and tvt_v in π\pi, we have

Cmax⁡A(π)≥max⁡{pvB,tv}+P(A).(34)C^{A}_{\max}(\pi) \ge\max\{p^{B}_{v}, t_v\} + P(\mathcal{A}). \tag*{(34)}

Note that tv=TB+P(B)−pvBt_v = T_B + P(\mathcal{B}) - p^{B}_{v}, Cmax⁡B(π)≥P(B)C^{B}_{\max}(\pi) \ge P(\mathcal{B}), and P(B)=P(B‾)+pvBP(\mathcal{B}) = P(\overline{\mathcal{B}}) + p^{B}_{v}. Combining these with (22), (23), and (34), we deduce that

Z(σ)−Z(π)≤min⁡{tv,pvB}+θTB,(35)Z(\sigma) - Z(\pi) \le\min\{t_v, p^{B}_{v}\} + \theta T_B, \tag*{(35)}
Z(π)≥θP(B‾)+θpvB+max⁡{tv,pvB}.(36)Z(\pi) \ge\theta P(\overline{\mathcal{B}}) + \theta p^{B}_{v} + \max\{t_v, p^{B}_{v}\}. \tag*{(36)}

Moreover, we note the following two properties of JvBJ^{B}_{v}:

  1. JvBJ^{B}_{v} starts before TBT_B in π\pi. This holds because JvBJ^{B}_{v} starts before the jobs in A\mathcal{A} (as rmin⁡(A)>tvr_{\min}(\mathcal{A}) > t_v), and by (33) its completion time cannot exceed TB+pvBT_B + p^{B}_{v}.

(ii) JvBJ_v^B is the largest BB-job in B\mathcal{B}. This follows since (33) and (34), together with tv=TB+P(B‾)−pvBt_v = T_B + P(\overline{B}) - p_v^B, imply that pvBp_v^B dominates the processing times of all other BB-jobs.

Since no AA-jobs are available while the jobs in B\mathcal{B} are being scheduled, and Procedure B does not assign priority to the largest BB-job JvBJ_v^B, we distinguish two subcases.

Case 2.1: TB+P(B‾)≤pvBT_B + P(\overline{B}) \leq p_v^B. By Procedure B, when the job immediately preceding JvBJ_v^B is scheduled, it must hold that

(1+θ)TB+11+θP(B‾)≤pvB.(1+\theta)T_B + \frac{1}{1+\theta}P(\overline{B}) \leq p_v^B.

Combining this with (34) and the fact that Cmax⁡B(π)≥P(B‾)+pvBC_{\max}^B(\pi) \geq P(\overline{B}) + p_v^B, we obtain

Z(π)≥θP(B‾)+θpvB+pvB≥(1+θ)((1+θ)TB+P(B‾)).Z(\pi) \geq\theta P(\overline{B}) + \theta p_v^B + p_v^B \geq(1+\theta)((1+\theta)T_B + P(\overline{B})).

Together with tv=TB+P(B‾)t_v = T_B + P(\overline{B}) and (35), this contradicts (2).

Case 2.2: TB+P(B‾)>pvBT_B + P(\overline{B}) > p_v^B. By Procedure B, when the job before JvBJ_v^B is scheduled, we have

(θ−11+θ)TB+11+θpvB≤P(B‾).\left(\theta- \frac{1}{1+\theta}\right)T_B + \frac{1}{1+\theta}p_v^B \leq P(\overline{B}).

Combined this with (34) and Cmax⁡B(π)≥P(B‾)+pvBC_{\max}^B(\pi) \geq P(\overline{B}) + p_v^B, tv=TB+P(B‾)t_v = T_B + P(\overline{B}), we have

Z(π)≥(1+θ)(θTB+pvB).Z(\pi) \geq(1+\theta)(\theta T_B + p_v^B).

which along with (35), leads a contradiction with (2).

By symmetry, the second statement follows upon swapping A\mathcal{A} and B\mathcal{B}. This completes the proof.

By Lemma 4, the jobs JuAJ_u^A and JvBJ_v^B, which are processed immediately before B\mathcal{B} and A\mathcal{A} in σ\sigma, always exist. If JuA∉AJ_u^A \notin\mathcal{A}, then JvB∈BJ_v^B \in\mathcal{B}; the corresponding Gantt chart of σ\sigma is shown in Figure 5. In this case, the following equalities hold for the two agents’ makespans in σ\sigma:

Figure 5. The Gantt chart of schedule in which JuA∉AJ_u^A \notin\mathcal{A}.

Cmax⁡A(σ)=TM+P(B′∪A′∪B∪A),(37)C_{\max}^A(\sigma) = T_M + P(B' \cup A' \cup B \cup A), \tag*{(37)}
Cmax⁡B(σ)=TM+P(B′∪A′∪B).(38)C_{\max}^B(\sigma) = T_M + P(B' \cup A' \cup B). \tag*{(38)}

In what follows, we derive further conclusions under the assumption that I\mathcal{I} is a counterexample.

Lemma 5. If JuA∉AJ_u^A \notin\mathcal{A} and rmin⁡(B)≤tur_{\min}(\mathcal{B}) \leq t_u, then Cmax⁡A(π)<Cmax⁡B(π)C_{\max}^A(\pi) < C_{\max}^B(\pi).

Proof. Assume, for contradiction, that Cmax⁡A(π)≥Cmax⁡B(π)C_{\max}^A(\pi) \geq C_{\max}^B(\pi) while JuA∉AJ_u^A \notin\mathcal{A} and rmin⁡(B)≤tur_{\min}(\mathcal{B}) \leq t_u in σ\sigma. We will derive a contradiction to (2).

From Cmax⁡A(π)≥Cmax⁡B(π)C_{\max}^A(\pi) \geq C_{\max}^B(\pi), we obtain

Z(π)≥P(B′∪B∪A′∪A)+θP(B′∪B).(39)Z(\pi) \geq P(B' \cup B \cup A' \cup A) + \theta P(B' \cup B). \tag*{(39)}

Combining this with (37) and (38) yields

Z(σ)−Z(π)≤(1+θ)TM+θP(A′).(40)Z(\sigma) - Z(\pi) \leq(1+\theta)T_M + \theta P(A'). \tag*{(40)}

We next distinguish two cases according to the relative order between rmin⁡(A∪A′)r_{\min}(\mathcal{A} \cup A') and B∪B′)\mathcal{B} \cup B'). Case 1: rmin⁡(A∪A′)≥rmin⁡(B∪B′)r_{\min}(A \cup A') \ge r_{\min}(B \cup B').

In this case, since JuAJ_u^A is scheduled at time tut_u, the algorithm implies that

θP(A′)≤P(B∪B′)−(1+θ)TM.\theta P(A') \le P(B \cup B') - (1+\theta)T_M.

Together with (39) and (40), this contradicts (2).

Case 2: rmin⁡(A∪A′)<rmin⁡(B∪B′)r_{\min}(A \cup A') < r_{\min}(B \cup B').

In this case, since JuAJ_u^A is scheduled at time tut_u, the algorithm guarantees

θP(A′)≤P(B∪B′)+(1+θ)TM.(41)\theta P(A') \le P(B \cup B') + (1+\theta)T_M. \tag*{(41)}

We now claim that

Z(π)≥(1+θ)TM+P(B′∪B∪A′∪A)+θP(B′∪B).(42)Z(\pi) \ge(1+\theta)T_M + P(B' \cup B \cup A' \cup A) + \theta P(B' \cup B). \tag*{(42)}

Indeed, if no jobs start before TMT_M in π\pi, then (42) holds immediately. Otherwise, there is a job starting before TMT_M in π\pi. By Observation 1 and the initial condition of this case, the job must be an AA-job with processing time no less than θ+1θTM\frac{\theta+1}{\theta}T_M. Since all BB-jobs would be scheduled after this AA-job, it follows that

Cmax⁡B(π)≥P(B′∪B)+θ+1θTM.C_{\max}^{B}(\pi) \ge P(B' \cup B) + \frac{\theta+1}{\theta}T_M.

This, together with the fact that Cmax⁡A(π)≥P(B′∪B∪A′∪A)C_{\max}^{A}(\pi) \ge P(B' \cup B \cup A' \cup A), implies that (42) holds. Finally, combining (42) with (37) and (38) yields

Z(σ)−Z(π)≤θP(A′).Z(\sigma) - Z(\pi) \le\theta P(A').

Together with (41) and (42), this contradicts (2).

In both cases we reach a contradiction. Hence Cmax⁡A(π)<Cmax⁡B(π)C_{\max}^{A}(\pi) < C_{\max}^{B}(\pi), as claimed. This completes the proof.

Lemma 5 implies that the following lower bounds always hold for π\pi:

Cmax⁡A(π)≥P(A′∪A),(43)C_{\max}^{A}(\pi) \ge P(A' \cup A), \tag*{(43)}
Cmax⁡B(π)≥P(A′∪A)+P(B′∪B).(44)C_{\max}^{B}(\pi) \ge P(A' \cup A) + P(B' \cup B). \tag*{(44)}

Lemma 6. If JuA∉AJ_u^A \notin A and rmin⁡(B)≤tur_{\min}(B) \le t_u, then rmin⁡(A)>tvr_{\min}(A) > t_v.

Proof. Suppose, for contradiction, that rmin⁡(A)≤tvr_{\min}(A) \le t_v. By Observation 1, at most one agent has a job that starts before TMT_M in π\pi. We distinguish two cases according to whether a job in M\mathcal{M} starts before TMT_M in π\pi.

Case 1: There exists an AA-job that starts before TMT_M in π\pi. By Observation 1, it follows that rmin⁡(A′∪A)<rmin⁡(B′∪B)r_{\min}(A' \cup A) < r_{\min}(B' \cup B). Since at time tvt_v job JvBJ_v^B is scheduled first, by the rule of Algorithm AOSA we obtain

P(B′∪B)≤θP(A′∪A)−(1+θ)TM.(45)P(B' \cup B) \le\theta P(A' \cup A) - (1+\theta)T_M. \tag*{(45)}

Combining (45) with (37), (38), (43) and (44), we get

Z(σ)−Z(π)≤θP(A′).Z(\sigma) - Z(\pi) \le\theta P(A').

This, together with (43) and (44), contradicts (2).

Case 2: All AA-jobs start at or after TMT_M in π\pi. We claim that

Z(π)≥θP(B′∪B)+(1+θ)P(A′∪A)+(1+θ)TM.(46)Z(\pi) \ge\theta P(B' \cup B) + (1+\theta)P(A' \cup A) + (1+\theta)T_M. \tag*{(46)}

Indeed, if all BB-jobs also start at or after TMT_M in π\pi, then (46) follows immediately from (37) and (38). Otherwise, there exists a BB-job that starts before TMT_M in π\pi. By Observation 1, the processing time of this BB-job is at least (1+θ)TM(1+\theta)T_M. Since all AA-jobs start after this BB-job in π\pi, we obtain

Cmax⁡A(π)≥(1+θ)TM+P(A′∪A),C_{\max}^{A}(\pi) \ge(1+\theta)T_M + P(A' \cup A),

which, together with (44) implies that (46) holds.

Combining (46) with (37) and (38), we obtain

Z(σ)−Z(π)≤θP(B′∪B).(47)Z(\sigma) - Z(\pi) \le\theta P(B' \cup B). \tag*{(47)}

Note that at time tvt_v, job JvBJ_v^B is scheduled prior to the available jobs in A\mathcal{A}. According to the scheduling rule of Algorithm AOSA, this implies that

P(B′∪B)≤(1+θ)TM+θP(A′∪A).P(B' \cup B) \le(1+\theta)T_M + \theta P(A' \cup A).

Combining this with (46), we obtain that Z(π)≥(1+θ)P(B′∪B)Z(\pi) \ge(1+\theta)P(B' \cup B). This, combined with (47), contradicts (2).

Hence the assumption is false and rmin⁡(A)>tvr_{\min}(\mathcal{A}) > t_v. This completes the proof.

Lemma 7. If rmin⁡(B)≤tur_{\min}(\mathcal{B}) \le t_u, then JuA∈AJ_u^A \in\mathcal{A}.

Proof. We argue by contradiction. Suppose, to the contrary, that JuA∉AJ_u^A \notin\mathcal{A} while rmin⁡(B)≤tur_{\min}(\mathcal{B}) \le t_u. The condition JuA∉AJ_u^A \notin\mathcal{A} implies that, in σ\sigma, all jobs in A\mathcal{A} are processed after B\mathcal{B}. In this case, the Gantt chart of σ\sigma is shown in Figure 5.

By Lemmas 5 and 6, we have Cmax⁡A(π)<Cmax⁡B(π)C_{\max}^{A}(\pi) < C_{\max}^{B}(\pi) and rmin⁡(A)>tvr_{\min}(\mathcal{A}) > t_v. By the fact that tv=TM+P(A′)+P(B′∪B)−pvBt_v = T_M + P(A') + P(B' \cup B) - p_v^B and rmin⁡(A)>tvr_{\min}(\mathcal{A}) > t_v, we obtain

Cmax⁡A(π)≥TM+P(A′∪A)+P(B′∪B)−pvB.(48)C_{\max}^{A}(\pi) \ge T_M + P(A' \cup A) + P(B' \cup B) - p_v^B. \tag*{(48)}

Combining this with (37), (38), and (44), we deduce that

Z(σ)−Z(π)≤pvB+θTM.(49)Z(\sigma) - Z(\pi) \le p_v^B + \theta T_M. \tag*{(49)}

Note that at time tvt_v, the only available job is JvBJ_v^B. By Observation 1, we have

tv≥11+θpvB.(50)t_v \ge\frac{1}{1+\theta}p_v^B. \tag*{(50)}

In what follows, we distinguish three cases according to the start time of JvBJ_v^B in π\pi.

Case 1: JvBJ_v^B starts at or after tvt_v in π\pi.

In this case, Cmax⁡B(π)≥Cmax⁡B(σ)C_{\max}^{B}(\pi) \ge C_{\max}^{B}(\sigma). Combining this with (37), (48), we obtain

Z(σ)−Z(π)≤pvB.(51)Z(\sigma) - Z(\pi) \le p_v^B. \tag*{(51)}

Moreover, it follows from Cmax⁡A(π)>tvC_{\max}^{A}(\pi) > t_v and Cmax⁡B(π)≥tv+pvBC_{\max}^{B}(\pi) \ge t_v + p_v^B, together with (50), that

Z(π)≥(1+θ)pvB.Z(\pi) \ge(1+\theta)p_v^B.

Together with (51), this contradicts (2).

Case 2: JvBJ_v^B starts in π\pi between TMT_M and tvt_v.

Since rmin⁡(A)>tvr_{\min}(\mathcal{A}) > t_v, we obtain

Cmax⁡A(π)≥TM+pvB.C_{\max}^{A}(\pi) \ge T_M + p_v^B.

Combining this with the inequality Cmax⁡A(π)<Cmax⁡B(π)C_{\max}^{A}(\pi) < C_{\max}^{B}(\pi), it follows that

Z(π)≥(1+θ)(TM+pvB).(52)Z(\pi) \ge(1+\theta)(T_M+p_v^B). \tag*{(52)}

This, together with (49), contradict (2).

Case 3: JvBJ_v^B starts before tMt_M in π\pi.

This implies that rvB<TMr_v^B < T_M and all AA-jobs start after JvBJ_v^B in π\pi. Therefore,

Cmax⁡A(π)≥pvB+P(A′∪A).(53)C_{\max}^{A}(\pi) \ge p_v^B + P(A' \cup A). \tag*{(53)}

By Observation 1, rvB<TMr_v^B < T_M implies that

pvB≥(1+θ)TM.(54)p_v^B \ge(1+\theta)T_M. \tag*{(54)}

Define x:=P(B′∪B)−pvBx := P(B' \cup B) - p_v^B. Then

Cmax⁡B(π)≥pvB+x,C_{\max}^{B}(\pi) \ge p_v^B + x,

which, together with (53), implies

Z(π)≥(1+θ)pvB+θx.(55)Z(\pi) \ge(1+\theta)p_v^B + \theta x. \tag*{(55)}

Moreover, combining (37), (38), (44), and (53), we obtain

Z(σ)−Z(π)≤(1+θ)TM+x.(56)Z(\sigma) - Z(\pi) \le(1+\theta)T_M + x. \tag*{(56)}

If x≥pvBx \ge p_v^B, then combining (49), (54), and (55), yields a contradiction to (2).

If x<pvBx < p_v^B, then JvBJ_v^B is the largest BB-job. Since no AA-job is available when the BB-job immediately preceding JvBJ_v^B is scheduled, Procedure B ensures

(1+θ)TM+11+θx≤pvB.(1+\theta)T_M + \frac{1}{1+\theta}x \le p_v^B.

Combining this with (56), we derive

Z(σ)−Z(π)≤pvB+θ1+θx.(57)Z(\sigma) - Z(\pi) \le p_v^B + \frac{\theta}{1+\theta}x. \tag*{(57)}

which, together with (55), again yields a contradiction with (2).

This completes the proof.

By an analogous argument, we obtain the following lemma.

Lemma 8. In schedule σ\sigma, if rmin⁡(A)≤tvr_{\min}(\mathcal{A}) \le t_v, then JvB∈BJ_v^B \in\mathcal{B}.

Lemma 9. If rmin⁡(B)>tur_{\min}(\mathcal{B}) > t_u, then JuA∉AJ_u^A \notin\mathcal{A}.

Proof. We argue by contradiction. Suppose that rmin⁡(B)>tur_{\min}(\mathcal{B})>t_u and JuA∈AJ_u^A\in\mathcal{A}. Under this assumption, JvB∉BJ_v^B\notin\mathcal{B}; hence all jobs in B\mathcal{B} appear at the tail of the schedule σ\sigma. In this case, the Gantt chart of σ\sigma is shown in Figure 6. Thus,

Figure 6. The Scenario with rmin⁡(B)>tur_{\min}(\mathcal{B})>t_u and JuA∈AJ_u^A\in\mathcal{A} in σ\sigma.

Z(σ)=tv+pvB+P(A)+θ(tv+pvB+P(A)+P(B)).(58)Z(\sigma)=t_v+p_v^B+P(\mathcal{A})+\theta\left(t_v+p_v^B+P(\mathcal{A})+P(\mathcal{B})\right). \tag*{(58)}

By Lemma 8, the condition JvB∉BJ_v^B\notin\mathcal{B} implies rmin⁡(A)>tvr_{\min}(\mathcal{A})>t_v. Together with rmin⁡(B)>tur_{\min}(\mathcal{B})>t_u, we obtain

Cmax⁡A(π)≥tv+P(A)(59)C_{\max}^A(\pi)\ge t_v+P(\mathcal{A}) \tag*{(59)}
Cmax⁡B(π)≥tu+P(B).(60)C_{\max}^B(\pi)\ge t_u+P(\mathcal{B}). \tag*{(60)}

Combining (58), (59), and (60) with the identity tu=tv+pvB+P(A)t_u=t_v+p_v^B+P(\mathcal{A}), we deduce

Z(σ)−Z(π)≤θpuA+pvB.(61)Z(\sigma)-Z(\pi)\le\theta p_u^A+p_v^B. \tag*{(61)}

We now distinguish two cases based on the relative order of Cmax⁡A(π)C_{\max}^A(\pi) and Cmax⁡B(π)C_{\max}^B(\pi).

Case 1: Cmax⁡A(π)≥Cmax⁡B(π)C_{\max}^A(\pi)\ge C_{\max}^B(\pi).

If JuAJ_u^A starts after all BB-jobs in π\pi, then, since rmin⁡(B)>tur_{\min}(\mathcal{B})>t_u, we have

Cmax⁡A(π)>tu+puA.(62)C_{\max}^A(\pi)>t_u+p_u^A. \tag*{(62)}

Recalling that tu=tv+pvB+P(A)t_u=t_v+p_v^B+P(\mathcal{A}) and combining (62) with (58) and (60), we obtain

Z(σ)−Z(π)≤θpuA.(63)Z(\sigma)-Z(\pi)\le\theta p_u^A. \tag*{(63)}

At time tut_u, JuAJ_u^A is the only available job. By Observation 1,

tu≥θ1+θpuA,t_u\ge\frac{\theta}{1+\theta}p_u^A,

which, together with (60), (62), and (63), yields a contradiction to (2).

If, instead, JuAJ_u^A is scheduled before some BB-jobs in π\pi, then

Cmax⁡B(π)≥puA+pvB.C_{\max}^B(\pi)\ge p_u^A+p_v^B.

Combining this with Cmax⁡A(π)≥Cmax⁡B(π)C_{\max}^A(\pi)\ge C_{\max}^B(\pi) and (61), we again obtain a contradiction to (2).

Case 2: Cmax⁡A(π)<Cmax⁡B(π)C_{\max}^A(\pi)<C_{\max}^B(\pi).

If JvBJ_v^B starts at or after tvt_v in π\pi, then, since rmin⁡(A∪B)>tvr_{\min}(\mathcal{A}\cup\mathcal{B})>t_v, we have

Cmax⁡B(π)≥tv+pvB+P(A)+P(B).(64)C_{\max}^B(\pi)\ge t_v+p_v^B+P(\mathcal{A})+P(\mathcal{B}). \tag*{(64)}

This together with (58) and (59), implies that

Z(σ)−Z(π)≤pvB.(65)Z(\sigma)-Z(\pi)\le p_v^B. \tag*{(65)}

At time tvt_v, JvBJ_v^B is the only available job. Hence, by Observation 1,

tv≥11+θpvB,t_v\ge\frac{1}{1+\theta}p_v^B,

which, together with (59), (64), and (65), contradicts (2).

If instead JvBJ_v^B starts before tvt_v in π\pi, then since rmin⁡(A)>tvr_{\min}(\mathcal{A}) > t_v, we obtain

Cmax⁡A(π)≥pvB+puA.C_{\max}^A(\pi) \ge p_v^B + p_u^A.

Combining this with Cmax⁡A(π)<Cmax⁡B(π)C_{\max}^A(\pi) < C_{\max}^B(\pi) and (61), we again obtain a contradiction to (2).

This completes the proof.

By combining the previous three lemmas, we obtain the following results.

Lemma 10. rmin⁡(B)>tur_{\min}(\mathcal{B}) > t_u holds if and only if JuA∉AJ_u^A \notin\mathcal{A}.

Lemma 11. rmin⁡(A)>tvr_{\min}(\mathcal{A}) > t_v holds if and only if JvB∉BJ_v^B \notin\mathcal{B}.

By Lemmas 10 and 11, we have that JuA∉AJ_u^A \notin\mathcal{A} and JvB∈BJ_v^B \in\mathcal{B} whenever rmin⁡(B)>tur_{\min}(\mathcal{B}) > t_u. In this case, the Gantt chart of schedule σ\sigma is illustrated in Figure 5. Combining (37) and (38), we obtain

Z(σ)=(1+θ)TM+P(A)+(1+θ)(P(B∪B′)+P(A′)).(66)Z(\sigma) = (1+\theta)T_M + P(\mathcal{A}) + (1+\theta)(P(\mathcal{B}\cup\mathcal{B}') + P(\mathcal{A}')). \tag*{(66)}

The following lemmas are established under this setting.

Lemma 12. If rmin⁡(B)>tur_{\min}(\mathcal{B}) > t_u, then Cmax⁡A(π)≥Cmax⁡B(π)C_{\max}^A(\pi) \ge C_{\max}^B(\pi).

Proof. We argue by contradiction. Suppose instead that Cmax⁡A(π)<Cmax⁡B(π)C_{\max}^A(\pi) < C_{\max}^B(\pi), which implies

Z(π)≥(1+θ)P(A∪A′)+θP(B∪B′).(67)Z(\pi) \ge(1+\theta)P(\mathcal{A}\cup\mathcal{A}')+\theta P(\mathcal{B}\cup\mathcal{B}'). \tag*{(67)}

By Lemmas 10 and 11, the condition rmin⁡(B)>tur_{\min}(\mathcal{B}) > t_u implies that JuA∉AJ_u^A \notin\mathcal{A}, JvB∈BJ_v^B \in\mathcal{B}, and rmin⁡(A)≤tvr_{\min}(\mathcal{A}) \le t_v.

We consider two cases based on the relationship between rmin⁡(A∪A′)r_{\min}(\mathcal{A}\cup\mathcal{A}') and rmin⁡(B∪B′)r_{\min}(\mathcal{B}\cup\mathcal{B}').

Case 1: rmin⁡(A∪A′)<rmin⁡(B∪B′)r_{\min}(\mathcal{A}\cup\mathcal{A}') < r_{\min}(\mathcal{B}\cup\mathcal{B}').

At time tvt_v, since JvBJ_v^B is given priority over AA-jobs by Algorithm AOSA, we have

P(B∪B′)≤θP(A∪A′)−(1+θ)TM.(68)P(\mathcal{B}\cup\mathcal{B}') \le\theta P(\mathcal{A}\cup\mathcal{A}')-(1+\theta)T_M. \tag*{(68)}

Combining (66)–(68), we obtain

Z(σ)−Z(π)≤θP(A′).Z(\sigma)-Z(\pi) \le\theta P(\mathcal{A}').

This, together with (67), contradicts (2).

Case 2: rmin⁡(A∪A′)≥rmin⁡(B∪B′)r_{\min}(\mathcal{A}\cup\mathcal{A}') \ge r_{\min}(\mathcal{B}\cup\mathcal{B}').

At time tvt_v, JvBJ_v^B has priority over AA-jobs under Algorithm AOSA. Thus, we have

P(B∪B′)≤θP(A∪A′)+(1+θ)TM.(69)P(\mathcal{B}\cup\mathcal{B}') \le\theta P(\mathcal{A}\cup\mathcal{A}')+(1+\theta)T_M. \tag*{(69)}

We claim that

Z(π)≥(1+θ)TM+(1+θ)P(A∪A′)+θP(B∪B′).(70)Z(\pi) \ge(1+\theta)T_M+(1+\theta)P(\mathcal{A}\cup\mathcal{A}')+\theta P(\mathcal{B}\cup\mathcal{B}'). \tag*{(70)}

Indeed, if a BB-job starts before TMT_M, by Observation 1, the BB-job has a processing time no less than (1+θ)TM(1+\theta)T_M and all AA-jobs start after that BB-job in π\pi, which implies that

Cmax⁡A(π)≥(1+θ)TM+P(A∪A′).C_{\max}^A(\pi) \ge(1+\theta)T_M+P(\mathcal{A}\cup\mathcal{A}').

This together with Cmax⁡B(π)≥P(A∪A′)+P(B∪B′)C_{\max}^{B}(\pi) \ge P(\mathcal{A}\cup\mathcal{A}')+P(\mathcal{B}\cup\mathcal{B}'), yields (70). Otherwise, no job starts before TMT_M, and (70) holds trivially.

Combining (66) and (70), we obtain that

Z(σ)−Z(π)≤P(B∪B′).Z(\sigma)-Z(\pi)\le P(\mathcal{B}\cup\mathcal{B}').

This, together with (69) and (70), yields a contradiction.

This completes the proof.

By Lemma 12, with respect to π\pi, whenever rmin⁡(B)>tur_{\min}(\mathcal{B})>t_u, we have

Cmax⁡A(π)≥P(B′∪B)+P(A′∪A),(71)C_{\max}^{A}(\pi)\ge P(\mathcal{B}'\cup\mathcal{B})+P(\mathcal{A}'\cup\mathcal{A}), \tag*{(71)}
Cmax⁡B(π)≥P(B′∪B),(72)C_{\max}^{B}(\pi)\ge P(\mathcal{B}'\cup\mathcal{B}), \tag*{(72)}
Cmax⁡B(π)≥tu+P(B).(73)C_{\max}^{B}(\pi)\ge t_u+P(\mathcal{B}). \tag*{(73)}

Combining these inequalities with (37) and (38), we obtain

Z(σ)−Z(π)≤TM+θpuA.(74)Z(\sigma)-Z(\pi)\le T_M+\theta p_u^{A}. \tag*{(74)}

Lemma 13. If rmin⁡(B)>tur_{\min}(\mathcal{B})>t_u, then JuAJ_u^{A} is largest job among those AA-jobs arriving at or before time tut_u.

Proof. When rmin⁡(B)>tur_{\min}(\mathcal{B})>t_u, the Gantt chart of σ\sigma is depicted in Figure 5. Suppose, for contradiction, that among the AA-jobs released no later than tut_u there exists an job other than JuAJ_u^{A} with processing time at least puAp_u^{A}. Denote the largest such AA-job by JlAJ_l^{A}. Then

Cmax⁡A(π)≥2puA.(75)C_{\max}^{A}(\pi)\ge2p_u^{A}. \tag*{(75)}

In σ\sigma, regardless of whether JlAJ_l^{A} is processed before or after tut_u, we have

tu≥θ1+θpuA.(76)t_u\ge\frac{\theta}{1+\theta}p_u^{A}. \tag*{(76)}

We consider three cases as follows:

Case 1: No job starts before TMT_M in π\pi. Since Cmax⁡A(π)≥Cmax⁡B(π)C_{\max}^{A}(\pi)\ge C_{\max}^{B}(\pi), we have

Cmax⁡A(π)≥TM+P(B′∪B)+P(A′∪A).(77)C_{\max}^{A}(\pi)\ge T_M+P(\mathcal{B}'\cup\mathcal{B})+P(\mathcal{A}'\cup\mathcal{A}). \tag*{(77)}

Combining (77) with (37), (38), and (73), we obtain

Z(σ)−Z(π)≤θpuA,Z(\sigma)-Z(\pi)\le\theta p_u^{A},

which, together with (73), (75), and (76), contradicts (2).

Case 2: One of JuAJ_u^{A} and JlAJ_l^{A} starts before TMT_M. By Observation 1, that AA-job has processing time at least (1+1θ)TM(1+\frac{1}{\theta})T_M. Hence

Cmax⁡A(π)≥1+θθTM+puA.C_{\max}^{A}(\pi)\ge\frac{1+\theta}{\theta}T_M+p_u^{A}.

Since all BB-jobs start after this AA-job in this case, we have Cmax⁡B(π)≥puAC_{\max}^{B}(\pi)\ge p_u^{A}. Combining these bounds, we obtain

Z(π)≥(1+θ)puA+1+θθTM.Z(\pi)\ge(1+\theta)p_u^{A}+\frac{1+\theta}{\theta}T_M.

Together with (74), this leads to a contradiction. Case 3: There exists a job other than JuAJ^A_u and JlAJ^A_l that starts before TMT_M in π\pi. By Observation 1, this job has a processing time at least (1+1θ)TM(1+\frac{1}{\theta})T_M. Consequently, both JuAJ^A_u and JlAJ^A_l start after that job. Hence

Cmax⁡A(π)≥1+θθTM+2puA,C^A_{\max}(\pi) \ge\frac{1+\theta}{\theta}T_M+2p^A_u,

which together with (73) and (76) implies that

Z(π)≥1+θθTM+(1+θ)puA.Z(\pi) \ge\frac{1+\theta}{\theta}T_M+(1+\theta)p^A_u.

Together with (74), this contradicts (2).

Therefore, JuAJ^A_u is largest job among those AA-jobs arriving at or before time tut_u.

Lemma 14. If rmin⁡(B)>tur_{\min}(B)>t_u, then JuAJ^A_u starts at or after tut_u in π\pi.

Proof. Suppose, for the sake of contradiction, that JuAJ^A_u starts before tut_u in π\pi. Since rmin⁡(B)>tur_{\min}(B)>t_u, all jobs in BB must start after JuAJ^A_u in π\pi. Consequently,

Cmax⁡B(π)≥puA+P(B′∪B).(78)C^B_{\max}(\pi) \ge p^A_u+P(B'\cup B). \tag*{(78)}

If JuAJ^A_u starts at or after TMT_M in π\pi, we further obtain that

Cmax⁡B(π)≥TM+puA+P(B),C^B_{\max}(\pi) \ge T_M+p^A_u+P(B),

which, together with Cmax⁡A(π)>Cmax⁡B(π)C^A_{\max}(\pi)>C^B_{\max}(\pi), implies that

Z(π)≥(1+θ)(TM+puA).Z(\pi) \ge(1+\theta)(T_M+p^A_u).

Together with (74), this contradicts (2). Therefore, JuAJ^A_u starts before TMT_M in π\pi, which implies that JuAJ^A_u is released before TMT_M. By Observation 1, we have

puA≥θ+1θTM.(79)p^A_u \ge\frac{\theta+1}{\theta}T_M. \tag*{(79)}

We consider two cases depending on whether A′‾\overline{A'} is empty.

Case 1: A′‾=∅\overline{A'}=\emptyset. In this case, P(A′)=puAP(A')=p^A_u. Combining this with (66), (71), and (78), we obtain

Z(σ)−Z(π)≤(1+θ)TM.Z(\sigma)-Z(\pi)\le(1+\theta)T_M.

Together with Cmax⁡A(π)≥puAC^A_{\max}(\pi)\ge p^A_u, (78), and (79), this contradicts (2).

Case 2: A′‾≠∅\overline{A'}\ne\emptyset. Let tt be the starting time of the last job from A′‾\overline{A'} in σ\sigma. By Lemma 13, JuAJ^A_u is the largest job among those AA-jobs released at or before tt. According to Procedure A, we distinguish two subcases:

Case 2.1: TM+P(A′‾)≤puAT_M+P(\overline{A'})\le p^A_u. At time tt, Procedure A schedules the last job of A′‾\overline{A'} prior to JuAJ^A_u. Hence,

TM+θ2(1+θ)2P(A′‾)≤θ1+θpuA.T_M+\frac{\theta^2}{(1+\theta)^2}P(\overline{A'})\le\frac{\theta}{1+\theta}p^A_u.

Combining this with (66), (71), (78) and P(A′)=P(A′‾)+puAP(A')=P(\overline{A'})+p^A_u, we obtain

Z(σ)−Z(π)≤θ1+θP(A′).Z(\sigma)-Z(\pi)\le\frac{\theta}{1+\theta}P(A').

Together with Z(π)≥P(A′)Z(\pi)\ge P(A'), this contradicts (2).

Case 2.2: TM+P(A′‾)>puAT_M + P(\overline{A'}) > p_u^A. The last job of A′‾\overline{A'} is scheduled prior to the largest AA-job JuAJ_u^A. By Procedure A, we have

P(A′‾)≥θ1+θpuA+(1θ−θ1+θ)TM.P(\overline{A'}) \ge\frac{\theta}{1+\theta}p_u^A+\left(\frac{1}{\theta}-\frac{\theta}{1+\theta}\right)T_M.

Combining this with Cmax⁡A(π)≥P(A′‾)+puAC_{\max}^A(\pi) \ge P(\overline{A'}) + p_u^A and Cmax⁡B(π)>tu≥TM+P(A′‾)C_{\max}^B(\pi) > t_u \ge T_M + P(\overline{A'}), we deduce that

Z(π)≥θTM+puA+(1+θ)P(A′‾)≥(1+θ)puA+1+θθTM.\begin{aligned} Z(\pi) \ge\theta T_M + p_u^A + (1+\theta)P(\overline{A'}) \\ &\ge(1+\theta)p_u^A+\frac{1+\theta}{\theta}T_M. \end{aligned}

This, together with (74), contradicts (2).

This completes the proof.

Lemma 15. If rmin⁡(B)>tur_{\min}(B) > t_u, then I\mathcal{I} is not a counterexample.

Proof. By Lemmas 10 and 11, the condition rmin⁡(B)>tur_{\min}(B) > t_u implies that JuA∉AJ_u^A \notin A and rmin⁡(A)≤tvr_{\min}(A) \le t_v. The corresponding Gantt chart of σ\sigma is shown in Figure 5.

If rmin⁡(A)>tur_{\min}(A) > t_u, then JuAJ_u^A is the only available job at time tut_u. By Algorithm AOLA, we have

tu≥θ1+θpuA.t_u \ge\frac{\theta}{1+\theta}p_u^A.

Moreover, by Lemma 14, the condition rmin⁡(B)>tur_{\min}(B) > t_u implies that JuAJ_u^A starts at or after tut_u in π\pi. Combining this with rmin⁡(A)>tur_{\min}(A) > t_u, rmin⁡(B)>tur_{\min}(B) > t_u, and Lemma 12, we obtain

Cmax⁡A(π)≥tu+puA+P(A∪B).C_{\max}^A(\pi) \ge t_u + p_u^A + P(A \cup B).

Combining these inequalities with (73) and (66), we get

Z(σ)−Z(π)≤θ1+θZ(π).Z(\sigma)-Z(\pi) \le\frac{\theta}{1+\theta}Z(\pi).

Therefore, I\mathcal{I} cannot be a counterexample.

In what follows, we assume rmin⁡(A)≤tur_{\min}(A) \le t_u. Note that at time tut_u only AA-jobs are available. We distinguish two cases according to Procedure A.

Case 1: TM+P(A′‾)+ps(tu)A≤puAT_M + P(\overline{A'}) + p_{s(t_u)}^A \le p_u^A. At time tut_u, JuAJ_u^A is scheduled by Procedure A. Thus,

TM+θ2(1+θ)2(P(A′‾)+ps(tu)A)>θ1+θpuA.T_M+\frac{\theta^2}{(1+\theta)^2}\left(P(\overline{A'})+p_{s(t_u)}^A\right)>\frac{\theta}{1+\theta}p_u^A.

Combining this with the condition of Case 1, we deduce that

TM>θ1+θ(P(A′‾)+ps(tu)A).(80)T_M>\frac{\theta}{1+\theta}\left(P(\overline{A'})+p_{s(t_u)}^A\right). \tag*{(80)}
(1+θ)TM+P(A′‾)+ps(tu)A>θpuA.(81)(1+\theta)T_M+P(\overline{A'})+p_{s(t_u)}^A>\theta p_u^A. \tag*{(81)}

From (80) and Observation 1, it follows that no jobs in A′‾∪{Js(tu)A}\overline{A'}\cup\{J_{s(t_u)}^A\} are released before TMT_M. Consequently, the job that can start before TMT_M in π\pi is not in A′‾∪{Js(tu)A}∪{JuA}\overline{A'}\cup\{J_{s(t_u)}^A\}\cup\{J_u^A\}. We further distinguish three subcases. Case 1.1: In schedule π\pi, there is one AA-job that begins before TMT_M. Then this AA-job does not belong to A‾′∪{Js(tu)A}∪{JuA}\overline{A}' \cup\{J^A_{s(t_u)}\} \cup\{J^A_u\} and all BB-jobs will start after this AA-job. According to Observation 1, that AA-job has a processing time of at least 1+θθTM\frac{1+\theta}{\theta}T_M. Therefore, we have

Cmax⁡A(π)≥1+θθTM+P(A‾′)+puA+ps(tu)A,(82)C^A_{\max}(\pi) \ge\frac{1+\theta}{\theta}T_M + P(\overline{A}') + p^A_u + p^A_{s(t_u)}, \tag*{(82)}
Cmax⁡B(π)≥1+θθTM.(83)C^B_{\max}(\pi) \ge\frac{1+\theta}{\theta}T_M. \tag*{(83)}

By combining these with (81), we obtain

Z(π)≥(1+θ)puA+1+θθTM,Z(\pi) \ge(1+\theta)p^A_u + \frac{1+\theta}{\theta}T_M,

which together with (74), implies that II is not a counterexample.

Case 1.2: In schedule π\pi, suppose there is one BB-job that begins before TMT_M. Then all AA-jobs will start after this BB-job. According to Observation 1, that BB-job has a processing time of at least (1+θ)TM(1+\theta)T_M. Consequently, we have

Cmax⁡B(π)≥(1+θ)TM,C^B_{\max}(\pi) \ge(1+\theta)T_M,
Cmax⁡A(π)≥(1+θ)TM+P(A‾′)+puA+ps(tu)A.C^A_{\max}(\pi) \ge(1+\theta)T_M + P(\overline{A}') + p^A_u + p^A_{s(t_u)}.

Combining these inequalities with (81), we obtain

Z(π)≥θ+1θTM+(1+θ)puA,Z(\pi) \ge\frac{\theta+1}{\theta}T_M + (1+\theta)p^A_u,

which, together with (74), implies that II is not a counterexample.

Case 1.3: No jobs start before TMT_M in π\pi. Then

Cmax⁡A(π)≥TM+P(B′∪B)+puA+P(A‾′)+P(A).(84)C^A_{\max}(\pi) \ge T_M + P(B' \cup B) + p^A_u + P(\overline{A}') + P(A). \tag*{(84)}

This, together with (66) and (73), yields

Z(σ)−Z(π)≤θpuA.(85)Z(\sigma) - Z(\pi) \le\theta p^A_u. \tag*{(85)}

Combining this with (81), (84), P(A)≥ps(tu)AP(A) \ge p^A_{s(t_u)} and Cmax⁡B(π)≥TMC^B_{\max}(\pi) \ge T_M, we conclude that II is not a counterexample.

Case 2: TM+P(A‾′)+ps(tu)A>puAT_M + P(\overline{A}') + p^A_{s(t_u)} > p^A_u. At time tut_u, Procedure A prioritizes the largest AA-job, JuAJ^A_u, over all other available AA-jobs, which results in the following inequality:

P(A‾′)+ps(tu)A<θ1+θpuA+(1θ−θ1+θ)TM.P(\overline{A}') + p^A_{s(t_u)} < \frac{\theta}{1+\theta}p^A_u + \left(\frac{1}{\theta} - \frac{\theta}{1+\theta}\right)T_M.

Substituting this bound into the initial condition, we obtain that

TM>θ2θ+1puA,(86)T_M > \frac{\theta}{2\theta+1}p^A_u, \tag*{(86)}
TM>θ1+θ(P(A‾′)+ps(tu)A).(87)T_M > \frac{\theta}{1+\theta}\left(P(\overline{A}') + p^A_{s(t_u)}\right). \tag*{(87)}

Based on Observation 1, the last inequality implies that no jobs in the set A‾′∪{Js(tu)A}\overline{A}' \cup\{J^A_{s(t_u)}\} are released before TMT_M. Consequently, the job that can start before TMT_M in π\pi is not in A‾′∪{Js(tu)A}∪{JuA}\overline{A}' \cup\{J^A_{s(t_u)}\} \cup\{J^A_u\}. We then consider three subcases. Case 2.1: In schedule π\pi, there is one AA-job that begins before TMT_M. As in Case 1.1, (82) and (83) hold. Combining these with the initial assumption of Case 2, (86), and the condition 1+θ≥θ21+\theta\ge\theta^2, we obtain

Z(π)≥(1+θ)puA+1+θθTMZ(\pi) \ge(1+\theta)p_u^A+\frac{1+\theta}{\theta}T_M

Together with (74), this shows that I\mathcal{I} is not a counterexample.

Case 2.2: In schedule π\pi, there is one BB-job that begins before TMT_M. Then all AA-jobs will start after this BB-job. According to Observation 1, that BB-job has a processing time of at least (1+θ)TM(1+\theta)T_M. Therefore, we have

Cmax⁡A(π)≥(1+θ)TM+P(A′‾)+puA+ps(tu)AC_{\max}^A(\pi) \ge(1+\theta)T_M+P(\overline{A'})+p_u^A+p_{s(t_u)}^A

which, combined with the initial condition of Case 2, (86) and the condition θ+1≥θ2\theta+1 \ge\theta^2, implies that

Cmax⁡A(π)≥(1+θ)puA(88)C_{\max}^A(\pi) \ge(1+\theta)p_u^A \tag*{(88)}

Combining this result with Cmax⁡B(π)≥(1+θ)TMC_{\max}^B(\pi) \ge(1+\theta)T_M and (74), we can conclude that I\mathcal{I} is not a counterexample.

Case 2.3: No jobs start before TMT_M in π\pi. Thus,

Cmax⁡A(π)≥TM+P(A′‾)+puA+ps(tu)AC_{\max}^A(\pi) \ge T_M+P(\overline{A'})+p_u^A+p_{s(t_u)}^A

which, combined with the initial condition of Case 2, yields that Cmax⁡A(π)≥2puAC_{\max}^A(\pi) \ge2p_u^A. Together with Cmax⁡B(π)≥TMC_{\max}^B(\pi) \ge T_M, (86), and the condition θ+1≥θ2\theta+1 \ge\theta^2, this implies that

Z(π)≥(1+θ)puA.Z(\pi) \ge(1+\theta)p_u^A.

Following a similar argument to Case 1.3, it can be shown that (85) holds. Therefore, I\mathcal{I} is not a counterexample in this subcase.

This completes the proof.

Analogously to Lemma 15, we can show that I\mathcal{I} is not a counterexample when rmin⁡(A)>tvr_{\min}(A)>t_v. However, by Lemmas 10 and 11, the conditions rmin⁡(B)>tur_{\min}(B)>t_u and rmin⁡(A)>tvr_{\min}(A)>t_v cannot occur simultaneously. Therefore, no counterexample exists. We thus obtain the following theorem.

Theorem 1. Algorithm has a competitive ratio of 1+θ1+θ1+\frac{\theta}{1+\theta} when 1≤θ≤5+121\le\theta\le\frac{\sqrt{5}+1}{2}.

Conclusions

This paper studied a two-agent single-machine scheduling problem 1∣rj, online∣Cmax⁡A+θCmax⁡B1\mid r_j,\text{ online}\mid C_{\max}^A+\theta C_{\max}^B, where 1≤θ≤1+521\le\theta\le\frac{1+\sqrt{5}}{2}. For this problem, we proposed Algorithm ALOA, which achieves the best possible competitive ratio of 1+θ1+θ1+\frac{\theta}{1+\theta}. This improves upon the result of Zhao et al., who presented an online algorithm with a competitive ratio of 1+2θ+θ21+2θ+θ2\frac{1+2\theta+\theta^2}{1+2\theta+\theta^2}.

When θ>1+52\theta>\frac{1+\sqrt{5}}{2}, it becomes more advantageous to process BB-jobs before AA-jobs. However, it is difficult to make scheduling decisions when only AA-jobs are available and t<θ1+θpl(t)At<\frac{\theta}{1+\theta}p_{l(t)}^A. From the analysis of Algorithm ALOA, we find that only in Case 2 of Lemma 15, ensuring the competitive ratio of 1+θ1+θ1+\frac{\theta}{1+\theta} requires that 1+θ≥θ21+\theta\ge\theta^2, that is, θ≤1+52\theta\le\frac{1+\sqrt{5}}{2}. At a time tt with t<θ1+θpl(t)At<\frac{\theta}{1+\theta}p_{l(t)}^A, regardless of whether the algorithm schedules Jl(t)J_{l(t)} or Js(t)J_{s(t)}, the competitive ratio—the objective function value of the algorithm’s solution relative to the optimal one—may exceed 1+θ1+θ1+\frac{\theta}{1+\theta}. To guarantee this bound, it is necessary to introduce an appropriate waiting strategy when scheduling jobs in A′A'. Designing such a strategy remains a key challenge. In particular, when θ>1+52\theta> \frac{1+\sqrt{5}}{2}, the current algorithm alone cannot ensure the performance ratio 1+θ1+θ1+\frac{\theta}{1+\theta}.

An immediate direction for future research is to develop an online algorithm that can achieve a competitive ratio of 1+θ1+θ1+\frac{\theta}{1+\theta} for the case where θ>1+52\theta> \frac{1+\sqrt{5}}{2}. This would require a sophisticated waiting strategy or alternative scheduling approach. It would also be valuable to explore how these results extend to multi-machine environments or other objective functions.

Acknowledgements

This research is supported by National Natural Science of China (12371317, 12571338).

References

  1. [1]Agnetis A, Billaut JC, Gawiejnowicz S, Pacciarelli D, Soukhal A. Multiagent scheduling: Models and algorithms. Springer, 2014.DOI
  2. [2]Agnetis A, Mirchandani PB, Pacciarelli D, Pacifici A. Scheduling problems with two competing agents. Oper. Res. 52(2), 229–242 (2004)DOI
  3. [3]Baker KR, Smith JC. A multiple-criterion model for machine scheduling. J. Sched. 6(1), 7–16 (2003)DOI
  4. [4]Ding G, Sun S. Single-machine scheduling problems with two agents competing for makespan. In: Lecture Notes in Computer Science, vol. 6328, pp. 244–255. Springer, 2010.DOI
  5. [5]Geng Z, Lu L. Two-agent scheduling of minimizing total weighted late work and maximum cost. J. Ind. Manag. Optim. 21(5), 3648–3667 (2025)DOI
  6. [6]Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. 4, 287–326 (1979)DOI
  7. [8]Lu XW, Zhao KJ, Gu MZ. Online single-machine scheduling to minimize the linear combination of makespans of two agents. Inf. Process. Lett. 173, 106173 (2022)DOI
  8. [9]Phosavanh J, Oron D. Two-agent single-machine scheduling with a rate-modifying activity. Eur. J. Oper. Res. 312(3), 866–876 (2024)DOI
  9. [10]Phosavanh J, Oron D. Single-machine two-agent scheduling with a rate-modifying activity and weighted due-date-related functions. J. Sched. (2025). https://doi.org/10.1007/s10951-025-00853-0
  10. [11]Shiau YR, Tsai MS, Lee WC, Cheng TCE. Two-agent two-machine flowshop scheduling with learning effects to minimize the total completion time. Comput. Ind. Eng. 87, 580–589 (2015)DOI
  11. [13]Ying KC, Pourhejazy P, Sung CE. Two-agent proportionate flowshop scheduling with deadlines: Polynomial-time optimization algorithms. Ann. Oper. Res. 343, 543–558 (2024)DOI
  12. [14]Yuan JJ, Ng CT, Cheng TCE. Scheduling with release dates and preemption to minimize multiple max-form objective functions. Eur. J. Oper. Res. 280(3), 860–875 (2020)DOI

Paper details

vlnc:W_wjvxr94x
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents