# Single Machine Scheduling and Due Date Assignment with Past-Sequence-Dependent Setup Time and Position-Dependent Processing Time

Authors: Chuan-Li Zhao; Chou-Jung Hsu; Hua-Feng Hsu
Journal: The Scientific World Journal
 (2014)

---

## Abstract

This paper considers single machine scheduling and due date assignment with setup time. The setup time is proportional to the length of the already processed jobs; that is, the setup time is past-sequence-dependent (p-s-d). It is assumed that a job's processing time depends on its position in a sequence. The objective functions include total earliness, the weighted number of tardy jobs, and the cost of due date assignment. We analyze these problems with two different due date assignment methods. We first consider the model with job-dependent position effects. For each case, by converting the problem to a series of assignment problems, we proved that the problems can be solved inO
n
4 time. For the model with job-independent position effects, we proved that the problems can be solved in O
n
3 time by providing a dynamic programming algorithm.


---

## Body

## 1. Introduction

In many realistic scheduling environments, a job’s processing time may be depending on its position in the sequence [1]. Two well-known special cases of this stream of research are (i)positional deterioration (aging effect), where the processing time of a job increases as a function of its position in a processing sequence and (ii)learning effect, where the processing time of a job decreases as a function of its position in a processing sequence. Biskup [2] and Cheng and Wang [3] independently introduced the learning concept to scheduling research. Other studies include Mosheiov and Sidney [4], Mosheiov [5, 6], Wu et al. [7, 8], and Yin et al. [9, 10]. Biskup [11] presented an updated survey of the results on scheduling problems with the learning effect. Mosheiov [6] first mentioned theaging effectin scheduling research. Other studies include Mosheiov [12], Kuo and Yang [13], Janiak and Rudek [14], Zhao and Tang [15], and Rustogi and Strusevich [16], among others. Moreover, some studies consider scheduling problems with general position-dependent processing time. Mosheiov [17] considered a scheduling problem with general position-dependent processing time. The polynomial algorithm is derived for makespan minimization on an m-machine proportionate flow shop. Zhao et al. [18] studied scheduling and due date assignment problem. They provided a unified model for solving the single machine problems with rejection and position-dependent processing time. Rustogi and Strusevich [19] presented a critical review of the known results for scheduling models with various positional effects.Koulamas and Kyparisis [20] first introduced a scheduling problem with past-sequence-dependent (p-s-d) setup time. They assumed that the job setup time is proportional to the sum of processing time of all already scheduled jobs. It is proved that the standard single machine scheduling with p-s-d setup time can be solvable in polynomial time when the objectives are the makespan, the total completion time, and the total absolute differences in completion time, respectively. Wang [21] studied the single machine scheduling problems with time-dependent learning effect and p-s-d setup time considerations. He showed that the makespan minimization problem, the total completion time minimization problem, and the sum of the quadratic job completion time minimization problem can be solved in polynomial time, respectively. Yin et al. [22] considered a single machine scheduling model with p-s-d setup time and a general learning effect. They showed that the single machine scheduling problems to minimize the makespan and the sum of thekth power of completion time are polynomially solvable under the proposed model. Hsu et al. [23] presented a polynomial-time algorithm for an unrelated parallel machine scheduling problem with setup time and learning effects to minimize the total completion time. Lee [24] proposed a model with the deteriorating jobs, the learning effect, and the p-s-d setup time. He provided the optimal schedules for some single machine problems. Huang et al. [25] considered some single machine scheduling problems with general time-dependent deterioration, position-dependent learning, and p-s-d setup time. They proved that the makespan minimization problem, the total completion time minimization problem, and the sum of the μth power of job completion time minimization problem can be solved by the SPT rule.Meeting due dates is one of the most important objectives in scheduling (Gordon et al. [26]). In some situations, the tardiness penalties depend on whether the jobs are tardy, rather than how late they are. In these cases, the number of tardy jobs should be minimized (Yin et al. [27]). Kahlbacher and Cheng [28] considered scheduling problems to minimize costs for earliness, due date assignment, and weighted number of tardy jobs. They presented nearly a full classification for the single and multiple machine models. Shabtay and Steiner [29] studied two single machine scheduling problems. The objectives are to minimize the sum of weighted earliness, tardiness, and due date assignment penalties and minimize the weighted number of tardy jobs and due date assignment costs, respectively. They proved that both problems are strongly NP-hard and give polynomial solutions for some important special cases. Koulamas [30] considered the second problem of Shabtay and Steiner [29]. He presented a faster algorithm for a due date assignment problem with tardy jobs. Gordon and Strusevich [31] addressed the problems of single machine scheduling and due date assignment problems in which a job’s processing time depends on its position in a processing sequence. The objective functions include the cost of the due dates, the total cost of discarded jobs that cannot be completed by their due dates, and the total earliness of the scheduled jobs. They presented polynomial-time dynamic programming algorithms for solving problems with two due date assignment methods, provided that the processing time of the jobs is positionally deteriorating. Hsu et al. [32] extended part of the objective functions proposed by Gordon and Strusevich [31] to the positional weighted earliness penalty and showed that the problems remain solvable in polynomial time.


