# Some Single-Machine Scheduling Problems with Learning Effects and Two Competing Agents

Authors: Hongjie Li; Zeyuan Li; Yunqiang Yin
Journal: The Scientific World Journal
 (2014)

---

## Abstract

This study considers a scheduling environment in which there are two agents and a set of jobs, each
of which belongs to one of the two agents and its actual processing time is defined as a decreasing linear
function of its starting time. Each of the two agents competes to process its respective jobs on a single
machine and has its own scheduling objective to optimize. The objective is to assign the jobs so that the
resulting schedule performs well with respect to the objectives of both agents. The objective functions
addressed in this study include the maximum cost, the total weighted completion time, and the discounted
total weighted completion time. We investigate three problems arising from different combinations of the
objectives of the two agents. The computational complexity of the problems is discussed and solution
algorithms where possible are presented.


---

## Body

## 1. Introduction

In traditional scheduling research, it is commonly assumed that the processing times of the jobs remain unchanged throughout the scheduling horizon. However, under certain circumstances, the job processing times may become short due to learning effects in the production environment. For example, Biskup  [1] points out that the repeated processing of similar tasks will improve workers’ efficiency; that is, it takes workers shorter times to process setups, operate machines or software, or handle raw materials and components. In such an environment, a job scheduled later will consume less time than the same job when scheduled earlier. Jobs in such a setting are said to be under the “learning effect” in the literature.Biskup [1] and Cheng and Wang [2] first introduce the idea of learning into the field of scheduling independently. Since then, a large body of literature on scheduling with learning effects has emerged. Examples of such studies are Mosheiov  [3], Mosheiov and Sidney  [4], Bachman and Janiak [5], Janiak and Rudek [6], Wang [7], and Yin et al. [8]. Biskup [9] provides a comprehensive review of research on scheduling with learning effects. For more recent studies in this line of research, the reader is referred to Jiang et al. [10, 11], Yang  [12], S.-J. Yang and D.-L. Yang  [13], Wang et al. [14], Wu et al. [15], Xu et al. [16], and Yin et al. [8].All the above papers consider the traditional case with a single agent. In recent years scheduling researchers have increasingly considered the setting of multiple competing agents, in which multiple agents need to process their own sets of jobs, competing for the use of a common resource and each agent has its own objective to optimize. However, there is little scheduling research in the multiagent setting in which the jobs are under learning effects. Liu et al. [17] study two models with two agents and position-dependent processing times. They assume that the actual processing time of job J
j is p
j
+
b
r in the aging-effect model, while the actual processing time of J
j is p
j
-
b
r in the learning-effect model, where r represents the processed position of J
j and b
>
0 denotes the aging or learning index. Ho et al. [18] define the actual processing time of job J
j as p
j
=
a
j
(
1
-
k
t
) if it is processed at time t, where a
j denotes the normal processing time of job J
j and k
≥
0 represents a constant such that k
(
t
0
+
∑
j
=
1
n
a
j
-
a
min
⁡
)
<
1 with a
min
⁡
=
min
⁡
j
=
1,2
,
…
,
n
{
a
j
}. Inspired by Ho et al. [18], Yin et al. [19] consider some two-agent scheduling problems under the learning effect model proposed in Ho et al. [18], in which the objective functions for agent A include the maximum earliness cost, the total earliness cost, and the total weighted earliness cost, and the objective function for agent B is always the same, that is, maximum earliness cost, and the objective is to minimize the objective function of agent A while keeping the objective function of agent B not greater than a given level. Similar models have been further studied by Wang and Xia [20], Wang [21], and so on. For the other related two-agent works without time-dependent processing times, the reader can refer to Baker and Smith [22], Agnetis et al. [23, 24], Cheng et al. [25, 26], Ng et al. [27], Mor and Mosheiov  [28], Lee et al. [29], Leung et al. [30], Wan et al. [31], Yin et al. [19, 32], Yu et al. [33], and Zhao and Lu [34].This study introduces a new scheduling model in which both the two-agent concept and the learning effects exist, simultaneously. We consider the following objective functions: the maximum cost, total completion time, total weighted completion time, and discounted total weighted completion time. The structural properties of optimal schedules are derived and polynomial time algorithms are developed for the problems where possible.The remaining part of the study is organized as follows: Section2 introduces the notation and terminology used throughout the paper. Sections 3–6 analyze the computational complexity and derive the optimal properties of the problems under study. The last section concludes the paper and suggests topics for future research.


