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 , for a given priority weight . 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 , we propose novel online algorithm which achieves a competitive ratio of . 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 but proposed an algorithm achieving only a ratio of , 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 ; 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 , focusing on the challenging parameter range . 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 , 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 . 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 and denote the sets of jobs belonging to Agent A and Agent B, respectively. For simplicity, jobs in and are referred to as A-jobs and B-jobs. These two job sets are disjoint, i.e., . Each job (for ) is characterized by a processing time and a release date . All jobs are to be processed non-preemptively on a single machine.
Each agent seeks to minimize its makespan, defined as , where is the completion time of job . The overall objective is to find a schedule that minimizes a weighted sum of the two agents’ makespans. The objective function is formulated as: , where 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 are unknown until its release date . At any time , 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 .
Definitions and Notations
We begin by introducing the key notations used throughout the analysis. A decision point is defined as any time at which the machine is idle and at least one job is available. A job is available at time if it has been released () but not yet processed.
For clarity, notations are often presented for Agent A only; analogous definitions apply to Agent B.
: The set of available jobs for agent at time .
: The set of all available jobs at time , i.e., .
and : The available A-jobs in with the shortest and longest processing times, respectively. Ties are broken arbitrarily.
: The start time of the last contiguous block of jobs that was completed at time . If the machine has been continuously busy since time 0, then .
: The set of A-jobs that were processed within the time interval .
: The total processing time of jobs in job set , i.e., .
: The minimum release date among jobs in job set , i.e., .
Figure 1 provides a graphical illustration of these notations.
Figure 1. An example of the notations defined at time .
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 .
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 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 and the start time of the current block. This mechanism ensures that machine time is allocated efficiently while respecting the relative priority encoded by .
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 .
Algorithm AOSA (Agent-Based Online Scheduling Algorithm)
Require: Priority weight ; sequence of jobs arriving over time Ensure: Feasible schedule minimizing
while there are unscheduled jobs do
Determine (set of available unscheduled jobs at time )
if then
if then
Run Procedure A
else
Wait until or a new job arrives
end if
else if then
if then
Run Procedure B
else
Wait until or a new job arrives
end if
else if and then
if then
if then
Run Procedure A
else
Run Procedure B
end if
else
if then
Run Procedure A
else
Run Procedure B
end if
end if
end if
end while
Procedure A
if then
if then
Schedule
else
Schedule
end if
else
if then
Schedule
else
Schedule
end if
end if
Procedure B
1: if then 2: if then 3: Schedule 4: else 5: Schedule 6: end if 7: else 8: if then 9: Schedule 10: else 11: Schedule 12: end if 13: end if
Competitive Analysis
In this section, we analyze the performance guarantee of Algorithm AOSA under the condition , which is equivalent to
For the competitive analysis, let denote the schedule generated by the online algorithm, with objective value . We compare with the value of an optimal offline schedule, denoted by , which has objective value .
Our analysis focuses on the structural properties of . The schedule 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 , denoted by .
(resp. ): the final contiguous sequence of A-jobs (resp. B-jobs) in . Note that may lie outside and thus form a pure block.
(resp. ): the set of A-jobs (resp. B-jobs) in that are scheduled before all jobs in . Either or may be empty.
(resp. ): the A-job (resp. B-job) in scheduled immediately before (resp. ).
if and if .
Figure 2 illustrates the structure of the last mixed block and the associated notations. We will now prove that the competitive ratio of Algorithm AOSA is . 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 be a minimal counterexample instance—that is, an instance with the minimum number of jobs that violates the bound. Let be the schedule produced by AOSA and be an optimal schedule for instance . Thus, we have:
Figure 2. An example of notations defined for .
In the remainder of this section, we analyze the smallest counterexample by deriving a collection of structural properties of the schedule . We then employ these properties to show that cannot constitute a valid counterexample. We begin by presenting a series of fundamental observations about .
Observation 1. Let be the start time of a block in the schedule produced by Algorithm AOSA. Then the following properties hold:
(i) All jobs arriving before in the block belong to the same agent.
(ii) For each A-job with release time , we have
(iii) For each B-job with release time , we have
Observation 2. If the final contiguous A-job block in the schedule begins immediately after an idle interval, then
Observation 3. If the final contiguous B-job block in the schedule begins immediately after an idle interval, then
Lemma 1. Both and belong to the mixed block in the schedule .
Proof. We prove the lemma by contradiction. Assume, without loss of generality, that does not belong to . This implies that 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 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, must be preceded by an A-job, denoted by . Note that and . This structural arrangement is illustrated in the Gantt chart in Figure 3.
Figure 3. is a pure lock in .
From this schedule structure, we can establish the following makespans in :
Furthermore, any feasible schedule, including the optimal offline schedule , must process these jobs. Thus, we have the trivial lower bounds:
We now analyze the schedule structure by considering two cases based on the minimal release time of jobs in .
Case 1. .
At decision time (the start of job ) there are available jobs from both agents. We distinguish two subcases according to the ordering of and .
.
By Observation 1 every -job in arrives no earlier than , hence
Since Algorithm AOSA chooses an A-job to be processed at the decision point , we obtain
Combining (9) and (10), regardless of whether holds or not, we deduce that
Together with (7), this yields
If , then by Observation 1 we have . Together with (5), (6), (7), and (9), this implies
In view of (12), this contradicts (2).
If , then
Combining this with (5), (6), and (9), we obtain
Moreover, since , it follows from (9), (10), and (13) that
Together with (14), this again contradicts (2).
.
In this case, by Observation 1, all -jobs in must have release times no earlier than . This implies
Moreover, since Algorithm AOSA schedules job at time , we further obtain
Together with (5), (6), (8), (15), this yields
If , then by Observation 1 we have . Combining this with (17), we obtain that
In view of (7) and (8), this contradicts (2).
If , then by combining (5), (6), (8), and (13), we obtain
Moreover, since , it follows from (16) that . Together with (18), this again contradicts (2).
Case 2. . In this case, all jobs in arrive strictly after , and thus . Consequently,
We further show that
Indeed, implies that . If inequality (20) were violated, then by Algorithm AOSA (which schedules at ), there would be at least one other available -job at that time, with being the largest. In that case, all available -jobs other than belong to , and and the remaining available -jobs would be scheduled within the same block, contradicting the assumption that is a pure block.
Again, we consider two subcases based on the value of .
, then by Observation 1 we have . Combining this with (5), (6), (7), and (19), we deduce
The last inequality follows from and .
Furthermore, noting that and , and combining (19) with (20), we obtain
Together with (21), this leads to a contradiction with (2).
. Combining (5), (6), (13), and (19), we obtain
Furthermore, noting that , and combining (13), (19), and (20), we deduce
These inequalities again contradict (2).
Therefore, must be contained in the block . By a similar argument, also belongs to the mixed block in .
This completes the proof of the lemma.
By Lemma 1, both and must belong to the same mixed block . Hence, the jobs in are processed consecutively in . It follows that at least one of and exists. In fact, we shall prove in the subsequent lemmas that if is a counterexample, then both and must exist.
Suppose next that is scheduled immediately after an idle interval in . In this case, necessarily exists. The corresponding Gantt chart is illustrated in Figure 4. With respect to , we then obtain
Figure 4. is scheduled immediately after an idle interval in .
Lemma 2. If starts immediately after an idle interval in , then must hold.
Proof. Suppose, for the sake of contradiction, that in starts immediately after an idle interval and . We will derive a contradiction to (2).
To derive lower bounds for the optimal schedule , let denote the earliest start time, under , of any job in . Then we obtain
We distinguish two cases, depending on whether or not.
. Substituting the condition into the lower bounds from (24) and (25) and comparing them with the makespans in (from (22) and (23)), we can obtain that . This directly contradicts (2).
. This condition implies that at least one job in is released and starts before time .
If the job starting before belongs to , then, by Observation 1,
Combining this with (22), (23), (24), and (25) yields
Together with (24) and (25), this contradicts (2).
If the job starting before belongs to , by Observation 1, its processing time is at least . In , all -jobs start after this -job. Thus,
Combining this with (22), (23), and (24) yields , contradicting (2).
This completes the proof.
Lemma 2 shows that . Consequently, we obtain the following lower bounds on the optimal schedule :
where denotes the earliest starting time of the jobs in under .
Lemma 3. If is scheduled immediately after an idle interval in , then it holds that .
Proof. We argue by contradiction. Assume, for the sake of contradiction, that . We distinguish two cases depending on whether holds.
Case 1: .
At time , both some -jobs and job are available. Since Algorithm AOSA gives priority to -jobs, we obtain
By combining this inequality with (26) and (27), we obtain
This bound, together with (22) and (23), contradicts (2).
Case 2: .
Again, at time , both -jobs and are available, and Algorithm AOSA prioritizes -jobs. Hence,
We claim that
If , then (29) follows directly from (22) and (23). Otherwise, there must exist a -job starting before in . By Observation 1, that job has processing time at least . Since all -jobs start after this -job in , we have
Combining this bound with (27) yields (29).
Finally, using (22), (23), and (29), we obtain
Together with (28) and (29), this contradicts (2). This completes the proof.
Now we are ready to establish the existence of both and .
Lemma 4. In schedule , 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 . Then A must follow B consecutively in . In this case, the corresponding Gantt chart of the schedule is illustrated in Figure 4.
From Lemmas 2,3, we have and . Since , it follows that
Combining this with (22), (23), and (27), we obtain
Since is the last B-job and no A-jobs are available at time , it follows directly from Observation 1 that
We now distinguish two cases according to the value of .
Case 1: . Combining this with (22), (23), and (30), we deduce that
Moreover, together with , (30), and (32), this leads to a contradiction with (2).
Case 2: . In this case, job must start before in . We claim that
Otherwise, if , then together with and (31), we obtain a contradiction with (2).
Since starts before and , i.e., all jobs in are scheduled after and in , we have
Note that , , and . Combining these with (22), (23), and (34), we deduce that
Moreover, we note the following two properties of :
starts before in . This holds because starts before the jobs in (as ), and by (33) its completion time cannot exceed .
(ii) is the largest -job in . This follows since (33) and (34), together with , imply that dominates the processing times of all other -jobs.
Since no -jobs are available while the jobs in are being scheduled, and Procedure B does not assign priority to the largest -job , we distinguish two subcases.
Case 2.1: . By Procedure B, when the job immediately preceding is scheduled, it must hold that
Combining this with (34) and the fact that , we obtain
Together with and (35), this contradicts (2).
Case 2.2: . By Procedure B, when the job before is scheduled, we have
Combined this with (34) and , , we have
which along with (35), leads a contradiction with (2).
By symmetry, the second statement follows upon swapping and . This completes the proof.
By Lemma 4, the jobs and , which are processed immediately before and in , always exist. If , then ; the corresponding Gantt chart of is shown in Figure 5. In this case, the following equalities hold for the two agents’ makespans in :
Figure 5. The Gantt chart of schedule in which .
In what follows, we derive further conclusions under the assumption that is a counterexample.
Lemma 5. If and , then .
Proof. Assume, for contradiction, that while and in . We will derive a contradiction to (2).
From , we obtain
Combining this with (37) and (38) yields
We next distinguish two cases according to the relative order between and . Case 1: .
In this case, since is scheduled at time , the algorithm implies that
Together with (39) and (40), this contradicts (2).
Case 2: .
In this case, since is scheduled at time , the algorithm guarantees
We now claim that
Indeed, if no jobs start before in , then (42) holds immediately. Otherwise, there is a job starting before in . By Observation 1 and the initial condition of this case, the job must be an -job with processing time no less than . Since all -jobs would be scheduled after this -job, it follows that
This, together with the fact that , implies that (42) holds. Finally, combining (42) with (37) and (38) yields
Together with (41) and (42), this contradicts (2).
In both cases we reach a contradiction. Hence , as claimed. This completes the proof.
Lemma 5 implies that the following lower bounds always hold for :
Lemma 6. If and , then .
Proof. Suppose, for contradiction, that . By Observation 1, at most one agent has a job that starts before in . We distinguish two cases according to whether a job in starts before in .
Case 1: There exists an -job that starts before in . By Observation 1, it follows that . Since at time job is scheduled first, by the rule of Algorithm AOSA we obtain
Combining (45) with (37), (38), (43) and (44), we get
This, together with (43) and (44), contradicts (2).
Case 2: All -jobs start at or after in . We claim that
Indeed, if all -jobs also start at or after in , then (46) follows immediately from (37) and (38). Otherwise, there exists a -job that starts before in . By Observation 1, the processing time of this -job is at least . Since all -jobs start after this -job in , we obtain
which, together with (44) implies that (46) holds.
Combining (46) with (37) and (38), we obtain
Note that at time , job is scheduled prior to the available jobs in . According to the scheduling rule of Algorithm AOSA, this implies that
Combining this with (46), we obtain that . This, combined with (47), contradicts (2).
Hence the assumption is false and . This completes the proof.
Lemma 7. If , then .
Proof. We argue by contradiction. Suppose, to the contrary, that while . The condition implies that, in , all jobs in are processed after . In this case, the Gantt chart of is shown in Figure 5.
By Lemmas 5 and 6, we have and . By the fact that and , we obtain
Combining this with (37), (38), and (44), we deduce that
Note that at time , the only available job is . By Observation 1, we have
In what follows, we distinguish three cases according to the start time of in .
Case 1: starts at or after in .
In this case, . Combining this with (37), (48), we obtain
Moreover, it follows from and , together with (50), that
Together with (51), this contradicts (2).
Case 2: starts in between and .
Since , we obtain
Combining this with the inequality , it follows that
This, together with (49), contradict (2).
Case 3: starts before in .
This implies that and all -jobs start after in . Therefore,
By Observation 1, implies that
Define . Then
which, together with (53), implies
Moreover, combining (37), (38), (44), and (53), we obtain
If , then combining (49), (54), and (55), yields a contradiction to (2).
If , then is the largest -job. Since no -job is available when the -job immediately preceding is scheduled, Procedure B ensures
Combining this with (56), we derive
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 , if , then .
Lemma 9. If , then .
Proof. We argue by contradiction. Suppose that and . Under this assumption, ; hence all jobs in appear at the tail of the schedule . In this case, the Gantt chart of is shown in Figure 6. Thus,
Figure 6. The Scenario with and in .
By Lemma 8, the condition implies . Together with , we obtain
Combining (58), (59), and (60) with the identity , we deduce
We now distinguish two cases based on the relative order of and .
Case 1: .
If starts after all -jobs in , then, since , we have
Recalling that and combining (62) with (58) and (60), we obtain
At time , is the only available job. By Observation 1,
which, together with (60), (62), and (63), yields a contradiction to (2).
If, instead, is scheduled before some -jobs in , then
Combining this with and (61), we again obtain a contradiction to (2).
Case 2: .
If starts at or after in , then, since , we have
This together with (58) and (59), implies that
At time , is the only available job. Hence, by Observation 1,
which, together with (59), (64), and (65), contradicts (2).
If instead starts before in , then since , we obtain
Combining this with 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. holds if and only if .
Lemma 11. holds if and only if .
By Lemmas 10 and 11, we have that and whenever . In this case, the Gantt chart of schedule is illustrated in Figure 5. Combining (37) and (38), we obtain
The following lemmas are established under this setting.
Lemma 12. If , then .
Proof. We argue by contradiction. Suppose instead that , which implies
By Lemmas 10 and 11, the condition implies that , , and .
We consider two cases based on the relationship between and .
Case 1: .
At time , since is given priority over -jobs by Algorithm AOSA, we have
Combining (66)–(68), we obtain
This, together with (67), contradicts (2).
Case 2: .
At time , has priority over -jobs under Algorithm AOSA. Thus, we have
We claim that
Indeed, if a -job starts before , by Observation 1, the -job has a processing time no less than and all -jobs start after that -job in , which implies that
This together with , yields (70). Otherwise, no job starts before , and (70) holds trivially.
Combining (66) and (70), we obtain that
This, together with (69) and (70), yields a contradiction.
This completes the proof.
By Lemma 12, with respect to , whenever , we have
Combining these inequalities with (37) and (38), we obtain
Lemma 13. If , then is largest job among those -jobs arriving at or before time .
Proof. When , the Gantt chart of is depicted in Figure 5. Suppose, for contradiction, that among the -jobs released no later than there exists an job other than with processing time at least . Denote the largest such -job by . Then
In , regardless of whether is processed before or after , we have
We consider three cases as follows:
Case 1: No job starts before in . Since , we have
Combining (77) with (37), (38), and (73), we obtain
which, together with (73), (75), and (76), contradicts (2).
Case 2: One of and starts before . By Observation 1, that -job has processing time at least . Hence
Since all -jobs start after this -job in this case, we have . Combining these bounds, we obtain
Together with (74), this leads to a contradiction. Case 3: There exists a job other than and that starts before in . By Observation 1, this job has a processing time at least . Consequently, both and start after that job. Hence
which together with (73) and (76) implies that
Together with (74), this contradicts (2).
Therefore, is largest job among those -jobs arriving at or before time .
Lemma 14. If , then starts at or after in .
Proof. Suppose, for the sake of contradiction, that starts before in . Since , all jobs in must start after in . Consequently,
If starts at or after in , we further obtain that
which, together with , implies that
Together with (74), this contradicts (2). Therefore, starts before in , which implies that is released before . By Observation 1, we have
We consider two cases depending on whether is empty.
Case 1: . In this case, . Combining this with (66), (71), and (78), we obtain
Together with , (78), and (79), this contradicts (2).
Case 2: . Let be the starting time of the last job from in . By Lemma 13, is the largest job among those -jobs released at or before . According to Procedure A, we distinguish two subcases:
Case 2.1: . At time , Procedure A schedules the last job of prior to . Hence,
Combining this with (66), (71), (78) and , we obtain
Together with , this contradicts (2).
Case 2.2: . The last job of is scheduled prior to the largest -job . By Procedure A, we have
Combining this with and , we deduce that
This, together with (74), contradicts (2).
This completes the proof.
Lemma 15. If , then is not a counterexample.
Proof. By Lemmas 10 and 11, the condition implies that and . The corresponding Gantt chart of is shown in Figure 5.
If , then is the only available job at time . By Algorithm AOLA, we have
Moreover, by Lemma 14, the condition implies that starts at or after in . Combining this with , , and Lemma 12, we obtain
Combining these inequalities with (73) and (66), we get
Therefore, cannot be a counterexample.
In what follows, we assume . Note that at time only -jobs are available. We distinguish two cases according to Procedure A.
Case 1: . At time , is scheduled by Procedure A. Thus,
Combining this with the condition of Case 1, we deduce that
From (80) and Observation 1, it follows that no jobs in are released before . Consequently, the job that can start before in is not in . We further distinguish three subcases. Case 1.1: In schedule , there is one -job that begins before . Then this -job does not belong to and all -jobs will start after this -job. According to Observation 1, that -job has a processing time of at least . Therefore, we have
By combining these with (81), we obtain
which together with (74), implies that is not a counterexample.
Case 1.2: In schedule , suppose there is one -job that begins before . Then all -jobs will start after this -job. According to Observation 1, that -job has a processing time of at least . Consequently, we have
Combining these inequalities with (81), we obtain
which, together with (74), implies that is not a counterexample.
Case 1.3: No jobs start before in . Then
This, together with (66) and (73), yields
Combining this with (81), (84), and , we conclude that is not a counterexample.
Case 2: . At time , Procedure A prioritizes the largest -job, , over all other available -jobs, which results in the following inequality:
Substituting this bound into the initial condition, we obtain that
Based on Observation 1, the last inequality implies that no jobs in the set are released before . Consequently, the job that can start before in is not in . We then consider three subcases. Case 2.1: In schedule , there is one -job that begins before . As in Case 1.1, (82) and (83) hold. Combining these with the initial assumption of Case 2, (86), and the condition , we obtain
Together with (74), this shows that is not a counterexample.
Case 2.2: In schedule , there is one -job that begins before . Then all -jobs will start after this -job. According to Observation 1, that -job has a processing time of at least . Therefore, we have
which, combined with the initial condition of Case 2, (86) and the condition , implies that
Combining this result with and (74), we can conclude that is not a counterexample.
Case 2.3: No jobs start before in . Thus,
which, combined with the initial condition of Case 2, yields that . Together with , (86), and the condition , this implies that
Following a similar argument to Case 1.3, it can be shown that (85) holds. Therefore, is not a counterexample in this subcase.
This completes the proof.
Analogously to Lemma 15, we can show that is not a counterexample when . However, by Lemmas 10 and 11, the conditions and cannot occur simultaneously. Therefore, no counterexample exists. We thus obtain the following theorem.
Theorem 1. Algorithm has a competitive ratio of when .
Conclusions
This paper studied a two-agent single-machine scheduling problem , where . For this problem, we proposed Algorithm ALOA, which achieves the best possible competitive ratio of . This improves upon the result of Zhao et al., who presented an online algorithm with a competitive ratio of .
When , it becomes more advantageous to process -jobs before -jobs. However, it is difficult to make scheduling decisions when only -jobs are available and . From the analysis of Algorithm ALOA, we find that only in Case 2 of Lemma 15, ensuring the competitive ratio of requires that , that is, . At a time with , regardless of whether the algorithm schedules or , the competitive ratio—the objective function value of the algorithm’s solution relative to the optimal one—may exceed . To guarantee this bound, it is necessary to introduce an appropriate waiting strategy when scheduling jobs in . Designing such a strategy remains a key challenge. In particular, when , the current algorithm alone cannot ensure the performance ratio .
An immediate direction for future research is to develop an online algorithm that can achieve a competitive ratio of for the case where . 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]Agnetis A, Billaut JC, Gawiejnowicz S, Pacciarelli D, Soukhal A. Multiagent scheduling: Models and algorithms. Springer, 2014.DOI
- [2]Agnetis A, Mirchandani PB, Pacciarelli D, Pacifici A. Scheduling problems with two competing agents. Oper. Res. 52(2), 229–242 (2004)DOI
- [3]Baker KR, Smith JC. A multiple-criterion model for machine scheduling. J. Sched. 6(1), 7–16 (2003)DOI
- [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]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]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
- [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
- [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
- [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
- [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
- [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
- [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