## 2. Problem Formulation and Preliminaries

This paper studies the single machine scheduling problems with simultaneous consideration of due date assignment, p-s-d setup time, and position-dependent processing time.The problem can be described as follows.A setN
=
{
J
1
,
J
2
,
…
,
J
n
} of n jobs has to be scheduled on a single machine. All jobs are available for processing at time zero and preemption is not permitted. Each job J
j has a basic processing time p
j. The actual processing time of job J
j, if scheduled in position r of a sequence, is given by
(1)
p
j
A
=
g
(
j
,
r
)
p
j
,
where g
(
j
,
1
), g
(
j
,
2
)
,
…
,
g
(
j
,
n
) represent an array of job-dependent positional factors.Each jobJ
j
∈
N has to be assigned a due date d
j, by which it is desirable to complete that job. Given a schedule, denote the completion time of job J
j by C
j. Job J
j is called tardy if C
j
>
d
j, and it is called nontardy if C
j
≤
d
j. Let U
j
=
1 if job J
j is tardy and let U
j
=
0 if job J
j is nontardy. The earliness of J
j is defined as E
j
=
d
j
-
C
j, provided that C
j
≤
d
j. In all problems considered in this paper, the jobs in set N have to be split into two subsets denoted by N
E and N
T. We refer to the jobs in set N
E as “nontardy,” while the jobs in set N
T are termed “tardy.” A penalty β
j is paid for the tardy job J
j
∈
N
T. Given a schedule π
=
[
J
[
i
]
,
J
[
2
]
,
…
,
J
[
n
]
], we assumed that the p-s-d setup time of J
[
j
] is given as Koulamas and Kyparisis [20] did, as follows:
(2)
s
[
j
]
=
δ
∑
i
=
1
j
-
1
p
[
i
]
A
,
j
=
2,3
,
…
,
n
,
s
[
1
]
=
0
,
where δ
≥
0 is a normalizing constant.The purpose is to determine the optimal due dates and the processing sequence such that the following function is minimized:(3)
F
(
d
,
π
)
=
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
φ
(
d
)
,
where π is the sequence of jobs, α is the positive unit earliness cost, d is the vector of the assigned due dates, and φ
(
d
) denotes the cost of assigning the due dates that depends on a specific rule chosen for due date assignment. We denote the problem as
(4)
1
|
p
j
A
=
p
j
g
(
j
,
r
)
,
S
psd
|
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
φ
(
d
)
.Most of the presented results hold for a general positional effect, that is, for any functiong
(
j
,
r
) that depends on both position r and job J
j. For each individual model, there is a particular rule that defines g
(
j
,
r
) and explains how exactly the value of p
j changes, for example.(i) Job-Dependent Learning Effect (Mosheiov and Sidney [4]). The actual processing time of a job J
j, if scheduled in position r of a sequence, is given by
(5)
p
j
A
=
p
j
r
a
j
,
where a
j
≤
0 is a job-dependent learning parameter (include a
j
=
a as a special case, i.e., p
j
A
=
p
j
r
a, Biskup [2]).(ii) Job-Dependent Aging Effect (Zhao and Tang [15]). The actual processing time of a job j, if scheduled in position r of a sequence, is given by
(6)
p
j
A
=
p
j
r
a
j
,
where a
j
≥
0 is a job-dependent aging parameter (include a
j
=
a as a special case, i.e., p
j
A
=
p
j
r
a, Moshieov [17]).(iii) Positional Exponential Deterioration (Wang [33]). The actual processing time of a job j, if scheduled in position r of a sequence, is given by
(7)
p
j
A
=
p
j
a
r
-
1
,
where a
≥
1 is a given positive constant representing a rate of deterioration, which is common for all jobs.We study our problem with the two most frequently used due date assignment methods.(i) The Common Due Date Assignment Method(usually referred to asCON). Where all jobs are assigned the same due date, such that is d
j
=
d for j
=
1,2
,
…
,
n and d
≥
0 is a decision variable.(ii) The Slack Due Date Assignment Method(usually referred to asSLK). Where all jobs are given an equal flow allowance that reflects equal waiting time (i.e., equal slacks), such that is  d
j
=
p
j
A
+
q for j
=
1,2
,
…
,
n and q
≥
0 is a decision variable.We first provide some lemmas.Lemma 1 (Hardy et al. [34]).
Let there be two sequences of numbersx
i and y
i (i
=
1,2
,
…
,
n). The sum ∑
i
=
1
n
x
i
y
i of products of the corresponding elements is the least if the sequences are monotonically ordered in the opposite sense.It is not difficult to see that the following property is valid for both the variants of our problem.Lemma 2.
There exists an optimal schedule in which the following properties hold: (1) all the jobs are processed consecutively without idle time and the first job starts at time 0 for both the variants of the problem; (2) all the nontardy jobs are processed before all the tardy jobs for both the variants of the problem.