## 2. Model Formulation

The problem investigated in this paper can be formally described as follows. Suppose that there are two agentsA and B, each of whom has a set of nonpreemptive jobs. The two agents compete to process their jobs on a common machine. Agent A has to process the job set  J
A
=
{
J
1
A
,
J
2
A
,
…
,
J
n
A
A
}, while agent B has to process the job set J
B
=
{
J
1
B
,
J
2
B
,
…
,
J
n
B
B
}. All the jobs are available for processing at time t
0, where t
0
≥
0. Let X
∈
{
A
,
B
}. The jobs belonging to agent X are called A-jobs. Associated with each job J
j
X
(
j
∈
{
1,2
,
…
,
n
X
}
), there are normal processing time a
j
X and weight w
j
X. Due to the learning effect, the actual processing time p
j of job J
j
X is defined as
(1)
p
j
X
=
a
j
X
(
1
-
k
t
)
,
j
=
1,2
,
…
,
n
X
,
where t
≥
t
0denotes job’s starting time and k
≥
0represents constant such that k
(
t
0
+
∑
J
j
X
∈
J
A
∪
J
B
a
j
X
-
a
min
⁡
)
<
1, where a
min
⁡
=
min
⁡
J
j
X
∈
J
A
∪
J
B
{
a
j
X
} (see Ho et al. [18] for details).Given a feasible scheduleS of the n
=
n
A
+
n
B jobs, we use C
j
X
(
S
) to denote the completion time of job J
j
X and omit the argument S whenever this does not cause confusion. The makespan of agent X is C
max
⁡
X
=
max
⁡
j
=
1,2
,
…
,
n
X
{
C
j
X
}. For each job J
j
X,  let f
j
X
(
·
) be a nondecreasing function.  In this case, the maximum cost is defined as f
max
⁡
X
=
max
⁡
j
=
1,2
,
…
,
n
X
{
f
j
X
(
C
j
X
)
}. The objective function of agent X considered in this paper includes the following: f
max
⁡
X (maximum cost), ∑
‍
C
j
X (total completion time), ∑
‍
w
j
X
C
j
X (total weighted completion time), and ∑
‍
w
j
X
(
1
-
e
-
r
C
j
X
) (discounted total weighted completion time).Using the three-field notation schemeα
|
β
|
γ introduced by Graham et al. [35], the problems considered in this paper are denoted as follows: 1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
f
max
⁡
A
(
C
A
)
:
f
max
⁡
B
(
C
B
)
≤
U, 1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
∑
‍
C
j
A
:
f
max
⁡
B
(
C
B
)
≤
U, 1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
∑
‍
w
j
A
C
j
A
:
f
max
⁡
B
(
C
B
)
≤
U, and 1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
∑
‍
w
j
A
(
1
-
e
-
r
C
j
A
)
:
f
max
⁡
B
(
C
B
)
≤
U.Note that all the objective functions involved in the considered problems are regular; that is, they are nondecreasing in the job completion times. Hence there is no benefit in keeping the machine idle.


## 3. Problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
f
max
A
:
f
max
B
≤
U

