# Two-Agent Single-Machine Scheduling with Resource-Dependent Starting Times

Authors: Peng Liu; Xiaoyu Tian
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We consider several two-agent scheduling problems with resource consumption on a single machine, where each of the agents wants to minimize a measure dependent on its own jobs. The starting time of each job of the first agent is related to the amount of resource consumed. The objective is to minimize the total amount of resource consumption of the first agent with the restriction that the makespan or the total completion time of the second agent cannot exceed a given boundU. The optimal properties and the optimal polynomial time algorithms are proposed to solve the scheduling problems.


---

## Body

## 1. Introduction

Recently, there has been a growing interest in the literature to study multiagent scheduling problems, in which different agents share a common processing machine, and each agent wants to minimize a cost function dependent on its own job.  Scheduling with multiple agents is firstly introduced by Baker and Smith [1] and Agnetis et al. [2].  Baker and Smith [1] manage to find a schedule that minimizes a combination of multiple agents’ objective functions.  Agnetis et al. [2] study several scheduling problems with two agents that have requirements of their own objective functions.  Some researchers pay their attention to the different machine environments and job characteristics of the scheduling problems with multiagent.  Yuan et al. [3] show that two dynamic programming recursions in Baker and Smith [1] are incorrect and give a polynomial time algorithm for the same problems.  Cheng et al. [4] extend one of the problems of Agnetis et al. [2] to the multiagent scheduling problem with minimizing the total weighted number of tardy jobs on a single machine.  They show that the problem is strongly NP-complete in general, and they study a special case in which the number of agents is fixed.  Cheng et al. [5] consider the multiagent scheduling problem on a single machine, where the agent’s objective functions are of the max form.  They study the feasibility model and the minimality model.  Leung et al. [6] study a two-agent scheduling environment with m identical parallel machines and generalize the results of Baker and Smith [1] and Agnetis et al. [2] by including the total tardiness objective, allowing for preemptions, and considering jobs with different release dates.  Gawiejnowicz et al. [7] consider a single-machine two-agent scheduling problem with proportionally deteriorating job processing times.  Yin et al. [8] consider several two-agent scheduling problems with assignable due dates on a single machine.  Gerstl and Mosheiov [9] consider the scheduling problems with two competing agents to minimize the weighted earliness-tardiness. Cheng et al. [10] study a two-agent single-machine scheduling problem with release times to minimize the total weighted completion time.  Zhao and Lu [11] consider two models of two-agent scheduling problems on identical machines.  Yin et al. [12] provide a branch-and-bound procedure for a single-machine earliness scheduling problem with two agents.  Yu et al. [13] investigate several single-machine two-synergetic-agent scheduling problems.  For other recent scheduling problems with two agents, the reader is referred to Lee et al. [14], Wu et al. [15], Feng et al. [16], and Wu et al. [17].On the other hand, the scheduling problems with resource consumption have received a considerable attention in the last two decades.  The classical scheduling problems have traditionally been considered under the assumptions that job processing times and release times are constant parameters and that the resource allocation issue is ignored. Cheng and Janiak [18] study the resource optimal control of job completion on a single machine with a constraint on maximum job completion time. Li [19] considers the problem of scheduling a set of jobs on a single machine where the release time of a job is related to the amount of resources consumed. Vasilev and Foote [20] investigate a single-machine scheduling problem where the resources consumed depend on the release times of jobs.  Kaspi and Shabtay [21] consider the problem of scheduling jobs on a single machine where job processing times are controllable through the allocation of a common limited resource.  Wang and Cheng [22] consider the single-machine scheduling problem with resource-dependent release times and processing times.  Shabtay and Kaspi [23] study the parallel machine scheduling problems with a convex resource consumption function. Yedidsion et al. [24] provide an optimization algorithm for the single-machine problem where the processing time of each job is resource-dependent. Wang et al. [25] study the single-machine scheduling problem with learning effect and resource-dependent processing times. Wei et al. [26] consider the single-machine scheduling with time and resource-dependent processing times. J. B. Wang and M. Z. Wang [27] consider the single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time. Wang et al. [28] consider the scheduling problem with processing times dependent on position, starting time, and allotted resources. Wang et al. [29] consider single-machine scheduling problems with deteriorating jobs and resource allocation in a group technology environment. Hsu and Yang [30] analyze unrelated parallel machine scheduling resource allocation problems with position-dependent deteriorating jobs.However, to the best of our knowledge, the multiagent scheduling problem with the consideration of resource-dependent starting times has hardly been studied in the literature.  These two categories of scheduling problems have been extensively and separately researched over the last two decades.  In this paper, we study the two-agent scheduling problems on a single machine with resource-dependent starting times, where the goal is to find a schedule that minimizes the objective function of one agent with the restriction that the objective function of the other agent cannot exceed a given bound.  The problems under consideration fall into the category of scheduling problems with resource consumption and multiple agents.The remainder of this paper is organized as follows.  In Section2, we describe the proposed problems.  In Sections 3 and 4, we develop the optimal polynomial time algorithms for the two-agent single-machine scheduling problems.  Section 5 gives some concluding remarks.


