# Two-Agent Scheduling to Minimize the Maximum Cost with Position-Dependent Jobs

Authors: Long Wan
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

This paper investigates a single-machine two-agent scheduling problem to minimize the maximum costs with position-dependent jobs. There are two agents, each with a set of independent jobs, competing to perform their jobs on a common machine. In our scheduling setting, the actual position-dependent processing time of one job is characterized by variable function dependent on the position of the job in the sequence. Each agent wants to fulfil the objective of minimizing the maximum cost of its own jobs. We develop a feasible method to achieve all the Pareto optimal points in polynomial time.


---

## Body

## 1. Introduction

Scheduling theory is very useful in industrial applications and provides much guidance in the real world. The traditional scheduling problems have only one agent to optimize its own objective. With the development of modern technology, more and more scheduling models occur. Once entering the 21st century, the existing one-agent scheduling models can not meet with the requirement of the time. Particularly, in the big data period, the internet must handle various instructions of online net citizens and meet with their different preferences. Under such environments, multiagent scheduling models appear. The ultimate theoretical results of multiagent scheduling problems are to get all the Pareto optimal points. Such a problem is usually called asPareto optimization problem (PP for short). Since Pareto optimization problems are very hard to deal with large number of scheduling models, the researchers consider somewhat weaker scheduling problems like single-objective scheduling problems, that is, to optimize the objective of one agent with the restrictions of the objectives of the other agents. Such a problem is calledconstrained optimization problem (CP for short). And, in reality, the resolution of CP problems will be more helpful for the resolution of PP problems. There are many papers in which the ultimate resolution of PP problems depends on the research results of CP problems; [1] is one of the most outstanding and instructive papers.Of multiagent problems, the two-agent problems are obviously most simple and most representative. Agnetis et al. [1] first defined the two problems for two-agent scheduling models and opened the door of studying two-agent scheduling problems. Baker and Smith [2] dealt with two-agent scheduling problems by combining the two objectives of both agents into one single objective. And the method can also obtain all the Pareto optimal points in some certain condition. Yuan et al. [3] pointed out the faults of some dynamic programming designed in [2] and developed correct methods. Biskup [4] first introduced position-dependent processing times to classic scheduling models and developed optimal algorithms for the considered problems. Further, Mosheiov [5] extended it to more scheduling problems, including single-machine problems, multicriteria problems, and parallel-machine problems. Bachman and Janiak considered some special position-dependent scheduling problem and proved that it is NP-hard in the strong sense. But with regret, the proof is not complete with lack of key statement of some places. Janiak and Kovalyov [6] supplemented the key statement and provided a new complete proof. Wang and Xia [7] and Wang [8] considered position-dependent processing times in some flow shop scheduling problems. Yin et al. [9] generalized the position-dependent functions of processing times and some theoretical results appearing in [4, 5]. Yang [10] simultaneously considered the jobs deterioration and the position-dependent learning effect under deteriorating maintenance environment and analyzed some results of single-machine scheduling models. Biskup [11] gave an excellent retrospect of scheduling theory with learning effects. Liu et al. [12] initially introduced two-agent models to position-dependent scheduling problems. They studied a single-machine two-agent CP scheduling problem in which one agent wants to minimize the total completion time subject to the maximum cost of the other agent bounded by a constant, where jobs’ actual processing times are defined by linear functions dependent on their positions in the schedule. Furthermore, Wan [13] deepened the results and showed that the PP version of [12] is polynomially solvable. For more related papers, we refer to Yin et al. [14–16].In the paper, we study the two-agent PP scheduling model introduced in [12, 13]. The objectives of the two agents are that both want to minimize the maximum cost of jobs. We develop a polynomial time algorithm to show that the PP problem can be efficiently solved. Section 2 provides some notations and problem description. A polynomial time algorithm is developed to show that the PP problem is solvable in Section 3.


## 2. Notations and Problem Statement

