# Approximation Algorithms and an FPTAS for the Single Machine Problem with Biased Tardiness Penalty

Authors: G. Moslehi; K. Kianfar
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

This paper addresses a new performance measure for scheduling problems, entitled “biased tardiness penalty.” We study the approximability of minimum biased tardiness on a single machine, provided that all the due dates are equal. Two heuristic algorithms are developed for this problem, and it is shown that one of them has a worst-case ratio bound of 2. Then, we propose a dynamic programming algorithm and use it to design an FPTAS. The FPTAS is generated by cleaning up some states in the dynamic programming algorithm, and it requiresO
n
3
/
ε time.


---

## Body

## 1. Introduction

In this paper, we study a single machine scheduling problem of minimizing total biased tardiness about a common due date. Every jobi  (
1
≤
i
≤
n
) has a processing time p
i, a weight tardiness factor w
i, and a base tardiness factor u
i. The machine is available at time zero and can process at most one job at a time. The jobs have a common due date d. The biased tardiness penalty of job i is defined as
(1)
Z
i
=
{
0
,
if
C
i
≤
d
u
i
+
w
i
(
C
i
-
d
)
,
if
C
i
>
d
,
where C
i is the completion time of job i. Figure 1 shows the biased tardiness penalty of job i based on its completion time in a sequence. The resulting problem is denoted by 1
∣
d
i
=
d
∣
BTP, where BTP means “biased tardiness penalty.”Figure 1
Biased tardiness penalty for jobi.Biased tardiness penalty is a kind of performance measures that, according to our observations, has not been studied in the literature in spite of its wide use in practical situations. One of the most common applications of biased tardiness is in designing delivery contracts. In many of delivery contracts, once an order is delivered later than its due date, a fixed penalty must be paid, and when the delivery becomes tardier, the related penalty will increase as well. Many of the practical conditions support this assumption; for example, consider a company where just one day delay in receiving raw materials will break down its production line. In this case, the initial damage caused by late delivery is huge while if the delay increases, the additional damage is relatively small. Another application for biased tardiness penalty is in transportation systems where we must pay extra money for solo-transporting a piece of goods if it is not ready to be carried with other orders.Problem1
∥
∑
w
i
T
i is NP-hard in the strong sense if the tardiness weights are not all equal [1, 2] and is optimally solvable in pseudo-polynomial time for a fixed number of distinct due dates [3]. Cheng et al. [4] have shown that the schedule that minimizes ma
x
j
w
j
T
j gives an (
n
-
1
)-approximation for this problem. Kolliopoulos and Steiner [3] design pseudo-polynomial algorithms for the case that there is only a fixed number of different due dates. They also develop an FPTAS if, in addition, the tardiness weights are bounded by a polynomial function of n. Karakostas et al. [5] consider the same problem, design a pseudo-polynomial algorithm, and apply a rounding scheme to obtain the desired approximation scheme.In a special case of problem1
∥
∑
w
i
T
i where the due date is common for all jobs, the resulting problem is proved to be NP-hard in the ordinary sense by Yuan [6], and Lawler and Moore [7] provide a pseudo-polynomial dynamic programming algorithm in O
(
n
2
d
) time. Fathi and Nuttle [8] develop a 2-approximation algorithm that requires O
(
n
2
) time. Kellerer and Strusevich [9] propose an FPTAS of O
(
n
6
log
⁡
W
/
ε
3
) time complexity, where W is the sum of tardiness weights; later, Kacem [10] studies the same problem and develops another approach to obtain a more effective FPTAS in O
(
n
2
/
ε
) time.If the tardiness weights are equal, problem1
∥
∑
T
i is NP-hard in the ordinary sense as proved by Du and Leung [11], and it is solvable by a pseudo-polynomial dynamic programming algorithm proposed by Lawler [1]. For this problem, Lawler [12] proposes a dynamic programming algorithm and converts it into an FPTAS of O
(
n
7
/
ε
) time complexity. Koulamas [13] provides a faster FPTAS running in O
(
n
5
log
⁡
n
+
n
5
/
ε
) time by applying an alternative rounding scheme in conjunction with implementing Kovalyov’s [14] bound improvement procedure. Della Croce et al. [15] consider some popular constructive and decomposition heuristics and conclude that none of them guarantees a constant worst-case ratio bound. Kovalyov and Werner [16] study the approximability of this problem on parallel machines with a common due date.To examine the complexity of problem1
∣
d
i
=
d
∣
BTP, we compare it with the problem of minimizing weighted tardiness on a single machine and common due date. If we set u
i
=
0 for all jobs i, the considered problem transforms to problem 1
∣
d
i
=
d
∣
∑
w
i
T
i that is shown in [1, 2] to be NP-hard in the ordinary sense.The remainder of this paper is organized as follows. In Sections2 and 3, we describe two heuristic algorithms for problem 1
∣
d
i
=
d
∣
BTP and prove their worst-case ratio bounds. Section 4 describes a dynamic programming algorithm that, in Section 5, we convert to an FPTAS using the technique ofstructuring the execution of an algorithm. Concluding remarks are given in Section 6.


## 2. SPT Algorithm

In this heuristic algorithm, jobs are sequenced according to a nondecreasing order of processing times, and, hence, it can be implemented inO
(
n
log
⁡
n
) time.Theorem 1.
Letw
min
⁡ and w
max
⁡ be, respectively, the smallest and largest weight tardiness factors, and let u
min
⁡ and u
max
⁡ be the smallest and largest base tardiness factors. Then, one has
(2)
Z
S
P
T
Z
*
≤
max
⁡
{
u
max
⁡
u
min
⁡
,
w
max
⁡
w
min
⁡
}
,
where Z
S
P
T is the penalty created bySPT algorithm and Z
* shows the optimal penalty for problem 1
∣
d
i
=
d
∣
B
T
P.Proof.
Consider two ordered sets{
A
w
} and {
A
u
} that include a nondecreasing order of the weight tardiness factors and base tardiness factors, respectively. Suppose that we create n dummy jobs by pairing processing times in SPT ordering and tardiness factors according to their reverse order in sets {
A
w
} and {
A
u
}. It can be easily verified that the associated total penalty, called L
B
*, is a lower bound on the total penalty of any sequence for real jobs.
Similarly, create another set ofn dummy jobs by pairing processing times in SPT ordering but tardiness factors consistent with the order of sets {
A
w
} and {
A
u
}. It can be easily tested that if we sequence these dummy jobs according to SPT ordering, the related total penalty, called U
B
SPT, is an upper bound on Z
SPT for the real jobs. Let n
T be the number of tardy jobs under SPT ordering. Also, let A
w
[
r
] and A
u
[
r
] denote the rth job in sets {
A
w
} and {
A
u
}, respectively. Also, let C
[
r
]
SPT denote the completion time of rth job in SPT ordering. Thus, we have
(3)
U
B
SPT
=
A
w
[
n
-
n
T
+
1
]
(
C
[
n
-
n
T
+
1
]
SPT
-
d
)
+
⋯
+
A
w
[
n
]
(
C
[
n
]
SPT
-
d
)
+
A
u
[
n
]
+
⋯
+
A
u
[
n
-
n
T
+
1
]
,
L
B
*
=
A
w
[
n
T
]
(
C
[
n
-
n
T
+
1
]
SPT
-
d
)
+
⋯
+
A
w
[
1
]
(
C
[
n
]
SPT
-
d
)
+
A
u
[
1
]
+
⋯
+
A
u
[
n
T
]
.
From (3) and the fact that the values are nondecreasingly ordered in sets {
A
w
} and {
A
u
}, we get
(4)
U
B
SPT
≤
w
max
⁡
[
(
C
[
n
-
n
T
+
1
]
SPT
-
d
)
+
⋯
+
(
C
[
n
]
SPT
-
d
)
]
+
u
max
⁡
n
T
,
L
B
*
≥
w
min
⁡
[
(
C
[
n
-
n
T
+
1
]
SPT
-
d
)
+
⋯
+
(
C
[
n
]
SPT
-
d
)
]
+
u
min
⁡
n
T
.
And if we signify the term (
C
[
n
-
n
T
+
1
]
SPT
-
d
)
+
⋯
+
(
C
[
n
]
SPT
-
d
) by T
SPT, then
(5)
U
B
SPT
L
B
*
≤
w
max
⁡
T
SPT
+
u
max
⁡
n
T
w
min
⁡
T
SPT
+
u
min
⁡
n
T
≤
max
⁡
{
w
max
⁡
w
min
⁡
,
u
max
⁡
u
min
⁡
}
,
which completes the proof.The following example illustrates that the worst-case ratio bound obtained by SPT ordering is tight for problem1
∣
d
i
=
d
∣
BTP.Example 2.
Suppose that we have two jobs with parameters given in Table1 and a common due date d
=
100.
SPT ordering generates the sequence (2-1) with total penalty equal to 1020, while the optimal sequence for this example is (1-2) with the total penalty of 204. So,(6)
Z
SPT
Z
*
=
1020
204
=
5
,
max
⁡
{
u
max
⁡
u
min
⁡
,
w
max
⁡
w
min
⁡
}
=
max
⁡
{
20
4
,
100
20
}
=
5
.Table 1
Jobs' parameters in Example2.
Jobi
p
i
w
i
u
i
1
100
100
20
2
10
20
4


## 3. Algorithm MPR (Minimum Penalty Rate)

In this section, we present another heuristic algorithm for problem1
∣
d
i
=
d
∣
BTP and show that the worst-case ratio bound of this algorithm is 2. Let G
=
(
g
[
1
]
,
g
[
2
]
,
…
,
g
[
n
]
) denote the sequence generated by MPR algorithm, where g
[
i
] represents the ith job within this sequence. This algorithm requires at most n iterations and during its rth iteration the (
n
-
r
+
1
)th element of G, g
[
n
-
r
+
1
], will be determined. Also, if there are some unscheduled jobs at each iteration filling the whole remaining period through due date (remaining tardiness period), we will choose the one making the minimum penalty and save the related sequence, G
^, beside the main sequence G. Finally, the algorithm sorts tardy jobs in the main and secondary sequences according to WSPT (weighted shortest processing time) ordering and returns the sequence with smaller penalty.LetZ
g
[
r
,
n
] denote sum penalties related to the jobs from rth position through the last job in sequence G. So, the algorithm is as follows.Algorithm MPR.(1)
LetU
=
{
1,2
,
…
,
n
} be the set of unscheduled jobs and let r be the counter index of positions in the sequence. Set C
[
n
]
=
P
sum
=
∑
i
=
1
n
p
i and r
=
n.
(2)
DefineU
^
=
{
i
∈
U
∣
p
i
≥
C
[
n
]
-
d
}. If U
^ is empty, then Z
^
best
=
∞; else, consider the job with the minimum penalty in U
^ as job i
^ that is calculated by Z
^
best
=
u
i
^
+
w
i
^
(
C
[
n
]
-
d
)
=
min
⁡
i
∈
U
^
{
u
i
+
w
i
(
C
[
n
]
-
d
)
} and also g
^
[
n
]
=
i
^.
(3)
For all jobsi
∈
U, calculate θ
i values by (7) and select a job k such that θ
k
=
min
⁡
i
∈
U
{
θ
i
}. If there is a tie, select the job with the smaller processing time;
(7)
θ
i
=
u
i
+
w
i
(
C
[
r
]
-
d
)
min
⁡
(
p
i
,
C
[
r
]
-
d
)
.
(4)
SetU
=
U
/
{
k
}, g
[
r
]
=
k, and C
[
r
-
1
]
=
C
[
r
]
-
p
k.
(5)
IfU
^
=
{
i
∈
U
∣
p
i
≥
C
[
r
-
1
]
-
d
} is not empty, then calculate the value Z
^
=
u
i
^
+
w
i
^
(
C
[
r
-
1
]
-
d
)
=
min
⁡
i
∈
U
^
{
u
i
+
w
i
(
C
[
r
-
1
]
-
d
)
}. If Z
^
+
Z
g
[
r
,
n
]
<
Z
^
best, then set Z
^
best
=
Z
^
+
Z
g
[
r
,
n
], g
^
[
r
-
1
]
=
i
^, and g
^
[
i
]
=
g
[
i
]  ∀
i
=
r
,
…
,
n.
(6)
IfC
[
r
-
1
]
>
d, then r
=
r
-
1 and go back to step 3.
(7)
Schedule the remaining jobs at the beginning of sequencesG and G
^.
(8)
Sort the tardy jobs in sequencesG and G
^ according to the nonincreasing order of w
i
/
p
i ratios.
(9)
IfZ
G
≤
Z
G
^, then return the sequence G
=
(
g
[
1
]
,
g
[
2
]
,
…
,
g
[
n
]
) with Z
g
[
1
,
n
] penalty, and, else, return the sequence G
^
=
(
g
^
[
1
]
,
g
^
[
2
]
,
…
,
g
^
[
n
]
) with penalty equal to Z
g
^
[
1
,
n
].It can be easily seen that MPR algorithm runs inO
(
n
2
) time. The following example illustrates the implementation of MPR algorithm on a simple problem.Example 3.
Suppose a problem with four jobs and a common due dated
=
10. Table 2 shows the jobs’ parameters.
At first,C
[
4
]
=
23, Z
^
best
=
∞, and U
^ is empty. At the first iteration of running the algorithm (
r
=
4
), we have θ
1
=
17.43, θ
2
=
11.33, θ
3
=
12.5, and  θ
4
=
13.67, where job 2 has the minimum value, and, hence, it is sequenced at the last position of G. Also, C
[
3
]
=
17, U
^
=
{
1
}, and Z
^
=
74, and considering Z
g
[
4,4
]
=
68, we get Z
^
best
=
142. So, g
^
[
4
]
=
2 and g
^
[
3
]
=
1.
At the second iteration(
r
=
3
), we have θ
1
=
10.57
,
θ
3
=
9.5, and   θ
4
=
8.67, where job 4 has the minimum value, and, hence, g
[
3
]
=
4. The algorithm calculates C
[
2
]
=
11, U
^
=
{
1,3
}, and Z
^
=
26, and considering Z
^
+
Z
g
[
3,4
]
=
146
>
Z
^
best, the value of Z
^
best will remain unchanged. At the last iteration (
r
=
2
), we have θ
1
=
26 and θ
3
=
26, and the algorithm sequences job 3 at the second position of sequence G. Also, C
[
1
]
=
7 and U
^ is empty.
After arbitrary scheduling the remaining jobs at the beginning of sequencesG and G
^, we get G
=
(
1,3
,
4,2
) and G
′
=
(
3,4
,
1,2
). These sequences are modified to G
=
(
1,4
,
2,3
) and G
′
=
(
3,4
,
1,2
) after implementing step 8. Also, Z
G
=
134 and Z
G
^
=
142, which forces the algorithm to select sequence G as the final output.Table 2
Jobs' parameters in Example3.
Jobi
p
i
w
i
u
i
1
7
8
18
2
6
4
16
3
4
2
24
4
6
5
17Here, we present two theorems about problem1
∣
d
i
=
d
∣
BTP which are used for proving the worst-case ratio bound of MPR algorithm.Theorem 4.
Consider a problem1
∣
d
i
=
d
∣
B
T
P. Define two sequences σ
=
(
σ
1
,
…
,
σ
m
) and σ
′
=
(
σ
1
′
,
…
,
σ
m
′
′
) on a common time interval, where the relation Z
i
/
min
⁡
(
p
i
,
C
i
-
d
)
≤
Z
j
/
min
⁡
(
p
j
,
C
j
-
d
) holds for all jobs i in σand jobs j in σ
′. Then, Z
σ
≤
Z
σ
′.Proof.
Consider two sequencesσ and σ
′ with tardiness penalties shown in Figure 2. Suppose that θ
σ
(
t
) and θ
σ
′
(
t
) denote the slope of the functions related to sequences σ and σ
′, respectively; then, according to the theorem’s assumption, we have θ
σ
(
t
)
≤
θ
σ
′
(
t
) for all t
∈
[
d
,
D
]. It is obvious that for all t
∈
[
d
,
D
] (especially for point d) the function related to sequence σ falls under the function related to sequence σ
′ and, hence, ∑
i
=
1
m
Z
σ
i
≤
∑
j
=
1
m
′
Z
σ
j
′. A similar conclusion can be made for the case where C
σ
m
<
C
σ
m
′
′ holds.Figure 2
Penalties related to sequencesσ and σ
′.Theorem 5.
In any optimal sequence for problem1
∣
d
i
=
d
∣
B
T
P, the tardy jobs with start time greater than or equal to d must be sequenced in WSPT ordering. This means that
(8)
∀
i
,
j
∈
Z
*
:
d
≤
C
i
-
p
i
<
C
j
-
p
j
⟹
p
i
w
i
≤
p
j
w
j
.Proof.
The proof is easily done by swapping each pair of the adjacent tardy jobs.Theorem 6.
Algorithm MPR gives a 2-approximation for problem1
∣
d
i
=
d
∣
B
T
P.Proof.
See the appendix.The following example illustrates that the worst-case ratio bound obtained by MPR is tight for problem1
∣
d
i
=
d
∣
BTP.Example 7.
Suppose that we haven
+
1 jobs with parameters given in Table 3 and a common due date d
=
n.
Algorithm MPR gives the sequence(
2
,
3
,
…
,
n
,
1
) with n
2
+
n
+
1 total penalty, while the optimal penalty is (
1
/
2
)
n
2
+
2
n
+
1
/
2 related to the sequence (
1
,
2
,
…
,
n
). Thus,
(9)
Z
G
Z
*
=
n
2
+
n
+
1
(
1
/
2
)
n
2
+
2
n
+
1
/
2
⟹
lim
⁡
n
→
∞
Z
G
Z
*
=
2
.Table 3
Jobs' parameters in Example7.
Jobi
p
i
w
i
u
i
1
n
n
+
1
/
n
n
2 ton
+
1
1
1
+
1
/
n
1


## 4. Dynamic Programming (DP) Algorithm

Without loss of generality, we consider that jobs are indexed according to the WLPT ordering. For problem1
∣
d
i
=
d
∣
BTP, an optimal schedule belongs to the class of schedules in which the early jobs are processed starting at time zero and are followed by a straddling job, called job α, that starts no later than time d and is completed after time d; in turn, the straddling job is followed by the block of tardy jobs. The early jobs can be processed in any order, while, according to Theorem 5, tardy jobs that start at or after the due date must be processed according to WSPT numbering. Let us introduce the following notations.[
t
,
f
] is a state in the state space, where t denotes the total processing time of early jobs and f is the total penalty of state.
ν
k
(
α
) is a set of states for the first k jobs, except for job α.
Z
α
* is the minimum penalty value for problem 1
∣
d
i
=
d
∣
BTP with a fixed straddling job α.
P
sum is the total processing time of all jobs.This DP algorithm schedules early jobs starting from time zero and the tardy jobs so that they become complete exactly at timeP
sum. According to this, the algorithm can be described as in Algorithm 1.Algorithm 1:DP algorithm.
(1) For eachα
=
{
1,2
,
…
,
n
}
(1.1) Setν
0
(
α
)
=
{
[
0,0
]
}
(1.2) For eachk
=
{
1,2
,
…
,
α
-
1
,
α
+
1
,
…
,
n
}
(i) Consider every state[
t
,
f
] in ν
k
-
1
(
α
)
(a) Ift
+
p
k
≤
d then add [
t
+
p
k
,
f
] to ν
k
(
α
)
(b) IfP
sum
-
∑
i
=
1
k
p
i
+
t
>
d then add [
t
,
f
+
u
k
+
w
k
(
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
-
d
)
] to ν
k
(
α
)
(ii) Delete the state spaceν
k
-
1
(
α
)
(1.3) SetZ
α
*
=
min
[
t
,
f
]
∈
ν
n
(
α
)
⁡
{
f
+
u
α
+
w
α
(
t
+
p
α
-
d
)
}
(2) Calculate the optimal value fromZ
*
=
min
α
∣
Z
α
*
≠
∅
⁡
Z
α
*LetU
B
* be an upper bound on the optimal penalty, and since f
≤
U
B
* and t
≤
d, we can restrict the number of states ν
k
(
α
) by d
×
U
B
*. The complexity of substep 1.2 of the DP algorithm is proportional to ∑
k
=
1
n
|
ν
k
(
α
)
| that leads to O
(
n
·
d
·
U
B
*
) time. However, this complexity can be reduced to O
(
n
·
d
) by selecting a state [
t
,
f
] with the smallest value of f at each iteration k and for every t. Similarly, we can get the complexity of substep 1.3 as O
(
d
), and so, the complexity of step 1 is O
(
n
2
·
d
). Step 2 requires O
(
n
) time, and the final complexity of DP algorithm will be calculated as O
(
n
2
·
d
). The following example illustrates the details of DP algorithm.Example 8.
Consider an instance of problem1
∣
d
i
=
d
∣
BTP with 3 jobs. The parameters of the jobs are given in Table 4, and the common due date is given as d
=
6 in this example.
Table5 shows the states generated in each states space regarding the selected straddling jobs as well as subsequences coupled with these states. The optimal value is Z
*
=
min
⁡
{
57,56,58
}
=
56 related to sequence (
3,2
,
1
) which is obtained by inserting straddling job α
=
2 into the subsequence (
3
,
,
1
).Table 4
Jobs' parameters in Example8.
Jobi
p
i
w
i
u
i
1
5
2
12
2
7
3
14
3
3
4
9Table 5
Procedure of DP algorithm in Example8.
v
0
(
α
)
v
1
(
α
)
v
2
(
α
)
Z
α
*
State
Sequence
State
Sequence
State
Sequence
α
=
1
[0, 0]
(  ,  ,  )
[0, 41]
(  ,  ,  2)
[3, 41]
(3,  ,   2)
41
+
16
=
57
α
=
2
[0, 0]
(  ,  ,  )
[5, 0]
[0, 30]
(1,  ,  )(  ,  ,  1)
[5, 45]
[3, 30]
[0, 55]
(1,  ,  3)(3,  ,  1)(  ,  3,   1)
min
⁡
{
45
+
32
30
+
26
55
+
17
}
=
56
α
=
3
[0, 0]
(  ,  ,  )
[5, 0]
[0, 30]
(1,  ,  )(  ,  ,  1)
[5, 41]
(1,  ,  2)
41
+
17
=
58


## 5. FPTAS Algorithm

One of the standard approaches to generate an FPTAS is the technique ofstructuring the execution of an algorithm. Here, the main idea is to take the exact but slow DP algorithm described in Section 4 and to interact with it while it is working. If the algorithm generates a lot of auxiliary states during its execution, then we may remove some of these states and clean up the algorithm’s memory. This method was introduced by Ibarra and Kim [17] for solving the knapsack problem, and in the recent years numerous scheduling problems have applied such an approach (see [18–22]). First, let us introduce the following notations.ε is the error bound of FPTAS algorithm.
ν
k
(
α
)
# is a set of states generated by FPTAS for the first k jobs, except for job α.
Z
α
# is the minimum penalty generated by FPTAS for problem 1
∣
d
i
=
d
∣
BTP with a fixed straddling job α.
Z
# is the minimum penalty generated by FPTAS for problem 1
∣
d
i
=
d
∣
BTP.Consider the penalty of algorithm MPR, calledZ
H, as an upper bound for the problem. To reduce the number of states in each iteration, we split the feasible interval [
0
,
Z
H
] related to the second coordinate of state [
t
,
f
] into L
+
1 equal subintervals I
m
=
[
(
m
-
1
)
Δ
,
m
Δ
)
1
≤
m
≤
L
+
1 of length Δ. For each of the resulting subintervals I
m, we keep at most one state with the smallest value t. Given an arbitrary ε
>
0, define
(10)
LB
=
Z
H
2
,
L
=
⌈
2
n
ε
⌉
,
Δ
=
Z
H
L
.The FPTAS algorithm works on the reduced state spaceν
k
(
α
)
# instead of ν
k
(
α
) and can be described as in Algorithm 2.Algorithm 2:FPTAS algorithm.
(1) For eachα
=
{
1,2
,
…
,
n
}
(1.1) Setν
0
(
α
)
#
=
{
[
0,0
]
}
(1.2) For eachk
=
{
1,2
,
…
,
α
-
1
,
α
+
1
,
…
,
n
}
(i) Consider every state[
t
,
f
] in ν
k
-
1
(
α
)
#
(a) Ift
+
p
k
≤
d then add [
t
+
p
k
,
f
] to ν
k
(
α
)
#
(b) IfP
sum
-
∑
i
=
1
k
p
i
+
t
>
d then add [
t
,
f
+
u
k
+
w
k
(
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
-
d
)
] to ν
k
(
α
)
#
(ii) Delete the state spaceν
k
-
1
(
α
)
#
(iii) Let[
t
,
f
]
m be a state in ν
k
(
α
)
# such that f
∈
I
m with the smallest t (break ties
by choosing the state of the smallest f). Set ν
k
(
α
)
#
=
{
[
t
,
f
]
m
∣
1
≤
m
≤
L
+
1
}
(1.3) SetZ
α
#
=
min
[
t
,
f
]
∈
ν
n
(
α
)
#
⁡
{
f
+
u
α
+
w
α
(
t
+
p
α
-
d
)
}
(2) Calculate the final solution of FPTAS fromZ
#
=
min
α
∣
Z
α
#
≠
∅
⁡
Z
α
#


### 5.1. Worst-Case Analysis of the FPTAS Algorithm

The worst-case analysis is based on comparing the execution of DP and FPTAS algorithms. First, a lemma is provided that will be used to prove the worst-case ratio bound of FPTAS.Lemma 9.
Let[
t
,
f
] be an arbitrary state in ν
k
(
α
). The FPTAS algorithm generates at least one state [
t
#
,
f
#
] in ν
k
(
α
)
# such that t
#
≤
t and f
#
≤
f
+
k
Δ.Proof.
The proof is done by induction onk. For k
=
0, obviously we have ν
0
(
α
)
#
=
ν
0
(
α
). Suppose that the lemma is valid up to k
-
1 and we want to show its validity for iteration k. Let [
t
,
f
] be a state in ν
k
(
α
) generated by the DP algorithm from a feasible state [
t
′
,
f
′
] at iteration k
-
1. Here, two cases can be distinguished. In the first case [
t
,
f
]
=
[
t
′
+
p
k
,
f
′
] and in the second case [
t
,
f
]
=
[
t
′
,
f
′
+
u
k
+
w
k
max
⁡
{
0
,
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
′
-
d
}
] holds. We prove the statement for iteration k in these two cases.
Case  1 ([
t
,
f
]
=
[
t
′
+
p
k
,
f
′
]). Since [
t
′
,
f
′
]
∈
ν
k
-
1
(
α
), there exists a state [
t
′
#
,
f
′
#
]
∈
ν
k
-
1
(
α
)
# such that t
′
#
≤
t
′ and f
′
#
≤
f
′
+
(
k
-
1
)
Δ. Therefore, the FPTAS algorithm generates the state [
t
′
#
+
p
k
,
f
′
#
] that may be eliminated when cleaning up the state subset. Let [
λ
,
μ
] be the remaining state in ν
k
(
α
)
# that is in the same interval as [
t
′
#
+
p
k
,
f
′
#
]. Thus, we drive that
(11)
λ
≤
t
′
#
+
p
k
≤
t
′
+
p
k
=
t
,
μ
≤
f
′
#
+
Δ
≤
f
′
+
(
k
-
1
)
Δ
+
Δ
=
f
+
k
Δ
.
Consequently, the lemma holds for iteration k in this case.
Case  2 ([
t
,
f
]
=
[
t
′
,
f
′
+
u
k
+
w
k
max
⁡
{
0
,
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
′
-
d
}
]). Since [
t
′
,
f
′
]
∈
ν
k
-
1
(
α
), there exists a state [
t
′
#
,
f
′
#
]
∈
ν
k
-
1
(
α
)
# such that t
′
#
≤
t
′ and f
′
#
≤
f
′
+
(
k
-
1
). Therefore, the FPTAS algorithm generates the state [
t
′
#
,
f
′
#
+
u
k
+
w
k
max
⁡
{
0
,
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
′
#
-
d
}
] at iteration k that may be eliminated during the cleaning up procedure. Let [
λ
′
,
μ
′
] be the remaining state in ν
k
(
α
)
# that is in the same interval as [
t
′
#
,
f
′
#
+
u
k
+
w
k
max
⁡
{
0
,
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
′
#
-
d
}
]. So, we have
(12)
λ
′
≤
t
′
#
≤
t
′
=
t
,
μ
′
≤
f
′
#
+
u
k
+
w
k
max
⁡
{
0
,
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
′
#
-
d
}
+
Δ
≤
f
′
+
(
k
-
1
)
Δ
+
u
k
+
w
k
max
⁡
{
0
,
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
′
#
-
d
}
+
Δ
≤
f
′
+
(
k
-
1
)
Δ
+
u
k
+
w
k
max
⁡
{
0
,
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
′
-
d
}
+
Δ
=
f
+
k
Δ
.
Thus, the lemma is proved for iteration k in this case, too.Theorem 10.
Given an arbitraryε
>
0, the FPTAS algorithm outputs a sequence with Z
# penalty such that Z
#
≤
(
1
+
ε
)
Z
*.Proof.
There exists a straddling job, calledα
*
, in the optimal sequence for problem 1
∣
d
i
=
d
∣
BTP. Since the FPTAS algorithm checks all jobs as straddling, then obviously job α
* will be selected in one of its iterations.
By definition, the optimal sequence can be related to a state[
t
α
*
*
,
f
α
*
*
] in ν
n
(
α
*
). According to Lemma 9, the FPTAS algorithm generates a state [
t
α
*
#
,
f
α
*
#
] in ν
n
(
α
*
)
# such that t
α
*
#
≤
t
α
*
* and
(13)
f
α
*
#
≤
f
α
*
*
+
n
Δ
=
f
α
*
*
+
n
Z
H
L
=
f
α
*
*
+
n
Z
H
⌈
2
n
/
ε
⌉
≤
f
α
*
*
+
n
Z
H
2
n
/
ε
=
f
α
*
*
+
ε
·
LB
.
It is clear thatZ
*
≥
LB. Let T
α
*
* and T
α
*
# denote the tardiness of job α
* in the optimal and FPTAS solutions, respectively. From f
α
*
*
+
T
α
*
*
=
Z
*, we have
(14)
t
α
*
#
≤
t
α
*
*
⟹
T
α
*
#
≤
T
α
*
*
⟹
f
α
*
#
+
T
α
*
#
≤
f
α
*
*
+
ε
·
LB
+
T
α
*
*
⟹
Z
#
≤
(
1
+
ε
)
Z
*
.
This will complete the proof.