## 2. Problem Description

We now describe our problems formally.  There are two families of independent and nonpreemptive jobsJA={J1A,J2A,…,JnAA} and JB={J1B,J2B,…,JnBB} to be processed on a common single machine.  All jobs are available for processing at time zero.  The jobs in JA and JB are called A-agent’s jobs and B-agent’s jobs, respectively.  Associated with each job JhA, let phA denote the processing time, h=1,2,…,nA.  The starting time shA is related to the amount of the resource fhA, consumed on job JhA.  We assume that fhA=f(shA), where f:R+→R+, called the resource consumption function, is a strictly increasing continuous function to A-agent’s jobs.  Associated with each job JkB, let pkB denote the processing time, k=1,2,…,nB.  Let π indicate a feasible schedule of the n=nA+nB jobs.  Let CkB(π) denote the completion time of B-agent’s job JkB under schedule π.  The objective function of agent A is to minimize the total amount of resource consumption ∑h=1nAf(shA).  The objective function of agent B is to minimize the makespan CmaxB=maxk=1,2,…,nB{CkB(π)} or the total completion time ∑k=1nBCkB(π).The goal is to minimize the total amount of resource consumption∑h=1nAf(shA) of agent A with the restriction that the makespan CmaxB or the total completion time ∑k=1nBCkB of agent B cannot exceed a given bound U.  If the value U is too small, an instance of the scheduling problem may not have feasible solutions.  If there is at least one feasible solution, we say that the instance is feasible.  According to the three-field notation ψ1|ψ2|ψ3 of Graham et al. [31], the two scheduling problems are denoted as 1∥∑h=1nAf(shA):CmaxB≤U and 1∥∑h=1nAf(shA):∑k=1nBCkB≤U, respectively.


## 3. Problem1∥∑h=1nAf(shA):CmaxB≤U