There are two agents, agentA and agent B, competing to schedule their respective jobs on a common single machine. The job sets of agent A and B are J
A
=
{
J
1
A
,
J
2
A
,
…
,
J
n
A
A
} and J
B
=
{
J
1
B
,
J
2
B
,
…
,
J
n
B
B
}, respectively, where n
A and n
B are the numbers of the jobs of agents A and B, respectively. The normal processing time of J
j
X is denoted by p
j
X, X
=
A
,
B, j
=
1,2
,
…
,
n
X. Each job J
j
X has a nondecreasing and nonnegative cost function f
j
X
(
·
) defined on the completion time. Let J
=
J
A
∪
J
B and n
=
n
A
+
n
B. For a feasible schedule of J, the following three conditions follow.(i)
The first job is processed at time zero.
(ii)
The processing of the jobs ofJ does not overlap.
(iii)
The machine processes the jobs ofJ without idle time.From the conditions, any schedule is consistent with a sequence ofJ. Generally, we let σ denote a sequence of J, as well as the consistent schedule. Let p
h
r
X denote the actual processing time of job J
h
X at position r, p
h
r
X
=
p
h
X
+
b
r, where b represents the variable ratio. We assume that |
b
|
<
p
min
⁡
/
n if b is negative lest the actual processing time of some job is negative in some feasible schedules, where p
min
⁡
=
min
⁡
{
p
j
X
:
J
j
X
∈
J
}. Given a sequence σ, the completion time of job J
j
X is denoted by C
j
X
(
σ
). The cost of job J
j
X is equal to f
j
X
(
C
j
X
(
σ
)
). Therefore, the cost of agent X is defined as the maximum cost of jobs; that is, f
max
⁡
X
(
σ
)
=
max
⁡
{
f
1
X
(
C
1
X
(
σ
)
)
,
f
2
X
(
C
2
X
(
σ
)
)
,
…
,
f
n
X
X
(
C
n
X
X
(
σ
)
)
}, X
=
A
,
B. For any job set J
0
⊆
J, we define the completion time of J
0 denoted by C
J
0
(
σ
) to be the completion time of its last job. If there is no confusion, C
j
X, C
J
0, and f
max
⁡
X are short for C
j
X
(
σ
), C
J
0
(
σ
), and f
max
⁡
X
(
σ
), respectively. For any two feasible schedules σ and ρ, we call σ
Pareto better than ρ if and only if (
f
max
⁡
A
(
σ
)
,
f
max
⁡
B
(
σ
)
)
≤
(
f
max
⁡
A
(
ρ
)
,
f
max
⁡
B
(
ρ
)
) and at least one inequality strictly holds. σ is calledPareto optimal if there is no schedule Pareto better than σ. And (
f
max
⁡
A
(
σ
)
,
f
max
⁡
B
(
σ
)
) is a Pareto optimal point. The objective is to find all the Pareto optimal points. Adopting the notation of [1], the PP problem can be denoted by 1
|
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
|
f
max
⁡
A
∘
f
max
⁡
B. For any job set J
0
⊆
J, let P
(
J
0
)
=
∑
J
j
X
∈
J
0
‍
p
j
X
+
|
J
0
|
(
|
J
0
|
+
1
)
b
/
2. Furthermore, if J
0
⊆
J
1, then P
(
J
0
)
≤
P
(
J
1
).Lemma 1 (see [13]).
Letσ be a feasible schedule of job set H
⊆
J; then C
H
(
σ
)
=
P
(
H
).From Lemma1, we know that the completion time of H does not depend on the processing order of jobs of H.Lety
=
(
y
A
,
y
B
) be a number pair; we consider problem 1
|
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
|
f
max
⁡
A ≤ y
A
:
f
max
⁡
B
≤
y
B. For the pair y, we define the resulting due date of J
j
X to be D
j
X
(
y
) with f
j
X
(
D
j
X
(
y
)
)
≤
y
X and f
j
X
(
D
j
X
(
y
)
+
1
)
>
y
X, X
=
A
,
B; j
=
1,2
,
…
,
n
X. Let EDD(
y
) be the schedule in which we sequence the jobs of J in nondecreasing order of the resulting due dates and try to schedule A-jobs after B-jobs for breaking the tie if it exists. Similar to the proof of EDD rule [17], we can get the following lemma.Lemma 2.
If problem1
|
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
|
f
max
⁡
A
≤
y
A
:
f
max
⁡
B
≤
y
B is feasible, then schedule EDD(
y
) is a feasible schedule.