## 3. TheCONDue Date Assignment Method

In theCON model, d
j
=
d (j
=
1,2
,
…
,
n). We choose γ
d as the cost function φ
(
d
), where γ is a positive constant. Thus, it follows from function (3) that our problem is to minimize the objective function:
(8)
F
(
d
,
π
)
=
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
γ
d
.The problem denotes(9)
1
|
p
j
A
=
p
j
g
(
j
,
r
)
,
S
psd
,
C
O
N
|
α
∑
J
j
∈
N
E
E
j
+
α
∑
J
j
∈
N
T
β
j
U
j
+
γ
d
.Kahlbacher and Cheng [28] provide an O
(
n
4
) time algorithm for the problem 1
|
C
O
N
|
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
γ
d. In this section, we consider a generalization of the basic model with p-s-d setup times and position-dependent processing times. As a result of Lemma 2, we can restrict our attention to those schedules without idle times and search for the optimal schedule only among the schedules in which one of the jobs is on time.Letπ
=
[
J
[
i
]
,
J
[
2
]
,
…
,
J
[
n
]
]; then
(10)
C
[
1
]
=
g
(
[
1
]
,
1
)
p
[
1
]
,
C
[
2
]
=
C
[
1
]
+
s
[
2
]
+
g
(
[
2
]
,
2
)
p
[
2
]
m
i
k
=
g
(
[
1
]
,
1
)
p
[
1
]
+
δ
g
(
[
1
]
,
1
)
p
[
1
]
+
g
(
[
2
]
,
2
)
p
[
2
]
m
i
k
=
∑
k
=
1
2
[
1
+
(
2
-
k
)
δ
]
g
(
[
k
]
,
k
)
p
[
k
]
,
m
i
m
⋮
C
[
j
]
=
∑
k
=
1
j
[
1
+
(
j
-
k
)
δ
]
g
(
[
k
]
,
k
)
p
[
k
]
,
m
i
m
⋮
C
[
n
]
=
∑
k
=
1
n
[
1
+
(
n
-
k
)
δ
]
g
(
[
k
]
,
k
)
p
[
k
]
.
∑
j
=
1
n
C
[
j
]
=
∑
j
=
1
n
(
n
-
j
+
1
)
(
1
+
δ
(
n
-
j
)
2
)
g
(
[
j
]
,
j
)
p
[
j
]
.Note that we need only to consider the schedule in which all the nontardy jobs are processed before all the tardy jobs.Lemma 3.
For the problem(11)
1
|
p
j
A
=
p
j
g
(
j
,
r
)
,
S
p
s
d
,
C
O
N
|
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
γ
d
,
if the number of jobs in N
E is h (denote |
N
E
|
=
h), there exists an optimal schedule π
=
[
J
[
1
]
,
J
[
2
]
,
…
,
J
[
n
]
], such that d
=
C
[
h
].Proof.
Supposeπ
=
[
J
[
i
]
,
J
[
2
]
,
…
,
J
[
n
]
] is an optimal schedule. Since jobs J
[
i
]
,
J
[
2
]
,
…
,
J
[
h
] are nontardy, then d
≥
C
[
h
]. Let Δ
=
d
-
C
[
h
]. Moving the due date Δ units of time to the left such that d
=
C
[
h
], the objective value will be decreasing (
α
j
+
γ
)
Δ, which is nonnegative. This means we can find a schedule with d
=
C
[
h
] that is at least as good as π.As a consequence of Lemma3, we consider the schedule π
=
[
J
[
i
]
,
J
[
2
]
,
…
,
J
[
n
]
] with d
=
C
[
h
].Thus,(12)
F
(
d
,
π
)
=
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
γ
d
=
α
∑
j
=
1
h
E
[
j
]
+
∑
j
=
h
+
1
n
β
[
j
]
+
γ
d
=
α
∑
j
=
1
h
[
C
[
h
]
-
C
[
j
]
]
+
∑
j
=
h
+
1
n
β
[
j
]
+
γ
C
[
h
]
=
(
α
h
+
γ
)
(
∑
j
=
1
h
[
1
+
(
h
-
j
)
δ
]
g
(
[
j
]
,
j
)
p
[
j
]
)
-
α
∑
j
=
1
h
(
h
-
j
+
1
)
(
1
+
1
2
δ
(
h
-
j
)
)
g
(
[
j
]
,
j
)
p
[
j
]
+
∑
j
=
h
+
1
n
β
[
j
]
=
∑
j
=
1
h
{
α
(
j
-
1
)
+
1
2
α
δ
(
h
-
j
)
(
h
+
j
-
1
)
mmm
1
2
+
[
1
+
δ
(
h
-
j
)
]
γ
}
g
(
[
j
]
,
j
)
p
[
j
]
+
∑
j
=
h
+
1
n
β
[
j
]
=
∑
j
=
1
h
w
j
g
(
[
j
]
,
j
)
p
[
j
]
+
∑
j
=
h
+
1
n
β
[
j
]
,
where
(13)
w
j
=
{
α
(
j
-
1
)
+
1
2
α
δ
(
h
-
j
)
(
h
+
j
-
1
)
1
2
mk
+
[
1
+
δ
(
h
-
j
)
]
γ
}
,
j
=
1,2
,
…
,
h
.Letx
j
,
r be a binary variable such that x
j
,
r
=
1 if job J
j is scheduled in therth position and x
j
,
r
=
0; otherwise, j
,
r
=
1,2
,
…
,
n. From  (12), we can formulate the problem with objective (8) as the following assignment problemA1(h), which can be solved in O
(
n
3
) time:
(14)
Min
⁡
∑
j
=
1
n
∑
r
=
1
n
c
j
,
r
x
j
,
r
i
s
.
t
.
k
∑
r
=
1
n
x
j
,
r
=
1
,
j
=
1,2
,
…
,
n
,
m
m
k
m
∑
j
=
1
n
x
j
,
r
=
1
,
r
=
1,2
,
…
,
n
,
m
m
k
m
x
j
,
r
∈
{
0,1
}
,
j
=
1,2
,
…
,
n
,
r
=
1,2
,
…
,
n
,
where
(15)
c
j
,
r
=
{
w
r
g
(
j
,
r
)
p
j
for
r
=
1,2
,
…
,
h
β
j
for
r
=
h
+
1
,
h
+
2
,
…
,
n
,
w
r
=
{
α
(
r
-
1
)
+
1
2
α
δ
(
h
-
r
)
(
h
+
r
-
1
)
m
k
1
2
+
[
1
+
δ
(
h
-
r
)
]
γ
}
,
r
=
1,2
,
…
,
h
.Note thatc
j
,
r is the cost of assigning job J
j (j
=
1,2
,
…
,
n) in therth (r
=
1,2
,
…
,
n) position in the schedule.In order to derive the optimal solution, we have to solve the above assignment problemA1(h) for any h
=
1,2
,
…
,
n. We summarize the results of the above analysis and present the following solution algorithm.Algorithm 4.
Step
1. For h
=
0 (d
=
0, all the jobs are tardy), calculate F
(
0
)
=
∑
j
=
1
n
β
j.
Step
2. For h from 1 to n, solve the assignment problemA1(h) and calculate the corresponding objective value F
(
h
).
Step
3. The optimal value of the function F is equal to min
⁡
{
F
(
h
)
∣
h
=
0,1
,
2
,
…
,
n
}.
As a result, we obtain the following theorem.Theorem 5.
Problem1
|
p
j
A
=
p
j
g
(
j
,
r
)
,
S
p
s
d
,
C
O
N
|
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
γ
d can be solved in O
(
n
4
) time.We demonstrate our approach using the following example.Example 6.
Consider the problem1
|
p
j
A
=
p
j
g
(
j
,
r
)
,
S
psd
,
C
O
N
|
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
γ
d.
Letn
=
5, h
=
3. The weights are α
=
1, γ
=
2, and δ
=
0.1.
The processing times arep
1
=
7, p
2
=
6, p
3
=
5, p
4
=
2, and p
5
=
1.
The tardy penalties areβ
1
=
10, β
2
=
8, β
3
=
4, β
4
=
5, and β
5
=
6.
The positional effects are(16)
g
(
j
,
r
)
=
[
2
1
3
2
4
1
3
2
2
3
2
3
1
4
3
1
2
3
1
3
2
1
2
3
4
]
,
w
1
=
2.7
,
w
2
=
3.4
,
w
3
=
4
.
The assignment problemA1(3) is
(17)
Min
⁡
∑
j
=
1
n
∑
r
=
1
n
c
j
,
r
x
j
,
r
i
s
.
t
.
k
∑
r
=
1
n
x
j
,
r
=
1
,
j
=
1,2
,
…
,
n
,
m
m
k
m
∑
j
=
1
n
x
j
,
r
=
1
,
r
=
1,2
,
…
,
n
,
m
m
k
m
x
j
,
r
∈
{
0,1
}
,
j
=
1,2
,
…
,
n
,
r
=
1,2
,
…
,
n
,
where
(18)
c
j
,
r
=
[
w
1
g
(
1,1
)
p
1
w
2
g
(
1,2
)
p
1
w
3
g
(
1,3
)
p
1
β
1
β
1
w
1
g
(
2,1
)
p
2
w
2
g
(
2,2
)
p
2
w
3
g
(
2,3
)
p
2
β
2
β
2
w
1
g
(
3,1
)
p
3
w
2
g
(
3,2
)
p
3
w
3
g
(
3,3
)
p
3
β
3
β
3
w
1
g
(
4,1
)
p
4
w
2
g
(
4,2
)
p
4
w
3
g
(
4,3
)
p
4
β
4
β
4
w
1
g
(
5,1
)
p
5
w
2
g
(
5,2
)
p
5
w
3
g
(
5,3
)
p
5
β
5
β
5
]
=
[
37.8
23.8
84
10
10
16.2
61.2
48
8
8
27
51
20
4
4
5.4
13.6
24
5
5
5.4
3.4
8
6
6
]
.
The solution is(19)
x
j
,
r
=
[
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
]
.
The optimal sequence isπ
*
=
[
J
4
,
J
5
,
J
3
,
J
1
,
J
2
], d
*
=
8.5. The total cost is 46.8.


## 4. TheSLKDue Date Assignment Method

In theSLK model, d
j
=
p
j
A
+
q   (j
=
1,2
,
…
,
n). We choose γ
q as the cost function φ
(
d
), where γ is a positive constant. Thus, it follows from function (3) that our problem is to minimize the objective function
(20)
F
(
d
,
π
)
=
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
γ
q
.
The problem denotes 1
|
p
j
A
=
p
j
g
(
j
,
r
)
,
S
psd
,
S
L
K
|
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
γ
q.Similar to theCON model, if the number of jobs in N
E is given, we have the following solution.Lemma 7.
For the problem1
|
p
j
A
=
p
j
g
(
j
,
r
)
,
S
p
s
d
,
S
L
K
|
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
γ
q, if |
N
E
|
=
h, there exists an optimal schedule π
=
[
J
[
1
]
,
J
[
2
]
,
…
,
J
[
n
]
], such that the slack time q
=
C
[
h
-
1
]
+
S
[
h
].Proof.
The proof is similar to that of Lemma3.
Letπ
=
[
J
[
1
]
,
J
[
2
]
,
…
,
J
[
n
]
], q
=
C
[
h
-
1
]
+
S
[
h
]. Thus,
(21)
q
=
∑
j
=
1
h
-
1
[
1
+
(
h
-
j
-
1
)
δ
]
g
(
[
j
]
,
j
)
p
[
j
]
+
δ
∑
j
=
1
h
-
1
g
(
[
j
]
,
j
)
p
[
j
]
=
∑
j
=
1
h
-
1
[
1
+
(
h
-
j
)
δ
]
g
(
[
j
]
,
j
)
p
[
j
]
,
E
[
j
]
=
d
[
j
]
-
C
[
j
]
=
g
(
[
j
]
,
j
)
p
[
j
]
+
q
-
C
[
j
]
=
g
(
[
j
]
,
j
)
p
[
j
]
+
∑
k
=
1
h
-
1
[
1
+
(
h
-
k
)
δ
]
g
(
[
k
]
,
k
)
p
[
k
]
-
∑
k
=
1
j
[
1
+
(
h
-
k
)
δ
]
g
(
[
k
]
,
k
)
p
[
k
]
=
g
(
[
j
]
,
j
)
p
[
j
]
+
∑
k
=
j
+
1
h
-
1
[
1
+
(
h
-
k
)
δ
]
g
(
[
k
]
,
k
)
p
[
k
]
,
mmmmmmmmmmmmmmmmkmm
1
≤
j
≤
h
-
1
.
Consequently,
(22)
∑
j
=
1
h
-
1
E
[
j
]
=
∑
j
=
1
h
-
1
{
∑
k
=
j
+
1
h
-
1
[
1
+
(
h
-
k
)
δ
]
g
(
[
k
]
,
k
)
p
[
k
]
}
g
(
[
j
]
,
j
)
p
[
j
]
m
m
m
m
+
∑
k
=
j
+
1
h
-
1
[
1
+
(
h
-
k
)
δ
]
g
(
[
k
]
,
k
)
p
[
k
]
}
=
∑
j
=
1
h
-
1
g
(
[
j
]
,
j
)
p
[
j
]
+
∑
j
=
2
h
-
1
(
j
-
1
)
[
1
+
(
h
-
j
)
δ
]
g
(
[
j
]
,
j
)
p
[
j
]
.
Therefore,
(23)
F
(
d
,
π
,
h
)
=
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
γ
q
=
α
∑
j
=
1
h
-
1
g
(
[
j
]
,
j
)
p
[
j
]
+
α
∑
j
=
2
h
-
1
(
j
-
1
)
[
1
+
(
h
-
j
)
δ
]
g
(
[
j
]
,
j
)
p
[
j
]
+
∑
j
=
h
+
1
n
β
[
j
]
+
γ
q
=
α
∑
j
=
1
h
-
1
g
(
[
j
]
,
j
)
p
[
j
]
+
α
∑
j
=
2
h
-
1
(
j
-
1
)
[
1
+
(
h
-
j
)
δ
]
g
(
[
j
]
,
j
)
p
[
j
]
+
∑
j
=
h
+
1
n
β
[
j
]
+
γ
∑
j
=
1
h
-
1
[
1
+
(
h
-
j
)
δ
]
g
(
[
j
]
,
j
)
p
[
j
]
=
∑
j
=
1
h
w
j
g
(
[
j
]
,
j
)
p
[
j
]
+
∑
j
=
h
+
1
n
β
[
j
]
,
where
(24)
w
j
=
{
α
+
γ
(
1
+
(
h
-
j
)
δ
)
for
j
=
1
,
α
+
[
α
(
j
-
1
)
+
γ
]
[
1
+
δ
(
h
-
j
)
]
for
j
=
2
,
…
,
h
-
1
,
0
for
j
=
h
.Since the objective functions forCON andSLK due date assignment methods have the same structure, we have the following solution.Letx
j
,
r be a binary variable such that x
j
,
r
=
1 if job J
j is scheduled in therth position and x
j
,
r
=
0; otherwise, j
,
r
=
1,2
,
…
,
n. If |
N
E
|
=
h, then we can formulate the problem with objective (20) as the following assignment problemA2(h), which can be solved in O
(
n
3
) time:
(25)
Min
⁡
∑
j
=
1
n
∑
r
=
1
n
c
j
,
r
x
j
,
r
i
s
.
t
.
∑
r
=
1
n
x
j
,
r
=
1
,
j
=
1,2
,
…
,
n
,
m
m
m
k
∑
j
=
1
n
x
j
,
r
=
1
,
r
=
1,2
,
…
,
n
,
m
m
m
k
x
j
,
r
∈
{
0,1
}
,
j
=
1,2
,
…
,
n
,
r
=
1,2
,
…
,
n
,
where
(26)
c
j
,
r
=
{
w
r
g
(
j
,
r
)
p
j
for
r
=
1,2
,
…
,
h
,
β
j
for
r
=
h
+
1
,
h
+
2
,
…
,
n
,
w
r
=
{
α
+
γ
(
1
+
(
h
-
r
)
δ
)
for
r
=
1
,
α
+
[
α
(
r
-
1
)
+
γ
]
[
1
+
δ
(
h
-
r
)
]
for
r
=
2
,
…
,
h
-
1
,
0
for
r
=
h
.In order to derive the optimal solution, we have to solve the above assignment problemA2(h) for any h
=
1,2
,
…
,
n.As a result, we obtain the following theorem.Theorem 8.
The problem1
|
p
j
A
=
p
j
g
(
j
,
r
)
,
S
p
s
d
,
S
L
K
|
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
γ
d can be solved in O
(
n
4
) time.


## 5. Job-Independent Position Effects Case

In this section, we explore the model with job-independent position effects; that is, the actual processing time of jobJ
j, if scheduled in position r of a sequence, is given by p
j
A
=
p
j
g
(
r
), where g
(
1
)
,
g
(
2
)
,
…
,
g
(
n
) represent an array of job-independent positional factors. In Section 4, we have shown that the general version (job-dependent position effects) can be solved in O
(
n
4
) time. In the following, we present an O
(
n
3
) time dynamic programming algorithm for solving the special version with job-independent position effects. The main idea that will be used in the development of our algorithm is similar to that of Shabtay et al. [35].Based on the properties proved in Section4, we have the following solutions.For theCON model, if |
N
E
|
=
h, π
=
[
J
[
1
]
,
J
[
2
]
,
…
,
J
[
n
]
], and d
=
C
[
h
], then
(27)
F
(
d
,
π
,
h
)
=
∑
j
=
1
h
{
α
(
j
-
1
)
+
1
2
α
δ
(
h
-
j
)
(
h
+
j
-
1
)
m
m
m
1
2
+
[
1
+
δ
(
h
-
j
)
]
γ
}
g
(
j
)
p
[
j
]
+
∑
j
=
h
+
1
n
β
[
j
]
=
∑
j
=
1
h
w
-
j
g
(
j
)
p
[
j
]
+
∑
j
=
h
+
1
n
β
[
j
]
,
where
(28)
w
-
j
=
{
α
(
j
-
1
)
+
1
2
α
δ
(
h
-
j
)
(
h
+
j
-
1
)
m
k
1
2
+
[
1
+
δ
(
h
-
j
)
]
γ
}
,
j
=
1,2
,
…
,
h
.For theSLK model, if |
N
E
|
=
h, π
=
[
J
[
1
]
,
J
[
2
]
,
…
,
J
[
n
]
], and d
=
C
[
h
-
1
]
+
S
[
h
], then
(29)
F
(
d
,
π
,
h
)
=
[
α
+
γ
(
1
+
(
h
-
j
)
δ
)
]
g
(
1
)
p
[
1
]
+
∑
j
=
2
h
-
1
{
α
+
[
α
(
j
-
1
)
+
γ
]
[
1
+
δ
(
h
-
j
)
]
}
mmmm
×
g
(
j
)
p
[
j
]
+
∑
j
=
h
+
1
n
β
[
j
]
=
∑
j
=
1
h
w
-
j
g
(
j
)
p
[
j
]
+
∑
j
=
h
+
1
n
β
[
j
]
,
where
(30)
w
-
j
=
{
α
+
γ
(
1
+
(
h
-
j
)
δ
)
for
j
=
1
,
α
+
[
α
(
j
-
1
)
+
γ
]
[
1
+
δ
(
h
-
j
)
]
for
j
=
2
,
…
,
h
-
1
,
0
for
j
=
h
.Using (27) and (29), and with any of the two previously mentioned due date assignments methods, let w
j
=
w
-
j
g
(
j
); the objective function can be formulated as F
(
d
,
π
)
=
∑
j
=
1
n
w
j
p
π
(
j
) for the special case of N
E
=
N, where no jobs are tardy. From Lemma 1, the optimal job sequence is obtained by matching the largest w
j value to the job with the smallest p
j value, the second largest w
j value to the job with the second smallest p
j value, and so on. The index of the w
j matched with p
j specifies the position of job j in the optimal sequence. For example, first renumber the jobs in the LPT order such that p
1
≥
p
2
≥
⋯
≥
p
n, and then reorder the positional weights such that w
i
1
≤
w
i
2
≤
⋯
≤
w
i
n  (i
1
,
i
2
,
…
,
i
n is a permutation of 1,2
,
…
,
n), schedules job j in the position i
j
(
j
=
1,2
,
…
,
n
).We now consider the due date assignment problem to minimize the objective function (3). Since the objective functions for all two due date assignment methods have the same structure, we provide a generic algorithm to solve these problems with two due date assignment methods. If set N
E is given, (|
N
E
|
=
h), then we can reorder the positional weights such that w
i
1
≤
w
i
2
≤
⋯
≤
w
i
h. Thus, an optimal job sequence of N
E is obtained in O
(
h
log
⁡
h
) time. However, in order to find the optimal solution for the due date assignment problem, the contribution of the total cost of the tardy jobs must be taken into account. Below, we present a new dynamic programming algorithm. For a given h, the idea of a dynamic programming algorithm to minimize the function (3) is as follows. We define the states of the form (
i
,
r
), where i means that jobs J
1
,
J
2
,
…
,
J
i have been considered and r, (1
≤
r
≤
min
⁡
{
i
,
h
}), represents how many of these jobs have been sequenced as nontardy jobs. A state (
i
,
r
) is associated with f
(
i
,
r
), the smallest value of the objective function in the class of partial schedules for processing i jobs, provided that r of the these jobs has been sequenced nontardy. This method works by either each job tardy or nontardy. Next, all f
(
i
,
r
) values can be calculated by applying the recursion for i
=
1,2
,
…
,
n and r
≥
max
⁡
{
1
,
h
-
(
n
-
i
)
}. The condition is that r
≥
h
-
(
n
-
i
) is necessary to ensure that we do not consider states that might lead to a solution which has fewer than r jobs in set N
E: since |
N
E
|
=
h and there are r jobs that have been sequenced nontardy among the first i jobs, the remaining h
-
r nontardy jobs needed to be selected from the last n
-
i jobs. The formal statement of the algorithm is below.Algorithm 9.
Step
0. Renumber the jobs in theLPTorder such that p
1
≥
p
2
≥
⋯
≥
p
n.
Step
1. Calculate positional weights w
j
=
w
-
j
g
(
j
) where
(31)
w
-
j
=
{
α
(
j
-
1
)
+
1
2
α
δ
(
h
-
j
)
(
h
+
j
-
1
)
m
k
1
2
+
[
1
+
δ
(
h
-
j
)
]
γ
}
,
(
j
=
1,2
,
…
,
h
)
for theCON model and w
-
1
=
α
+
γ
[
1
+
(
h
-
1
)
δ
], w
-
j
=
α
+
[
α
(
j
-
1
)
+
γ
]
[
1
+
δ
(
h
-
j
)
], (j
=
2
,
…
,
h
-
1), and w
-
h
=
0 for theSLKmodel. Reorder the positional weights such that w
i
1
≤
w
i
2
≤
⋯
≤
w
i
h. Initialize f
(
0,0
)
=
0, f
(
i
,
r
)
=
∞ for r
>
i.
Step
2. For i from 1 to n calculate
(32)
f
(
i
,
0
)
=
f
(
i
-
1,0
)
+
β
i
,
(33)
f
(
i
,
r
)
=
min
⁡
{
f
(
i
-
1
,
r
)
+
β
i
,
f
(
i
-
1
,
r
-
1
)
+
w
i
r
p
i
}
,
mmmmi
max
⁡
{
1
,
h
-
(
n
-
i
)
}
≤
r
≤
min
⁡
{
i
,
h
}
.
Step
3. Compute the optimal value of the function f
*
(
h
)
=
f
(
n
,
h
).
For a givenh value, calculating all possible f
(
n
,
h
) values using the above recursion relation requires O
(
n
h
) time. Since the value of positional weights (and the order of positional weights) can be altered by changing the h value, we must repeat the entire programming procedure for each h
=
0,1
,
2
,
…
,
n. Thus the minimal objective value, F
*, is given by
(34)
F
*
=
min
⁡
h
=
0,1
,
…
,
n
{
f
*
(
h
)
}
.
Therefore, the following statement holds.Theorem 10.
Both the problems1
|
p
j
A
=
p
j
g
(
r
)
,
S
p
s
d
,
C
O
N
|
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
γ
d and 1
|
p
j
A
=
p
j
g
(
r
)
,
S
p
s
d
,
S
L
K
|
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
γ
d can be solved in O
(
n
3
) time.Example 11.
Consider the problem1
|
p
j
A
=
p
j
g
(
r
)
,
S
psd
,
C
O
N
|
α
∑
J
j
∈
N
E
E
j
+
∑
J
j
∈
N
T
β
j
U
j
+
γ
d.
Letn
=
5 and h
=
3. The weights are α
=
1, γ
=
2, and δ
=
0.1.
The processing times arep
1
=
7, p
2
=
6, p
3
=
5, p
4
=
2, and p
5
=
1.
The tardy penalties areβ
1
=
10, β
2
=
8, β
3
=
4, β
4
=
5, and β
5
=
6.
The positional effects areg
(
1
)
=
8, g
(
2
)
=
7, g
(
3
)
=
3, g
(
4
)
=
4, and g
(
5
)
=
7.
Positional weights arew
1
=
21.6, w
2
=
23.8, and w
3
=
12.
Positional weights are reordered such thatw
i
1
≤
w
i
2
≤
w
i
3; that is, w
i
1
=
w
3, w
i
2
=
w
1, and w
i
3
=
w
2:
(35)
f
(
0,0
)
=
0
,
i
=
1
,
f
(
1,0
)
=
f
(
0,0
)
+
β
1
=
10
,
f
(
1,1
)
=
f
(
0,0
)
+
w
i
1
p
1
=
84
,
i
=
2
,
f
(
2,0
)
=
f
(
1,0
)
+
β
2
=
18
,
f
(
2,1
)
=
min
⁡
{
f
(
1,1
)
+
β
2
,
f
(
1,0
)
+
w
i
1
p
2
}
=
min
⁡
{
92,82
}
=
82
,
f
(
2,2
)
=
f
(
1,1
)
+
w
i
2
p
2
=
203.6
,
i
=
3
,
f
(
3,0
)
=
f
(
2,0
)
+
β
3
=
22
,
f
(
3,1
)
=
min
⁡
{
f
(
2,1
)
+
β
3
,
f
(
2,0
)
+
w
i
1
p
3
}
=
min
⁡
{
86,78
}
=
78
,
f
(
3,2
)
=
min
⁡
{
f
(
2,2
)
+
β
3
,
f
(
2,1
)
+
w
i
2
p
3
}
=
min
⁡
{
207.6,190
}
=
190
,
f
(
3,3
)
=
f
(
2,2
)
+
w
i
3
p
3
=
322.6
,
i
=
4
,
f
(
4,0
)
=
f
(
3,0
)
+
β
4
=
27
,
f
(
4,2
)
=
min
⁡
{
f
(
3,2
)
+
β
4
,
f
(
3,1
)
+
w
i
2
p
4
}
=
min
⁡
{
195,121.2
}
=
121.2
,
f
(
4,3
)
=
min
⁡
{
f
(
3,3
)
+
β
4
,
f
(
3,2
)
+
w
i
3
p
4
}
=
min
⁡
{
327.6,237.6
}
=
237.6
,
i
=
5
,
f
(
5,0
)
=
f
(
4,0
)
+
β
5
=
33
,
f
(
5,3
)
=
min
⁡
{
f
(
4,3
)
+
β
5
,
f
(
4,2
)
+
w
i
3
p
5
}
=
min
⁡
{
243.6,145
}
=
145
.
Therefore, f
(
3
)
=
f
(
5,3
)
=
145.
The optimal sequence isπ
*
=
[
J
4
,
J
5
,
J
3
,
J
1
,
J
2
], d
*
=
41.9. The total cost is 145.


## 6. Conclusions

Scheduling problems involving position-dependent processing time have received increasing attention in recent years. In this paper, we considered single machine scheduling and due date assignment with setup time in which a job’s processing time depends on its position in a sequence. The setup time is past-sequence-dependent (p-s-d). The objective functions include total earliness, the weighted number of tardy jobs, and the cost of due date assignment. The due date assignment methods used in this problem include common due date (CON) and equal slack (SLK). We have presented an O
(
n
4
) time algorithm for the general case and an O
(
n
3
) time dynamic programming algorithm for the special cases. In the paper, the model with position-dependent effects is considered. However, in some other situations, a job’s processing time may be time-dependent or both position-dependent and time-dependent. Therefore, it is worthwhile for future research to investigate the model in which a job’s processing time depends both on its position in a sequence and its start time. It is also interesting for future research to investigate the model in the context of other scheduling settings, including multimachine and job-shop scheduling.



---

*Source: 620150-2014-08-27.xml*