In this section, we develop an optimal polynomial time algorithm to solve the problem1∥∑h=1nAf(shA):CmaxB≤U.  The following Lemmas 1 and 2 are easily obtained, and we omit the details of the proof.Lemma 1.
Given a sequenceπ={J1B,J2B,…,JnBB,J1A,J2A,…,JnAA} and a constant U, define CπB=∑k=1nBpkB. Then, if U<CπB, the sequence π corresponds to an infeasible schedule.Lemma 2.
Given a sequenceπ={J1A,J2A,…,JnAA,J1B,J2B,…,JnBB} and a constant U, define CπB=∑h=1nAphA+∑k=1nBpkB.  Then, if U≥CπB, the schedule corresponding to the sequence π is feasible.Now we can define bounds for the constraintU.  Define U_=∑k=1nBpkB and U¯=∑h=1nAphA+∑k=1nBpkB.Lemma 3.
IfU<U_=∑k=1nBpkB, there are no feasible schedules.  If U≥U¯=∑h=1nAphA+∑k=1nBpkB, there are feasible schedules for all possible sequences.From now on, we will always assume thatU_≤U≤U¯ in this problem.Lemma 4.
An optimal schedule exists in which theA-agent’s jobs are processed in the nondecreasing order of processing times phA.Proof.
The resource consumption functionf is a strictly increasing continuous function to A-agent’s jobs.  Since starting A-agent’s jobs later consumes more resources, A-agent’s jobs should be processed as early as possible.  Hence, A-agent’s jobs should be processed in a nondecreasing order of phA.Lemma 5.
An optimal schedule exists in which theB-agent’s jobs are consecutively processed.Proof.
The makespan of agentB is the maximum completion time of B-agent’s jobs on the single machine; that is, the makespan of agent B is the completion time of B-agent’s last job.  Using a pairwise job interchange argument, we can consecutively process B-agent’s jobs and consolidate all B-agent’s jobs into a block.Next, an algorithm to determine an optimal schedule of the problem1∥∑h=1nAf(shA):CmaxB≤U is developed as follows.Algorithm 6.Step 1.
Seti←1.Step 2.
Arrange theA-agent’s jobs as {J1A,J2A,…,JnAA} according to the nondecreasing order of phA and denote all B-agent’s jobs as a dummy job B1.Step 3.
Define sequenceS={J1A,J2A,…,JnA-1A,JnAA,B1} and calculate the makespan CmaxB for agent B.  If CmaxB≤U, then the sequence S is an optimal schedule.Step 4.
Select the dummy jobB1 to the (nA-i)th position in the sequence {J1A,J2A,…,JnA-iA,JnA-i+1A,…,JnAA} and calculate the makespan CmaxB for agent B.  If CmaxB≤U, then the sequence Si={J1A,J2A,…,JnA-iA,B1,JnA-i+1A,…,JnA-1A,JnAA} is an optimal schedule, and stop.  Otherwise, go to Step 5.Step 5.
Ifi<nA and CmaxB>U, then i←i+1, and go to Step 4. Otherwise, stop.Theorem 7.
Algorithm6 generates an optimal schedule for the problem 1∥∑h=1nAf(shA):CmaxB≤U in O(nAlognA+nB) time.Proof.
The proof of optimality is straightforward from the results of Lemmas1–5.  We now turn to time complexity.  The time to sequence the jobs of set JA according to the nondecreasing order of phA is O(nAlognA). Creating dummy job B1 incurs O(nB) operations.  The solution requires finding locations for the dummy job B1 among the A-agent’s jobs sequenced by the nondecreasing order of phA.  So, the overall computational complexity of Algorithm 6 is bounded by O(nAlognA+nB). This completes the proof.


## 4. Problem1∥∑h=1nAf(shA):∑k=1nBCkB≤U