## 3. The Main Results

In this section, we will describe our algorithm to show that the PP problem1
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
f
max
⁡
A
∘
f
max
⁡
B can be solved in O
(
n
A
3
n
B
+
n
A
n
B
3
). First, we design an algorithm to solve the problem 1
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
f
max
⁡
A
:
f
max
⁡
B
≤
U and the problem 1
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
f
max
⁡
A
≤
U
:
f
max
⁡
B for any given bound U.Algorithm  A. For problem 1
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
f
max
⁡
A
:
f
max
⁡
B
≤
U.Step  0. Initialize J
¯
≔
J, n
¯
≔
n
A
+
n
B, n
¯
A
≔
n
A, n
¯
B
≔
n
B, f
max
⁡
A
≔
-
∞.Step  1. Calculate the current completion time T
≔
P
(
J
¯
).Step  2. If n
¯
A
=
0 and n
¯
B
=
0, then Stop and Return the value f
max
⁡
A.Step  3. If n
¯
A
=
0 and n
¯
B
>
0, let K be the set of B-jobs of J
¯ with the cost at most U. If K
=
∅, then Stop and Return infeasible. Otherwise arbitrarily select one B-job J
k
B of K and schedule job J
k
B at position n
¯, n
¯
≔
n
¯
-
1, n
¯
B
≔
n
¯
B
-
1, J
¯
≔
J
¯
∖
{
J
k
B
}, go to Step  1.Step  4. If n
¯
A
>
0 and n
¯
B
=
0, we select an A-job J
l
A out of J
¯ so that f
l
A
(
T
)
=
min
⁡
J
i
A
∈
J
¯
f
i
A
(
T
) and schedule J
l
A at position n
¯, n
¯
≔
n
¯
-
1
,
n
¯
A
≔
n
¯
A
-
1
,
f
max
⁡
A
≔
{
f
max
⁡
A
,
f
l
A
(
T
)
}
,
J
¯
≔
J
¯
∖
{
J
l
A
}, go to Step  1.Step  5. If n
¯
A
>
0 and n
¯
B
>
0, let K be the set of B-jobs of J
¯ with the cost at most U. If K
=
∅, then we select an A-job J
l
A out of J
¯ so that f
l
A
(
T
)
=
min
⁡
J
i
A
∈
J
¯
f
i
A
(
T
) and schedule J
l
A at position n
¯, n
¯
≔
n
¯
-
1, n
¯
A
≔
n
¯
A
-
1, f
max
⁡
A
≔
{
f
max
⁡
A
,
f
l
A
(
T
)
}, J
¯
≔
J
¯
∖
{
J
l
A
}, go to Step  1. Otherwise arbitrarily select one B-job J
k
B of K and schedule job J
k
B at position n
¯, n
¯
≔
n
¯
-
1, n
¯
B
≔
n
¯
B
-
1, J
¯
≔
J
¯
∖
{
J
k
B
}, go to Step  1.We can apply AlgorithmA to problem 1
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
f
max
⁡
A
≤
U
:
f
max
⁡
B only by exchanging the identities of agent A and agent B.Theorem 3.
AlgorithmA solves the problem 1
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
f
max
⁡
A
:
f
max
⁡
B
≤
U correctly.Proof.
Supposeσ is the resulted sequence by applying Algorithm A to problem 1
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
f
max
⁡
A
:
f
max
⁡
B
≤
U. Let ρ be an optimal sequence of problem 1
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
f
max
⁡
A
:
f
max
⁡
B
≤
U; we only need to prove that f
max
⁡
A
(
σ
)
≤
f
max
⁡
A
(
ρ
). Let J
i
0
A be such an A-job that f
i
0
A
(
σ
)
=
f
max
⁡
A
(
σ
); we denote by K the set of jobs prior to job J
i
0
A in σ including job J
i
0
A. Let J
K be the last job of K scheduled in ρ; we denote the set of jobs prior to job J
K in ρ including job J
K by L. K
⊆
L and P
(
K
)
≤
P
(
L
). According to Algorithm A, for each B-job J
j
B
∈
K, we have f
j
B
(
P
(
K
)
)
>
U. Since P
(
K
)
≤
P
(
L
), f
j
B
(
P
(
L
)
)
≥
f
j
B
(
P
(
K
)
)
>
U. Furthermore, J
K must be an A-job J
j
0
A. By the algorithm, we know that f
i
0
A
(
P
(
K
)
)
=
min
⁡
J
i
A
∈
K
{
f
i
A
(
P
(
K
)
)
}. So (1)
f
max
⁡
A
ρ
≥
f
j
0
A
(
C
j
0
A
(
ρ
)
)
=
f
j
0
A
(
P
(
L
)
)
≥
f
j
0
A
(
P
(
K
)
)
≥
f
i
0
A
(
P
(
K
)
)
=
f
max
⁡
A
(
σ
)
.
We complete the proof.In the following, we state a very popular method to get a Pareto optimal point of problem1
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
f
max
⁡
A
∘
f
max
⁡
B. The method is first developed in [18] and then applied in [1, 19, 20].Algorithm
B
(
U
). For problem 1
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
f
max
⁡
A
∘
f
max
⁡
B.Step  0. Call Algorithm A to 1
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
f
max
⁡
A
:
f
max
⁡
B
≤
U. If algorithm A returns infeasible, then let Algorithm B
(
U
) stop and returns infeasible. Otherwise let x be the returned value f
max
⁡
A. Call Algorithm A to 1
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
f
max
⁡
A
≤
x
:
f
max
⁡
B, let y be the returned value, then we stop the algorithm and return the pair (
x
,
y
).Theorem 4.
AlgorithmB
(
U
) returns a Pareto optimal point (
x
,
y
) with y
≤
U. Furthermore, if (
x
¯
,
y
¯
) is also a Pareto optimal point with y
¯
≤
U, then x
¯
≥
x and y
¯
≤
y.For each scheduleσ, we define the indicator function Δ
j
i
(
σ
) as below: (2)
Δ
j
i
(
σ
)
=
1
,
if
J
i
A
≺
σ
J
j
B
,
0
,
if
J
j
B
≺
σ
J
i
A
.Here J
i
A
≺
σ
J
j
B means that J
i
A is prior to J
j
B in σ and vice versa. Furthermore, we set Δ
(
σ
)
=
∑
1
≤
i
≤
n
A
,
1
≤
j
≤
n
B
‍
Δ
j
i
(
σ
).Lemma 5.
For any two Pareto optimal pointsy
=
(
y
1
,
y
2
) and z
=
(
z
1
,
z
2
), Δ
(
E
D
D
(
y
)
)
<
Δ
(
E
D
D
(
z
)
) only if y
1
>
z
1 and y
2
<
z
2.Proof.
Since the cost functionf
j
X
(
·
) of job J
j
X is nondecreasing, X
=
A
,
B
;
j
=
1,2
,
…
,
n
X, we have D
i
A
(
y
)
≥
D
i
A
(
z
) for any A-job J
i
A, i
=
1,2
,
…
,
n
A and D
j
A
(
y
)
≤
D
j
A
(
z
) for any B-job J
j
B, j
=
1,2
,
…
,
n
B. Therefore,(3)
Δ
j
i
EDD
y
≤
Δ
j
i
EDD
z
,
i
=
1,2
,
…
,
n
A
,
j
=
1,2
,
…
,
n
B
.Note that y
=
(
y
1
,
y
2
) and z
=
(
z
1
,
z
2
) are two Pareto optimal points; we have f
max
⁡
A
(
EDD
(
y
)
)
=
y
1
,
f
max
⁡
B
(
EDD
(
y
)
)
=
y
2 and f
max
⁡
A
(
EDD
(
z
)
)
=
z
1, f
max
⁡
B
(
EDD
(
z
)
)
=
z
2. Let J
j
0
B be such a B-job that f
j
0
B
(
C
j
0
B
(
EDD
(
z
)
)
)
=
z
2 which means that C
j
0
B
(
EDD
(
z
)
)
=
D
j
0
B
(
z
); we denote the job set of jobs prior to J
j
0
B in EDD
(
z
) including job J
j
0
B by K:(4)
D
j
B
(
z
)
≤
D
j
0
B
(
z
)
,
J
j
B
∈
K
.Let J
K be the last job of K scheduled in EDD
(
y
), and we denote the set of jobs prior to job J
K in EDD
(
y
) including job J
K by L: K
⊆
L and P
(
K
)
≤
P
(
L
). By (4), (5)
f
j
B
P
L
≥
f
j
B
P
K
=
f
j
B
D
j
0
B
z
≥
z
2
>
y
2
,
J
j
B
∈
K
.It means that J
K is not a B-job but an A-job. And we denote the A-job by J
i
0
A; then(6)
Δ
j
0
i
0
(
EDD
(
y
)
)
<
Δ
j
0
i
0
(
EDD
(
z
)
)
.Therefore, (7)
Δ
EDD
y
=
∑
1
≤
i
≤
n
A
,
1
≤
j
≤
n
B
‍
Δ
j
i
(
EDD
(
y
)
)
<
∑
1
≤
i
≤
n
A
,
1
≤
j
≤
n
B
‍
Δ
j
i
(
EDD
(
z
)
)
=
Δ
(
EDD
(
z
)
)
.
We complete the proof.Algorithm
C. For problem 1
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
f
max
⁡
A
∘
f
max
⁡
B.Step  0. Initialize U
≔
+
∞, k
≔
1.Step  1. Call Algorithm B
(
U
) for problem 1
|
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
|
f
max
⁡
A
∘
f
max
⁡
B.Step  2. If Algorithm A
(
U
) returns infeasible, then we stop and output the Pareto optimal points (
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
k
,
y
k
). Otherwise, let (
x
,
y
) be the resulted schedule from Algorithm A
(
U
); set (
x
k
,
y
k
)
≔
(
x
,
y
), U
≔
y
k
-
1, k
≔
k
+
1. And go to Step  1.Theorem 6.
AlgorithmC returns all the Pareto optimal points of problem 1
p
h
r
A
=
p
h
A
+
b
r
,
p
k
v
B
=
p
k
B
+
b
v
f
max
⁡
A
∘
f
max
⁡
B in O
(
n
A
3
n
B
+
n
A
n
B
3
).Proof.
It is obvious that AlgorithmC returns all the Pareto optimal points. We then analyze the complexity of Algorithm C. Note that Algorithm A can be implemented in O
(
n
A
2
+
n
B
2
); Algorithm B
(
U
) can also be implemented in O
(
n
A
2
+
n
B
2
). For any feasible schedule τ, 0
≤
Δ
(
τ
)
≤
n
A
n
B. Hence, by Lemma 5, there are at most n
A
n
B
+
1 times of implementation of Algorithm B
(
U
) during the running of Algorithm C. Furthermore, we can get that Algorithm C can be completed in O
(
n
A
3
n
B
+
n
A
n
B
3
).



---

*Source: 932680-2015-04-12.xml*