In this section we address the problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
f
max
⁡
A
:
f
max
⁡
B
≤
U and show that it can be solved optimally in polynomial time. We first develop some structural properties of optimal schedules for the problem which will be used in developing the algorithm.Lemma 1 (see [19]).
For problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
C
max
⁡, the makespan is equal to
(2)
(
t
0
-
1
k
)
∏
j
=
1
n
X
‍
(
1
-
k
a
j
X
)
+
1
k
=
(
t
0
-
1
k
)
∏
j
=
1
n
A
‍
(
1
-
k
a
j
A
)
∏
j
=
1
n
B
‍
(
1
-
k
a
j
B
)
+
1
k
.In the sequel, we setu
=
(
t
0
-
(
1
/
k
)
)
∏
j
=
1
n
X
‍
(
1
-
k
a
j
X
)
+
(
1
/
k
). Then the following results hold.Proposition 2.
For the problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
f
max
⁡
A
:
f
max
⁡
B
≤
U, if there is aB-job J
k
B such that f
k
B
(
u
)
≤
U, then there exists an optimal schedule such that J
k
B is scheduled last and there is no optimal schedule where anA-job is scheduled last.Proof.
Assume thatS is an optimal schedule where the B-job J
h
B is not scheduled in the last position. Let π denote the set of jobs scheduled prior to job J
h
B. We construct from S a new schedule S
′by moving job J
h
B to the last position and leaving the other jobs unchanged in S. Then, the completion times of the jobs processed before job J
h
B in S
′ are the same as that in S since there is no change for any job preceding J
h
B in S. The jobs belonging to π are scheduled earlier, so their completion times are smaller in S
′ by Lemma 1. It follows that f
k
X
(
C
k
X
(
S
′
)
)
≤
f
k
X
(
C
k
X
(
S
)
) for any job J
k
X in π, where X
∈
{
A
,
B
}. By the assumption that f
h
B
(
u
)
≤
U, job J
h
B is feasible in S
′,  so schedule S
′ is feasible and optimal, as required.For eachB-job J
j
B, let us define a deadline D
j
B such that f
j
B
(
C
j
B
)
≤
U for C
j
B
≤
D
j
B and f
j
B
(
C
j
B
)
>
U for C
j
B
>
D
j
B (if the inverse function f
j
B
(
·
) is available, the deadlines can be evaluated in constant time; otherwise, this requires logarithmic time).Proposition 3.
For the problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
f
max
⁡
A
:
f
max
⁡
B
≤
U, there exists an optimal schedule where the B-jobs are scheduled according to the nondecreasing order of D
j
B.Proof.
Assume thatS is an optimal schedule where the B-jobs are not scheduled according to the nondecreasing order of D
j
B. Let J
l
B and J
h
B be the first pair of jobs such that D
l
B
>
D
h
B. In this schedule, job J
l
B is processed earlier; then a set of A-jobs, denoted as π, are consecutively processed and then job J
h
B. In addition, denote by π
′ the set of jobs processed after job J
h
B. We construct from S a new schedule S
′ by extracting job J
l
B, reinserting it just after job J
h
B and leaving the other jobs unchanged in schedule S. Then the completion times of the jobs processed prior to job J
l
B in S
′ are the same as that in S. By Lemma 1, the completion time of job J
h
B in S equals that of job J
l
B in S
′; that is, C
l
B
(
S
′
)
=
C
h
B
(
S
), so the completion times of the jobs belonging to π
′ are identical in both S and S
′. Since S is feasible, it follows that C
l
B
(
S
′
)
=
C
h
B
(
S
)
≤
D
h
B
<
D
l
B, so job J
l
B is feasible in S
′. The π-jobs and job J
h
B are scheduled earlier in S
′, implying that their actual processing times are smaller in S
′, so their completion times are earlier in S
′, and thus they remain feasible. Therefore, schedule S
′ is feasible and optimal.
Thus, repeating doing this procedure for all theB-jobs not sequenced according to nondecreasing order of D
j
B completes the proof.Proposition 4.
For the problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
f
max
⁡
A
:
f
max
⁡
B
≤
U, if f
k
B
(
u
)
>
U for any B-job J
k
B, then there exists an optimal schedule where the A-job with the smallest cost f
k
A
(
u
) is processed in the last position.Proof.
Assume thatS is an optimal schedule where the A-job with the smallest cost J
h
A, that is, f
h
A
(
u
)
=
min
⁡
J
j
A
∈
J
A
{
f
j
A
(
u
)
}, is not processed in the last position. By the hypothesis, the last job in schedule S is an A-job, say J
l
A. This means f
h
A
(
u
)
<
f
l
A
(
u
). In this schedule, job J
h
A is scheduled earlier. Let π denote the set of jobs scheduled after job J
h
A and prior to job J
l
A. We construct from S a new schedule S
′ by extracting job J
h
A, reinserting it just after job J
l
A, and leaving the other jobs unchanged in schedule S. There is no change for any job preceding J
h
A in S. We claim the following.(1)
ScheduleS
′ is feasible. First, the completion times of the jobs processed prior to job J
h
A in S
′ are the same as that in S
′. Since the jobs belonging to π are scheduled earlier in S
′, their actual processing times are smaller in S
′, so their completion times are earlier in S
′. It follows that f
k
X
(
C
k
X
(
S
′
)
)
≤
f
k
X
(
C
k
X
(
S
)
) for any job J
k
X in π, where X
∈
{
A
,
B
}, as required.
(2)
ScheduleS
′ is a better schedule than S. By Lemma 1, the completion time of the last job J
l
A in S equals that of the last job J
h
A in S
′; that is, C
l
A
(
S
)
=
C
h
A
(
S
′
)
=
u. Thus, to prove that S
′ is better than S, it suffices to show that
(3)
max
⁡
{
f
l
A
(
C
l
X
(
S
′
)
)
,
f
h
A
(
u
)
}
≤
max
⁡
{
f
h
A
(
C
h
X
(
S
′
)
)
,
f
l
A
(
u
)
}
.
Since f
k
A
(
·
) is a nondecreasing function of the completion time of job J
k
A and C
l
X
(
S
′
)
<
u, we have f
l
A
(
C
l
X
(
S
′
)
)
≤
f
l
A
(
u
). Thus max
⁡
{
f
l
A
(
C
l
X
(
S
′
)
)
,
f
h
A
(
u
)
}
≤
f
l
A
(
u
), as required.
The result follows.Summing up the above analysis, our algorithm for problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
f
max
⁡
A
:
f
max
⁡
B
≤
U can be formally described as in Algorithm 1.Algorithm 1
Input:n
A
,
n
B
,
U, p
A
=
(
p
1
A
,
p
2
A
,
…
,
p
n
A
A
) and p
B
=
(
p
1
B
,
p
2
B
,
…
,
p
n
B
B
).
Step  1. Set h
=
n
B
,
J
=
J
A
,
f
max
⁡
A
=
0 and t
=
(
t
0
-
1
/
k
)
∏
j
=
1
n
X
‍
(
1
-
k
a
j
X
)
+
1
/
k,; solve D
j
B from
f
j
B
(
D
j
B
)
=
U for j
=
1,2
,
…
,
n
B and renumber them according to the non-decreasing
order such that D
[
1
]
B
≤
D
[
2
]
B
≤
⋯
≤
D
[
n
B
]
B;
Step  2. If h
≥
1, then
Ift
≤
D
[
h
]
B, then
seth
=
h
-
1, t
=
(
t
-
a
[
h
]
B
)
/
(
1
-
k
a
[
h
]
B
), assign job J
[
h
]
B at time t, and go to Step  2;
Else
go to Step  3;
Else
go to Step  3;
Step  3. If J
≠
∅, then
select the jobJ
l
A from J with the the smallest cost, that is,  f
l
A
(
t
)
=
min
⁡
J
j
A
∈
J
A
{
f
j
A
(
t
)
},
setf
max
⁡
A
=
max
⁡
{
f
max
⁡
A
,
f
l
A
(
t
)
}, t
=
(
t
-
a
l
A
)
/
(
1
-
k
a
l
A
), assign job J
l
A at time t, delete J
l
A from J,
and go to Step  4;
Elseif h
≥
1
report that the instance is not feasible;
Else
go to Step  4;
Step  4. If J is not empty or h
≥
1, then
go to Step  2.
Else
stop.Theorem 5.
Algorithm1 solves problem 1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
f
max
⁡
A
:
f
max
⁡
B
≤
U in O
(
n
A
2
+
n
B
log
⁡
n
B
) time.Proof.
Step 1 requires a sorting operation of theB-jobs, which takes O
(
n
B
log
⁡
n
B
) time. Step 2 takes O
(
n
B
) time since the calculation of the f
j
B
(
·
) functions in Step 2 can be evaluated in constant time by the assumption. In Step 3 we calculate the f
j
A
(
·
) value for all the remaining unscheduled A-jobs, which takes O
(
n
A
) time. Thus, after n
A iterations, Step 3 can be executed in O
(
n
A
2
) time. Therefore, the overall time complexity of the algorithm is indeed O
(
n
A
2
+
n
B
log
⁡
n
B
).