### 5.2. Complexity of the FPTAS Algorithm

MPR algorithm runs inO
(
n
2
) time as the initial phase of FPTAS. The state space ν
k
(
α
)
#  (
k
=
{
1,2
,
…
,
n
}
) is generated at each iteration of substep 1.2 and in O
(
n
2
) time. Since |
ν
k
(
α
)
#
|
≤
L, we have
(15)
∑
k
=
1
n
|
ν
k
(
α
#
)
|
≤
n
L
=
n
⌈
2
n
ε
⌉
≤
n
(
2
n
ε
+
1
)
.According to this, substep 1.2 requiresO
(
n
2
/
ε
) time. Noting that step 1 iterates n times for every selection of α values, the complexity of this step is O
(
n
3
/
ε
). Finally, step 2 requires O
(
n
) time, and the final complexity of the FPTAS algorithm is computed as O
(
n
3
/
ε
).


## 5.1. Worst-Case Analysis of the FPTAS Algorithm

The worst-case analysis is based on comparing the execution of DP and FPTAS algorithms. First, a lemma is provided that will be used to prove the worst-case ratio bound of FPTAS.Lemma 9.
Let[
t
,
f
] be an arbitrary state in ν
k
(
α
). The FPTAS algorithm generates at least one state [
t
#
,
f
#
] in ν
k
(
α
)
# such that t
#
≤
t and f
#
≤
f
+
k
Δ.Proof.
The proof is done by induction onk. For k
=
0, obviously we have ν
0
(
α
)
#
=
ν
0
(
α
). Suppose that the lemma is valid up to k
-
1 and we want to show its validity for iteration k. Let [
t
,
f
] be a state in ν
k
(
α
) generated by the DP algorithm from a feasible state [
t
′
,
f
′
] at iteration k
-
1. Here, two cases can be distinguished. In the first case [
t
,
f
]
=
[
t
′
+
p
k
,
f
′
] and in the second case [
t
,
f
]
=
[
t
′
,
f
′
+
u
k
+
w
k
max
⁡
{
0
,
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
′
-
d
}
] holds. We prove the statement for iteration k in these two cases.
Case  1 ([
t
,
f
]
=
[
t
′
+
p
k
,
f
′
]). Since [
t
′
,
f
′
]
∈
ν
k
-
1
(
α
), there exists a state [
t
′
#
,
f
′
#
]
∈
ν
k
-
1
(
α
)
# such that t
′
#
≤
t
′ and f
′
#
≤
f
′
+
(
k
-
1
)
Δ. Therefore, the FPTAS algorithm generates the state [
t
′
#
+
p
k
,
f
′
#
] that may be eliminated when cleaning up the state subset. Let [
λ
,
μ
] be the remaining state in ν
k
(
α
)
# that is in the same interval as [
t
′
#
+
p
k
,
f
′
#
]. Thus, we drive that
(11)
λ
≤
t
′
#
+
p
k
≤
t
′
+
p
k
=
t
,
μ
≤
f
′
#
+
Δ
≤
f
′
+
(
k
-
1
)
Δ
+
Δ
=
f
+
k
Δ
.
Consequently, the lemma holds for iteration k in this case.
Case  2 ([
t
,
f
]
=
[
t
′
,
f
′
+
u
k
+
w
k
max
⁡
{
0
,
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
′
-
d
}
]). Since [
t
′
,
f
′
]
∈
ν
k
-
1
(
α
), there exists a state [
t
′
#
,
f
′
#
]
∈
ν
k
-
1
(
α
)
# such that t
′
#
≤
t
′ and f
′
#
≤
f
′
+
(
k
-
1
). Therefore, the FPTAS algorithm generates the state [
t
′
#
,
f
′
#
+
u
k
+
w
k
max
⁡
{
0
,
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
′
#
-
d
}
] at iteration k that may be eliminated during the cleaning up procedure. Let [
λ
′
,
μ
′
] be the remaining state in ν
k
(
α
)
# that is in the same interval as [
t
′
#
,
f
′
#
+
u
k
+
w
k
max
⁡
{
0
,
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
′
#
-
d
}
]. So, we have
(12)
λ
′
≤
t
′
#
≤
t
′
=
t
,
μ
′
≤
f
′
#
+
u
k
+
w
k
max
⁡
{
0
,
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
′
#
-
d
}
+
Δ
≤
f
′
+
(
k
-
1
)
Δ
+
u
k
+
w
k
max
⁡
{
0
,
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
′
#
-
d
}
+
Δ
≤
f
′
+
(
k
-
1
)
Δ
+
u
k
+
w
k
max
⁡
{
0
,
P
sum
-
∑
i
=
1
k
-
1
p
i
+
t
′
-
d
}
+
Δ
=
f
+
k
Δ
.
Thus, the lemma is proved for iteration k in this case, too.Theorem 10.
Given an arbitraryε
>
0, the FPTAS algorithm outputs a sequence with Z
# penalty such that Z
#
≤
(
1
+
ε
)
Z
*.Proof.
There exists a straddling job, calledα
*
, in the optimal sequence for problem 1
∣
d
i
=
d
∣
BTP. Since the FPTAS algorithm checks all jobs as straddling, then obviously job α
* will be selected in one of its iterations.
By definition, the optimal sequence can be related to a state[
t
α
*
*
,
f
α
*
*
] in ν
n
(
α
*
). According to Lemma 9, the FPTAS algorithm generates a state [
t
α
*
#
,
f
α
*
#
] in ν
n
(
α
*
)
# such that t
α
*
#
≤
t
α
*
* and
(13)
f
α
*
#
≤
f
α
*
*
+
n
Δ
=
f
α
*
*
+
n
Z
H
L
=
f
α
*
*
+
n
Z
H
⌈
2
n
/
ε
⌉
≤
f
α
*
*
+
n
Z
H
2
n
/
ε
=
f
α
*
*
+
ε
·
LB
.
It is clear thatZ
*
≥
LB. Let T
α
*
* and T
α
*
# denote the tardiness of job α
* in the optimal and FPTAS solutions, respectively. From f
α
*
*
+
T
α
*
*
=
Z
*, we have
(14)
t
α
*
#
≤
t
α
*
*
⟹
T
α
*
#
≤
T
α
*
*
⟹
f
α
*
#
+
T
α
*
#
≤
f
α
*
*
+
ε
·
LB
+
T
α
*
*
⟹
Z
#
≤
(
1
+
ε
)
Z
*
.
This will complete the proof.