For the problem1∥∑h=1nAf(shA):∑k=1nBCkB≤U, we have the following lemmas that are similar to Lemmas 1, 2, and 3.Lemma 8.
Given a sequenceπ={J1B,J2B,…,JnBB,J1A,J2A,…,JnAA} and a constant U, define CπB=∑k=1nB(nB-k+1)pkB. Then, if U<CπB, the sequence π corresponds to an infeasible schedule.Proof.
IfU<CπB, then
(1)∑k=1nBCkB=∑k=1nB(skB+pkB)=∑k=1nB(s1B+∑i=1k-1piB+pkB)=∑k=1nB(s1B+∑i=1kpiB)=∑k=1nBs1B+∑k=1nB∑i=1kpkB=nBs1B+∑k=1nB(nB-k+1)pkB=CπB>U,
which implies that the sequence π is infeasible.Lemma 9.
Given a sequenceπ={J1A,J2A,…,JnAA,J1B,J2B,…,JnBB} and a constant U, define CπB=nB∑h=1nAphA+∑k=1nB(nB-k+1)pkB.  Then, if U≥CπB, the schedule corresponding to the sequence π is feasible.Proof.
IfU≥CπB, then
(2)∑k=1nBCkB=∑k=1nB(skB+pkB)=∑k=1nB(s1B+∑i=1k-1piB+pkB)=∑k=1nB(s1B+∑i=1kpiB)=∑k=1nBs1B+∑k=1nB∑i=1kpkB=nB∑h=1nAphA+∑k=1nB(nB-k+1)pkB=CπB≤U,
which implies that the sequence π is feasible.Now we can define bounds for the constraintU.  Let the processing times of the B-agent’s jobs be ordered in the nondecreasing order p1B≤p2B≤⋯≤pnBB.  Then, define U_=∑k=1nB(nB-k+1)pkB and U¯=nB∑h=1nAphA+∑k=1nBkpkB.  These constants play an important role in this problem.Lemma 10.
IfU<U_=∑k=1nB(nB-k+1)pkB, there are no feasible schedules. If U≥U¯=nB∑h=1nAphA+∑k=1nBkpkB, there are feasible schedules for all possible sequences.In view of these properties, the analysis in the following section will be confined to the case in whichU_≤U≤U¯.Lemma 11.
An optimal schedule exists in which theA-agent’s jobs are processed in the nondecreasing order of processing times phA.Proof.
The proof is same to Lemma4, and we omit the details.Lemma 12.
An optimal schedule exists in which theB-agent’s jobs are consecutively processed in the nondecreasing order of processing times pkB.Proof.
Using a pairwise job interchange argument, we can consecutively processB-agent’s jobs in the nondecreasing order of processing times pkB.Next, an algorithm to determine an optimal schedule of the problem1∥∑h=1nAf(shA):∑k=1nBCkB≤U is developed as follows.Algorithm 13.Step 1.
Seti←1.Step 2.
Arrange theA-agent’s jobs as {J1A,J2A,…,JnAA} according to the nondecreasing order of phA,  and denote all B-agent’s jobs sequenced by the nondecreasing order of pkB as a dummy job B1.Step 3.
Define sequenceS={J1A,J2A,…,JnA-1A,JnAA,B1} and calculate the total completion time ∑k=1nBCkB for agent B.  If ∑k=1nBCkB≤U, then the sequence S is an optimal schedule.Step 4.
Select the dummy jobB1 to the (nA-i)th position in the sequence {J1A,J2A,…,JnA-iA,JnA-i+1A,…,JnAA} and calculate ∑k=1nBCkB for agent B.  If ∑k=1nBCkB≤U, then the sequence Si={J1A,J2A,…,JnA-iA,B1,JnA-i+1A,…,JnA-1A,JnAA} is an optimal schedule, and stop. Otherwise, go to Step 5.Step 5.
Ifi<nA and ∑k=1nBCkB>U, then i←i+1, and go to Step 4.  Otherwise, stop.Theorem 14.
Algorithm13 generates an optimal schedule for the problem 1∥∑h=1nAf(shA):∑k=1nBCkB≤U in O(nAlognA+nBlognB) time.Proof.
The proof of optimality is straightforward from the results of Lemmas8–12.  We now turn to time complexity.  The times to sequence the jobs of sets JA and JB according to the nondecreasing orders of phA and pkB are O(nAlognA) and O(nBlognB), respectively.  Creating dummy job B1 incurs O(nB) operations.  So, the overall computational complexity of Algorithm 13 is bounded by O(nAlognA+nBlognB).  This completes the proof.


## 5. Conclusions

In this paper, we introduce a new scheduling model in which both resource-dependent starting times and two agents exist simultaneously.  The objective is to minimize the total amount of resource consumption of the first agent with the restriction that the makespan or the total completion time of the second agent does not exceed a given bound.  We propose the optimal properties and the optimal polynomial time algorithms for the considered scheduling problems.Future research may be directed to analyze the problems with other objective functions such as minimizing the number of late jobs, the total weighted completion time, and tardiness.  An interesting research topic is also to consider other resource consumption functions.  Finally, the future research direction is to analyze the scheduling problem with more than two agents or in other machine environments.



---

*Source: 805261-2013-08-19.xml*