## 4. Problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
∑
‍
w
j
A
C
j
A
:
f
max
B
≤
U

Leung et al. [30] show that problem 1
|
|
∑
‍
w
j
A
C
j
A
:
f
max
⁡
B
≤
U is NP-hard in the strong sense. Since our problem 1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
∑
‍
w
j
A
C
j
A
:
f
max
⁡
B
≤
U is a generalization of the problem 1
|
|
∑
‍
w
j
A
C
j
A
:
f
max
⁡
B
≤
U, then so is our problem. In what follows we show that the problem 1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
∑
‍
w
j
A
C
j
A
:
f
max
⁡
B
≤
U is polynomially solvable if the A-jobs have reversely agreeable weights; that is,  a
i
A
≤
b
j
A implies w
i
A
≥
w
j
A for all jobs J
i
A and J
j
A. It is clear that Propositions 2 and 3 still hold for this problem. We modify Proposition 4 as follows.Proposition 6.
For the problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
∑
‍
w
j
A
C
j
A
:
f
max
⁡
B
≤
U, if the A-jobs have reversely agreeable weights, then there exists an optimal schedule where the A-jobs are assigned according to the nondecreasing order of a
j
A
/
w
j
A, that is, in the weighted shortest processing time (WSPT) order.Proof.
Assume thatS is an optimal schedule where A-jobs are not scheduled in the WSPT order. Let J
l
A and J
h
A be the first pair of jobs such that a
l
A
/
w
l
A
>
a
h
A
/
w
h
A. Then a
l
A
≥
a
h
A and w
l
A
≤
w
h
A due to the fact that the A-jobs have reversely agreeable weights. Assume that, in schedule S, job J
l
A starts its processing at time T; then a set of B-jobs are consecutively processed and then job J
h
A. In addition, let π
′ denote the set of jobs processed after job J
h
A. We construct a new scheduling S
′ from S by swapping jobs J
l
A and J
h
A and leaving the other jobs unchanged. We conclude the following. (1)
ScheduleS
′ is feasible. By Lemma 1, the completion time of job J
h
A in S equals that of job J
l
A in S
′; that is, C
l
A
(
S
′
)
=
C
h
A
(
S
), so the completion times of the jobs belonging to π
′ are identical in both S and S
′. Since a
l
A
≥
a
h
A, we have C
h
A
(
S
′
)
=
T
+
a
h
A
(
1
-
k
T
)
≤
T
+
a
l
A
(
1
-
k
T
)
=
C
l
A
(
S
). Hence the π-jobs are scheduled earlier in S
′, implying that their actual processing times are smaller in S
′, so their completion times are earlier in S
′. Hence f
k
B
(
C
k
B
(
S
′
)
)
≤
f
k
B
(
C
k
B
(
S
)
) for any job J
k
B in π, as required.
(2)
ScheduleS
′ is better than S. By the proof of (1), it is sufficient to show that
(4)
w
h
A
C
h
A
(
S
′
)
+
w
l
A
C
l
A
(
S
′
)
≤
w
l
A
C
l
A
(
S
)
+
w
h
A
C
h
A
(
S
)
.
Since C
h
A
(
S
′
)
≤
C
l
A
(
S
) and C
l
A
(
S
′
)
=
C
h
A
(
S
), we have
(5)
w
l
A
C
l
A
(
S
)
+
w
h
A
C
h
A
(
S
)
-
(
w
h
A
C
h
A
(
S
′
)
+
w
l
A
C
l
A
(
S
′
)
)
≥
w
l
A
C
h
A
(
S
′
)
+
w
h
A
C
l
A
(
S
′
)
-
(
w
h
A
C
h
A
(
S
′
)
+
w
l
A
C
l
A
(
S
′
)
)
=
(
w
l
A
-
w
h
A
)
(
C
h
A
(
S
′
)
-
C
l
A
(
S
′
)
)
≥
0
,
as required.
Thus, repeating this swapping argument for all theA-jobs not sequenced in the WSPT order yields the theorem.Based on the results of Propositions2, 3, and 6, our algorithm to solve the problem 1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
∑
‍
w
j
A
C
j
A
:
f
max
⁡
B
≤
U for the case where the A-jobs have reversely agreeable weights can be formally described as in Algorithm 2.Algorithm 2
Input:n
A
,
n
B
,
U, w
A
=
(
w
1
A
,
w
2
A
,
…
,
w
n
A
A
), p
A
=
(
p
1
A
,
p
2
A
,
…
,
p
n
A
A
) and p
B
=
(
p
1
B
,
p
2
B
,
…
,
p
n
B
B
).
Step  1. Set t
=
(
t
0
-
1
/
k
)
∏
j
=
1
n
X
‍
(
1
-
k
a
j
X
)
+
1
/
k
,
l
=
n
A
,
h
=
n
B, and ∑
‍
w
j
A
C
j
A
=
0;
sort the A-jobs according to the non-decreasing order of a
j
A
/
w
j
A, that is,
a
[
1
]
A
/
w
[
1
]
A
≤
a
[
2
]
A
/
w
[
2
]
A
≤
⋯
≤
a
[
n
A
]
A
/
w
[
n
A
]
A;
calculate the deadlines of the B-jobs from f
j
B
(
D
j
B
)
=
U and renumber them
according to the non-decreasing order such that D
[
1
]
B
≤
D
[
2
]
B
≤
⋯
≤
D
[
n
B
]
B;
Step  2. If h
≥
1, then
Ift
≤
D
[
h
]
B, then
seth
=
h
-
1, t
=
(
t
-
a
[
h
]
B
)
/
(
1
-
k
a
[
h
]
B
), assign job J
[
h
]
B at time t, and go to Step  2;
Else
go to Step  3;
Else
go to Step  3;
Step  3. If l
≥
1, then
setl
=
l
-
1, ∑
‍
w
j
A
C
j
A
=
∑
‍
w
j
A
C
j
A
+
w
[
l
]
A
t, t
=
(
t
-
a
[
l
]
A
)
/
(
1
-
k
a
[
l
]
A
), assign J
[
l
]
A at time t, and go to Step  4;
Elseif h
≥
1
output that the instance is not feasible;
Else
go to Step  4;
Step  4. If h
≥
1 or l
≥
1, then
go to Step  2.
Else
stop.Theorem 7.
The problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
∑
‍
w
j
C
j
A
:
f
max
⁡
B
≤
U can be solved in O
(
n
A
log
⁡
n
A
+
n
B
log
⁡
n
B
) time by applying Algorithm 2 if all A-jobs have reversely agreeable weights.Proof.
The correctness comes from the above analysis. Now we turn to the time complexity of the algorithm. Step 1 requires two sorting operations of theA-jobs and B-jobs, respectively, which take O
(
n
A
log
⁡
n
A
) time and O
(
n
B
log
⁡
n
B
) time, respectively. Both Steps 2 and 3 take O
(
2
) time. Therefore, the overall time complexity of the algorithm is indeed O
(
n
A
log
⁡
n
A
+
n
B
log
⁡
n
B
).