## 5.2. Complexity of the FPTAS Algorithm

MPR algorithm runs inO
(
n
2
) time as the initial phase of FPTAS. The state space ν
k
(
α
)
#  (
k
=
{
1,2
,
…
,
n
}
) is generated at each iteration of substep 1.2 and in O
(
n
2
) time. Since |
ν
k
(
α
)
#
|
≤
L, we have
(15)
∑
k
=
1
n
|
ν
k
(
α
#
)
|
≤
n
L
=
n
⌈
2
n
ε
⌉
≤
n
(
2
n
ε
+
1
)
.According to this, substep 1.2 requiresO
(
n
2
/
ε
) time. Noting that step 1 iterates n times for every selection of α values, the complexity of this step is O
(
n
3
/
ε
). Finally, step 2 requires O
(
n
) time, and the final complexity of the FPTAS algorithm is computed as O
(
n
3
/
ε
).


## 6. Conclusion

In this paper, we presented a new performance measure for scheduling problems, calledbiased tardiness penalty. According to this performance measure, two kinds of penalties are assigned to each tardy job: one fixed penalty and the other that linearly increases by the increase in tardiness value. Two approximation algorithms were designed with the polynomial running times. The first approximation algorithm, SPT, gives a worst-case ratio bound linking to size of instances, while the second approximation algorithm, MPR, has a constant worst-case ratio bound of 2. Next, we developed a dynamic programming algorithm and converted it to an FPTAS using the method ofstructuring the execution of an algorithm. The resulting FPTAS runs in O
(
n
3
/
ε
) time.



---

*Source: 679702-2014-04-27.xml*