## 5. Problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
∑
‍
w
j
A
(
1
-
e
-
r
C
j
A
)
:
f
max
B
≤
U

This section address the problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
w
j
A
(
1
-
e
-
r
C
j
A
)
:
f
max
⁡
B
≤
U. We show that it is polynomially solvable if the A-jobs have reversely agreeable weights. It is clear that Propositions 2 and 3 still hold for this problem. We give Proposition 8 as follows.Proposition 8.
For the problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
w
j
A
(
1
-
e
-
r
C
j
A
)
:
f
max
⁡
B
≤
U, if the A-jobs have reversely agreeable weights, then there exists an optimal schedule where the A-jobs are assigned according to the nondecreasing order of (
1
-
e
-
r
a
j
A
)
/
w
j
A
e
-
r
a
j
A, that is, in the weighted discount shortest processing time (WDSPT) order.Proof.
We adopt the same notation as that used in the proof of Proposition6. Assume that (
1
-
e
-
r
a
l
A
)
/
w
l
A
e
-
r
a
l
A
>
(
1
-
e
-
r
p
h
A
)
/
w
h
A
e
-
r
p
h
A. Since A-jobs have reversely agreeable weights, we have a
l
A
≥
a
h
A and w
l
A
≤
w
h
A. Then by the proof of Proposition 6,  we know that C
h
A
(
S
′
)
≤
C
l
A
(
S
), C
l
A
(
S
′
)
=
C
h
A
(
S
), and C
k
A
(
S
′
)
=
C
j
A
(
S
) for all the other jobs J
k
A
∈
J
A
/
{
J
l
A
,
J
k
A
} and that schedule S
′ is feasible. To show that S
′ is better than S, it is sufficient to show that
(6)
w
h
A
(
1
-
e
-
r
C
h
A
(
S
′
)
)
+
w
l
A
(
1
-
e
-
r
C
l
A
(
S
′
)
)
≤
w
l
A
(
1
-
e
-
r
C
l
A
(
S
)
)
+
w
h
A
(
1
-
e
-
r
C
h
A
(
S
)
)
.
In fact, since r
∈
(
0,1
), C
h
A
(
S
′
)
≤
C
l
A
(
S
), and C
l
A
(
S
′
)
=
C
h
A
(
S
), we have
(7)
w
l
A
(
1
-
e
-
r
C
l
A
(
S
)
)
+
w
h
A
(
1
-
e
-
r
C
h
A
(
S
)
)
-
(
w
h
A
(
1
-
e
-
r
C
h
A
(
S
′
)
)
+
w
l
A
(
1
-
e
-
r
C
l
A
(
S
′
)
)
)
=
w
h
A
e
-
r
C
h
A
(
S
′
)
+
w
l
A
e
-
r
C
l
A
(
S
′
)
-
w
l
A
e
-
r
C
l
A
(
S
)
-
w
h
A
e
-
r
C
h
A
(
S
)
≥
w
h
A
e
-
r
C
h
A
(
S
′
)
+
w
l
A
e
-
r
C
h
A
(
S
′
)
-
w
l
A
e
-
r
C
h
A
(
S
′
)
-
w
h
A
e
-
r
C
l
A
(
S
′
)
=
(
w
h
A
-
w
l
A
)
(
e
-
r
C
h
A
(
S
′
)
-
e
-
r
C
l
A
(
S
′
)
)
≥
0
.
Hence, w
h
A
(
1
-
e
-
r
C
h
A
(
S
′
)
)
+
w
l
A
(
1
-
e
-
r
C
l
A
(
S
′
)
)
≤
w
l
A
(
1
-
e
-
r
C
l
A
(
S
)
)
+
w
h
A
(
1
-
e
-
r
C
h
A
(
S
)
). Therefore, S
′ is not worse than S. Thus, repeating this swapping argument for all the A-jobs not sequenced in the WDSPT order yields the theorem.Based on the above analysis, our algorithm to solve the problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
∑
‍
w
j
A
(
1
-
e
-
r
C
j
A
)
:
f
max
⁡
B
≤
U for the case where the A-jobs have reversely agreeable weights can be described as in Algorithm 3.Algorithm 3
Input:n
A
,
n
B
,
U
,
r, w
A
=
(
w
1
A
,
w
2
A
,
…
,
w
n
A
A
), p
A
=
(
p
1
A
,
p
2
A
,
…
,
p
n
A
A
) and p
B
=
(
p
1
B
,
p
2
B
,
…
,
p
n
B
B
).
Step  1. Set t
=
(
t
0
-
1
/
k
)
∏
j
=
1
n
X
‍
(
1
-
k
a
j
X
)
+
1
/
k
,
l
=
n
A
,
h
=
n
B, and ∑
‍
w
j
A
(
1
-
e
-
r
C
j
A
)
=
0;
sort the A-jobs in non-decreasing order of (
1
-
e
-
r
a
j
A
)
/
(
w
j
A
e
-
r
a
j
A
),
that is, (
1
-
e
-
r
a
[
1
]
A
)
/
(
w
[
1
]
A
e
-
r
a
[
1
]
A
)
≤
(
1
-
e
-
r
a
[
2
]
A
)
/
(
w
[
2
]
A
e
-
r
a
[
2
]
A
)
≤
⋯
≤
(
1
-
e
-
r
a
[
n
A
]
A
)
/
(
w
[
n
A
]
A
e
-
r
a
[
n
A
]
A
);
calculate the deadlines of the B-jobs from f
j
B
(
D
j
B
)
=
U and
renumber them according to the non-decreasing order, that is, D
[
1
]
B
≤
D
[
2
]
B
≤
⋯
≤
D
[
n
B
]
B;
Step  2. If h
≥
1, then
Ift
≤
D
[
h
]
B, then
seth
=
h
-
1, t
=
(
t
-
a
[
h
]
B
)
/
(
1
-
k
a
[
h
]
B
), assign J
[
h
]
B at time t, and go to Step  2;
Else
go to Step  3;
Else
go to Step  3;
Step  3. If l
≥
1, then
setl
=
l
-
1, ∑
‍
w
j
A
(
1
-
e
-
r
C
j
A
)
=
∑
‍
w
j
A
(
1
-
e
-
r
C
j
A
)
+
w
[
l
]
A
(
1
-
e
-
r
t
), t
=
(
t
-
a
[
l
]
A
)
/
(
1
-
k
a
[
l
]
A
),
assignJ
[
l
]
A at time t, and go to Step  4;
Elseif h
≥
1
output that the instance is not feasible;
Else
go to Step  4;
Step  4. If h
≥
1 or l
≥
1, then
go to Step  2.
Else
stop.Theorem 9.
The problem1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
∑
‍
w
j
A
(
1
-
e
-
r
C
j
A
)
:
f
max
⁡
B
≤
U can be solved in O
(
n
A
log
⁡
n
A
+
n
B
log
⁡
n
B
) time by applying Algorithm 3 for the case that the A-jobs have reversely agreeable weights.Proof.
The proof is analogous to that of Theorem7.


## 6. Conclusions

This paper introduced a new scheduling model on a single machine that involves two agents and learning effects simultaneously. We studied the problem of finding an optimal schedule for agentA, subject to the constraint that the maximum cost of agent B does not exceed a given value. We derived the optimal structural properties of optimal schedules and provided polynomial time algorithms for the problem 1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
f
max
⁡
A
:
f
max
⁡
B
≤
U. We also showed that the problems 1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
∑
‍
w
j
C
j
A
:
f
max
⁡
B
≤
U and 1
∣
p
j
X
=
a
j
X
(
1
-
k
t
)
∣
∑
‍
w
j
A
(
1
-
e
-
r
C
j
A
)
:
f
max
⁡
B
≤
U can also be solved in polynomial time under certain agreeable conditions. Future research may consider the scheduling model with more than two agents.



---

*Source: 471016-2014-05-25.xml*