# A Nonpolynomial Optimal Algorithm for Sequencing Inspectors in a Repeat Inspection System with Rework

Authors: Moon Hee Yang; Jae Hyung Cho
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Assuming that two types of inspection errors are nonidentical and that only the items rejected by an inspector are reworked and sent to the next inspection cycle, we formulate a combinatorial optimization problem for simultaneously determining both the minimum frequency of inspection-rework cycles and the optimal sequence of inspectors selected from a set of available inspectors, in order to meet the constraints of the outgoing quality level. Based on the inherent properties from our mathematical model, we provide a nonpolynomial optimal algorithm with a time complexity ofO
(
2
m
).


---

## Body

## 1. Introduction

Criticisms of the “Zero Defects (ZD)” concept frequently center around allegations of extreme cost in meeting the standard. Proponents say that it is an entirely reachable ideal and that claims of extreme cost result from misapplication of the principles. In order to reach ZD or to meet the constraints of the outgoing quality with the ppm (parts per million) level demanded by consumers, many authors have proposed repeated inspection systems (RIS), such that the few nonconforming items that escape detection at the first inspection operation would then be caught during the second or third inspection operations. Especially for critical items that could result in catastrophic system failure, any type of RIS designed for critical item can turn out to be cost effective in terms of the expected total cost, since the cost resulting from a falsely accepted item is much higher than that of repeated inspections. In designing or redesigning a cost-effective RIS, many factors besides the number of repeated inspection cycles should be considered, such as objective functions, the number of quality characteristics (single or multiple), sequences of multiple quality characteristics, the type and assumption of inspection errors (type I and/or type II, identical or nonidentical), a series of fractions for inspection (partial/full or incomplete/complete), and sequences of inspectors if their errors are not identical.Several models of RISs subject to inspection errors under different conditions have appeared in the literature. We chronologically describe some papers partially related to our model. In the 1980s, Raouf et al. [1] were the first to develop a model for determining the optimal number of repeat inspections for multicharacteristic components to minimize the total expected cost. In the same year, Raz and Thomas [2] proposed a series of multiple inspections where only the items perceived to be conforming by all inspectors would be finally accepted, while the others would be discarded along the inspection line. Assuming that a group of inspectors operate at both different cost levels and nonidentical inspection errors in each stage in the sequence, a branch-and-bound technique was presented for determining an optimum sequencing inspection plan for obtaining a target quality level, minimal unit cost of production and inspection, and a series of optimal fractions for inspection. Based on dynamic programming, Drury et al. [3] examined different ways of combining the results of two different sequential inspections. Garcia-Diaz et al. [4] determined the number of repeated inspections at a certain cycle where the minimum expected total cost is achieved. Jaraiedi et al. [5] proposed a multiple-inspection system similar to Raz and Thomas’s model, but it differed in that an inspector must examine all the characteristics of a unit one by one. This model can be used for determining the minimum number of inspection stages to meet a target average outgoing quality. Tang [6] provided a rule for determining the optimal sequence of multiple quality characteristics for minimizing the cost of inspection within each inspection stage. Lee [7] dealt with the model discussed by Raouf et al. and developed a stop rule for seeking the optimal number of inspection stages.In the 1990s, Raz and Bricker [8] proposed three basic types of inspection sequences (complete, fixed, and variable) and studied the problem of sequencing inspection operations subject to errors in order to minimize the expected sum of inspection and penalty costs. Based on a branch-and-bound approach and recursive calls to a sequence of evaluation functions, the optimal algorithm for each type was provided, as well as a family of heuristics for the variable sequence problem. By modifying Raz and Thomas’s cost model slightly and under some regular conditions, Liou et al. [9] derived an analytical solution to determine the optimal number of inspectors and the optimal sequence of inspectors. Chen and Labbrecht [10] used marginal analysis and gave an efficient algorithm to optimize the sequence and frequency of inspections of multicharacteristic components. Chiou [11] proposed a multiple-inspection system, where the inspection error is identical, and rejected items are repairable. With or without the assumption of AOQL constraint (average outgoing quality limit) and reinspection policy, four types of mathematical models were suggested, and algorithms to solve the optimal number of inspection cycles as well as its optimal inspection fraction for each cycle were provided.In the 2000s, Yang [12] proposed an RIS with rework assuming identical inspection errors, repairable items, and a percent-defective target and provided an analytical formula for determining the minimum number of inspection-rework cycles that gave less than a target AOQ (average outgoing quality). Duffuaa and Khan [13] developed a general repeat inspection plan for dependent multicharacteristic critical components by extending the model given by Duffuaa and Nadeem [14]. Assuming six types of inspection errors, a procedure was provided for determining a local optimal number of cycles that minimized the total expected cost. Up to now, the effects of selecting and sequencing inspectors on AOQ or total inspection cost have rarely been studied, due to its inherent mathematical complexity. Only a few, such as Raouf et al. [1] and Raz and Thomas [2], have dealt with similar topics assuming that rejected items are discarded.In this paper, we assume that (1) all the items accepted by an inspector are not reinspected but stored in a specific storage area, (2) all the items rejected by an inspector are reworked and sent to the next inspection cycle, (3) an inspector performs a single characteristic inspection, and (4) the types I and II errors of inspectors are nonidentical, fixed, and known. In Section2, our problem is described in detail. In Section 3, we derive AOQ as a function of a sequence of inspectors and prove some fundamental properties. Based on the properties, we provide a practical algorithm for simultaneously determining an optimal frequency and an optimal sequence of inspectors, which gives a target AOQ.


## 2. Problem Statement

Suppose that the expected initial defective rate of items produced in production lines is given as a constantp and that we need repeated inspections in order to meet the constraints of the target AOQ level (q
G). Let W be a set of m available inspectors, represented as {
W
1
,
W
2
,
…
,
W
m
}, and let I
k (∈
W) be the inspector, selected from the set W and assigned to the kth inspection cycle. The following assumptions are made:(1)
I
k examines a single characteristic of an item at a time and examines all the items given during the kth inspection cycle, and each inspector must be assigned only once to one cycle.
(2)
I
k makes two kinds of errors: rejecting a conforming item (type I error) or accepting a nonconforming item (type II error), and type I and type II error probabilities are not variables but constants measured as (
α
k
,
β
k
). The error probabilities of inspectors are not identical. That is, (
α
i
,
β
i
)
≠
(
α
j
,
β
j
) for integers i and j, with 1
≤
i
,
j
≤
m
,
i
≠
j.
(3)
The item inspected byI
k is accepted as conforming only if the characteristic is correctly or falsely classified as conforming by I
k. Otherwise, it is rejected as nonconforming. All the items accepted by I
k are not reinspected anymore but accumulated in a specific storage area, and all the items rejected by I
k are reworked by a repairman at a constant defective rate (p).
(4)
The reworked items are sent to either the next inspection-rework cycle or the storage area only when the AOQ of all the items accumulated in the area is less than or equal toq
G. The above procedure is continued until we obtain an AOQ less than or equal to q
G.LetΨ
(
k
), represented by 〈
I
1
,
…
,
I
k
〉, be a sequence of k inspectors selected from W and assigned to k inspection cycles. Let Ψ
∗
(
k
) be the sequence with size k from W such that A
O
Q
(
Ψ
∗
(
k
)
)
≤
A
O
Q
(
Ψ
(
k
)
), where A
O
Q
Ψ is an AOQ resulting from a sequence Ψ. Now, under the assumption that 0
<
p
,
q
G
,
α
k
,
β
k
<
1, our problem can be described as follows:SP:
givenp, q
G, m, and {
(
α
k
,
β
k
)
,
k
=
1,2
,
…
,
m
} as input variables where p
>
q
G, determine both n
∗ and Ψ
∗
(
n
∗
) simultaneously, where n
∗ is the minimum number of inspection-rework cycles such that A
O
Q
(
Ψ
∗
(
n
∗
)
)
≤
q
G.Note that the total number of possible sequences will be as many as∑
k
=
1
m
(
m
k
)
k
!, where (
m
k
)
=
m
!
/
m
-
k
!
k
!, since the number of combinations of k inspectors from W is (
m
k
), and the number of permutations (or sequences) of k inspectors from a combination of k inspectors is k
!.


## 3. Analysis and Optimization of Our Inspection Problem

### 3.1. Derivation of AOQ and Properties

Suppose that a sequence with sizen is given as Ψ
(
n
)
=
〈
I
1
,
I
2
,
…
,
I
n
〉 for 1
≤
n
≤
m. For an integer k with 1
≤
k
≤
n, letG
k = expected number of conforming items entering the (k
+
1)-st inspection cycle,
B
k = expected number of nonconforming items entering the (k
+
1)-st inspection cycle,
G
G
k = expected number of items correctly accepted by I
k,
B
G
k = expected number of items falsely rejected by I
k,
G
B
k = expected number of items falsely accepted by I
k,
B
B
k = expected number of items correctly rejected by I
k,
R
k = expected number of items entering the kth rework operation,
R
0 = expected number of items entering the first cycle,
L
k = expected number of items correctly or falsely accepted by I
k.Then, for an integer k with 1
≤
k
≤
n, we have G
G
k
=
(
1
-
α
k
)
G
k
-
1, B
G
k
=
α
k
G
k
-
1, G
B
k
=
β
k
B
k
-
1, and B
B
k
=
(
1
-
β
k
)
B
k
-
1, where G
0
=
(
1
-
p
)
R
0 and B
0
=
p
R
0. Since the items classified as conforming by I
k are accumulated in a specific storage area, we have L
k
=
G
G
k
+
G
B
k and R
k
=
B
G
k
+
B
B
k. Hence, we have(1)
L
k
=
1
-
α
k
G
k
-
1
+
β
k
B
k
-
1
(2)
R
k
=
α
k
G
k
-
1
+
1
-
β
k
B
k
-
1
.After reworking at thekth rework operation, we have(3)
G
k
=
1
-
p
R
k
(4)
B
k
=
p
R
k
.After completing thekth inspection-rework cycle, since the expected number of nonconforming items in the storage area will be the sum of the expected number of items falsely accepted and the expected number of nonconforming items in the kth rework operation, A
O
Q
(
Ψ
(
k
)
) can be derived as (5)
AOQ
Ψ
k
=
1
R
0
∑
i
=
1
k
G
B
i
+
B
k
=
1
R
0
∑
i
=
1
k
β
i
B
i
-
1
+
p
R
k
.For convenience, letγ
k
=
(
1
-
p
)
α
k
+
p
(
1
-
β
k
) and Γ
k
=
∏
i
=
1
k
γ
i for 1
≤
k
≤
m. Note that γ
k can be interpreted as the probability with which I
k classifies an item as nonconforming and that 0
<
γ
k
<
1. From the four recurrence relations equations (1) through (4), the mathematical expressions for R
k, G
k, B
k, L
k, and A
O
Q
(
Ψ
(
k
)
) can be derived as closed-form solutions in the following lemma.Lemma 1.
For an integerk with 1
≤
k
≤
m, (1)
R
k
=
R
0
Γ
k,
(2)
G
k
=
(
1
-
p
)
R
0
Γ
k,
(3)
B
k
=
p
R
0
Γ
k,
(4)
(6)
L
k
=
1
-
γ
1
R
0
f
o
r
k
=
1
1
-
γ
k
R
0
Γ
k
-
1
f
o
r
2
≤
k
≤
m
,
(5)
(7)
A
O
Q
Ψ
k
=
p
β
1
+
γ
1
f
o
r
k
=
1
p
β
1
+
∑
i
=
2
k
β
i
Γ
i
-
1
+
Γ
k
f
o
r
2
≤
k
≤
m
.Proof.
Using (3) and (4), R
k can be reduced to(8)
R
k
=
α
k
G
k
-
1
+
1
-
β
k
B
k
-
1
=
α
k
1
-
p
+
1
-
β
k
p
R
k
-
1
=
γ
k
R
k
-
1
=
R
0
Γ
k
for
1
≤
k
≤
m
.Using (8), we have(9)
G
k
=
1
-
p
R
0
Γ
k
,
B
k
=
p
R
0
Γ
k
.Since 1
-
γ
1
=
(
1
-
p
)
(
1
-
α
1
)
+
p
β
1, from (1), we have (10)
L
1
=
1
-
α
1
G
0
+
β
1
B
0
=
1
-
γ
1
R
0
.Using (9), since 1
-
γ
k
=
(
1
-
p
)
(
1
-
α
k
)
+
p
β
k, we have (11)
L
k
=
1
-
α
k
G
k
-
1
+
β
k
B
k
-
1
=
1
-
p
1
-
α
k
+
p
β
k
R
0
Γ
k
-
1
=
1
-
γ
k
R
0
Γ
k
-
1
for
2
≤
k
≤
n
.Using (5), (8), and (9), we have (12)
AOQ
Ψ
1
=
1
R
0
β
1
B
0
+
p
R
1
=
p
β
1
+
γ
1
,
AOQ
Ψ
k
=
1
R
0
∑
i
=
1
k
β
i
B
i
-
1
+
p
R
k
=
p
β
1
+
∑
i
=
2
k
β
i
Γ
i
-
1
+
Γ
k
for
k
≥
2
.Example 2.
When(
R
0
,
p
,
m
) = (10,000 units, 5%, 4) and α
i
,
β
i
,
i
=
1,2
,
3,4 are given as shown in Table 1, compute A
O
Q
(
Ψ
(
2
)
) for all possible sequences of Ψ
(
2
) and find the minimum of A
O
Q
(
Ψ
(
2
)
).Table 1
Input data ofα
i
,
β
i
,
i
=
1,2
,
3,4 and (
v
i
,
λ
i
).
i
α
i (%)
β
i (%)
v
i (%)
λ
i
i
α
i (%)
β
i (%)
v
i (%)
λ
i
1
0.92
4.50
5.42
0.0454
3
0.72
4.60
5.32
0.0463
2
0.97
4.51
5.48
0.0455
4
0.85
5.18
6.03
0.0522Suppose thatΨ
(
2
)
=
〈
3
,
1
〉 is scheduled; Inspector 3 is assigned to the first inspection cycle and Inspector 1 to the second. Since G
0
=
9,500 and B
0
=
500, Inspector 3 has G
G
1
=
9,432, B
G
1
=
68, G
B
1
=
23, and B
B
1
=
477 after completion of the first inspection cycle as shown in Table 2. It follows that the number of items sent to the storage area is L
1
=
G
G
1
+
G
B
1
=
9,455 since these items have been classified as conforming by Inspector 3 even though some of them have been falsely accepted. The number of items correctly or falsely rejected by Inspector 3 is R
1
=
545 and these items are sent to the rework shop, where they are repaired with G
1
=
518 and B
1
=
27 and sent to the second inspection cycle assigned by Inspector 1. Now, since G
1
=
518 and B
1
=
27, Inspector 1 has G
G
2
=
51
3, B
G
2
=
5, G
B
2
=
1, and B
B
2
=
26 after completion of the second inspection cycle. It follows that the number of items sent to the storage area is L
2
=
G
G
2
+
G
B
2
=
51
5 since those items have been classified as conforming by Inspector 1. The number of items rejected by Inspector 1 is R
2
=
31 and these items are sent to the rework shop, where they are repaired with G
2
=
29 and B
2
=
2, and they are sent to the storage area instead of the third inspection cycle since two inspection cycles are given.Table 2
All possible sequences with size 2 and AOQs.
Ψ
(
2
)
I
1
Repair
I
2
Repair
A
O
Q
Ψ
2 (ppm)
G
G
1
B
G
1
G
B
1
B
B
1
L
1
R
1
G
1
B
1
G
G
2
B
G
2
G
B
2
B
B
2
L
2
R
2
G
2
B
2
1,2
9,413
87
23
478
9,435
565
537
28
531
5
1
27
533
32
31
2
2,538
2,1
9,408
92
23
477
9,430
570
541
28
536
5
1
27
537
32
31
2
2,544
1,3
9,413
87
23
478
9,435
565
537
28
533
4
1
27
534
31
29
2
2,534
3,1
9,432
68
23
477
9,455
545
518
27
513
5
1
26
515
31
29
2
2,577
1,4
9,413
87
23
478
9,435
565
537
28
532
5
1
27
534
31
30
2
2,553
4,1
9,419
81
26
474
9,445
555
527
28
522
5
1
26
524
31
30
2
2,872
2,3
9,408
92
23
477
9,430
570
541
28
537
4
1
27
539
31
30
2
2,541
3,2
9,432
68
23
477
9,455
545
518
27
513
5
1
26
514
31
30
2
2,578
2,4
9,408
92
23
477
9,430
570
541
28
537
5
1
27
538
32
30
2
2,561
4,2
9,419
81
26
474
9,445
555
527
28
522
5
1
26
523
32
30
2
2,873
3,4
9,432
68
23
477
9,455
545
518
27
514
4
1
26
515
30
29
2
2,593
4,3
9,419
81
26
474
9,445
555
527
28
523
4
1
26
525
30
29
2
2,869Since the total number of nonconforming items in the storage area isG
B
1
+
G
B
2
+
B
2
=
25.77, the value of A
O
Q
(
〈
3
,
1
〉
) can be computed as 2,577 ppm, which can be also computed by using Lemma 1-(5). In the similar method above, the value of AOQ for each possible sequence with size 2 can be computed and summarized in Table 2. Note that the total number of possible sequences with size 2 is 4
2
2
!
=
12 and that the sequence 〈
1,3
〉 gives the smallest AOQ (=2,534 ppm) of all possible sequences with size 2.In fact, the input data given in the example are partially extracted from the original data sets of a Korean back-light unit supplier, and, from the data sets, the averages of the type I and type II errors were estimated as 0.8641% and 4.5031%, respectively, by Yang and Cho [15].Consider the minimization problem ofA
O
Q
(
Ψ
(
1
)
). Suppose that W
i with (
α
i
,
β
i
) from a set W of m available inspectors is assigned to the single inspection cycle. Then, from Lemma 1-(5), A
O
Q
(
Ψ
(
1
)
) can be expressed as p
1
-
p
v
i
+
p
2, where v
i
=
α
i
+
β
i. Since p is constant, A
O
Q
(
Ψ
(
1
)
) is minimized if and only if the inspector with v
m
i
n
=
min
1
≤
i
≤
m
⁡
[
v
i
] is assigned to the cycle. In the above example, since v
m
i
n
=
v
3
=
5.32%, Inspector 3 must be allocated in order to attain the minimum AOQ = 5,027 ppm.Consider the minimization problem ofA
O
Q
(
Ψ
(
2
)
). This minimization problem is not as easy as the minimization problem of A
O
Q
(
Ψ
(
1
)
). However, if the first inspector has been optimally assigned, that is, Ψ
∗
(
1
)
=
〈
I
1
〉, the minimization problem of A
O
Q
(
Ψ
(
2
)
) given Ψ
∗
(
1
)
=
〈
I
1
〉 can be easily solved. When W
i with (
α
i
,
β
i
) from a set of (m
-
1) available inspectors, expressed as W
-
{
I
1
}, is assigned to the second inspection cycle, A
O
Q
(
Ψ
(
2
)
) given Ψ
∗
(
1
) can be expressed as p
{
β
1
+
γ
1
p
+
γ
1
(
1
-
p
)
v
i
} from Lemma 1-(5). Since α
1, β
1, and p are constants, A
O
Q
(
Ψ
(
2
)
) given Ψ
∗
(
1
) can be minimized if and only if the inspector with the smallest value ofv
i among W
-
{
I
1
} is assigned to the second inspection cycle. Generally, when W
i with (
α
i
,
β
i
) from W
-
{
I
1
,
I
2
,
…
,
I
n
-
1
} is assigned to the nth inspection cycle for 3
≤
n
≤
m, A
O
Q
(
Ψ
(
n
)
) given Ψ
∗
(
n
-
1
)
=
〈
I
1
,
…
,
I
n
-
1
〉 can be derived as (13)
AOQ
Ψ
n
=
AOQ
Ψ
∗
n
-
1
-
p
Γ
n
-
1
-
β
n
Γ
n
-
1
-
γ
n
Γ
n
-
1
=
AOQ
Ψ
∗
n
-
1
-
p
1
-
p
Γ
n
-
1
1
-
v
n
since
β
k
+
γ
k
=
1
-
p
v
k
+
p
=
AOQ
Ψ
∗
n
-
1
-
δ
n
,where δ
n
=
p
(
1
-
p
)
Γ
n
-
1
(
1
-
v
n
). Since A
O
Q
(
Ψ
∗
(
n
-
1
)
) and p
(
1
-
p
)
Γ
n
-
1 are constants, A
O
Q
(
Ψ
(
n
)
) given Ψ
∗
(
n
-
1
) can be minimized if and only if the inspector with v
m
i
n among W
-
{
I
1
,
…
,
I
n
-
1
} is assigned to the nth inspection cycle. For this reason, it may be likely to conjecture that the optimal solution of the minimization of A
O
Q
(
Ψ
(
n
)
) is one of v-increasing sequences. This conjecture turned out to be wrong. The counterexample can be constructed from the above example. Consider the minimization problem of A
O
Q
(
Ψ
(
2
)
). Since Ψ
∗
(
1
)
=
〈
3
〉, v
1
=
5.4
2
%, v
2
=
5.48
%, and v
4
=
6.03
%, the optimal sequence of the minimization of A
O
Q
(
Ψ
(
2
)
) given Ψ
∗
(
1
) is 〈
3,1
〉. However, the optimal sequence of the minimization of A
O
Q
(
Ψ
(
2
)
) turned out to be 〈
1
,
3
〉 instead of 〈
3
,
1
〉, where A
O
Q
(
〈
3
,
1
〉
) = 2,577 ppm > A
O
Q
(
〈
1
,
3
〉
) = 2,534 ppm as shown in Table 2.Basically the minimization ofA
O
Q
(
Ψ
(
n
)
) is different from the minimization of A
O
Q
(
Ψ
(
n
)
) given Ψ
∗
(
n
-
1
). It turns out that when n
≥
2, the optimal sequence Ψ
∗
(
n
) of the minimization of A
O
Q
(
Ψ
(
n
)
) is one of λ-increasing sequences with size n, where λ is the ratio of the type II error to one minus the type I error. In the above example, since the λ-increasing sequence with size 4 is 〈
1
,
2
,
3
,
4
〉, the λ-increasing sequences with size 2 are 〈
1,2
〉, 〈
1
,
3
〉, 〈
1
,
4
〉, 〈
2
,
3
〉, 〈
2
,
4
〉, and 〈
3
,
4
〉, and the sequence with the smallest value of AOQ of them is optimal. Since A
O
Q
(
〈
1
,
3
〉
) gives the minimum value of AOQ as shown in Table 2, Ψ
∗
(
2
) becomes 〈
1
,
3
〉. Similarly, Ψ
∗
(
3
) is the sequence with the smallest value of AOQ of the candidate solutions: 〈
1
,
2
,
3
〉, 〈
1
,
2
,
4
〉, 〈
1
,
3
,
4
〉, and 〈
2
,
3
,
4
〉. It turns out that Ψ
∗
(
3
)
=
〈
1
,
2
,
3
〉 with AOQ = 2,394 ppm.In order to prove generally thatΨ
∗
(
k
) is one of λ-increasing sequences with size k when k
≥
2, letW
i
k = a subset ofk inspectors selected from W,
C
k = a collection of subsets with size k ofW; that is, C
k
=
{
W
i
(
k
)
,
i
=
1,2
,
…
,
m
k
},
Ψ
j
(
W
i
(
k
)
) = the jth sequence or permutation generated from W
i
(
k
),
C
(
W
i
(
k
)
) = a collection of sequences with size k generated from W
i
(
k
); that is, C
(
W
i
(
k
)
)
=
{
Ψ
j
(
W
i
(
k
)
)
,
j
=
1,2
,
…
,
k
!
}.In the above example, sinceW
=
{
1
,
2
,
3
,
4
}, the collection C
(
2
) of subsets with size 2 of W becomes {
{
1
,
2
}
,
{
1
,
3
}
,
{
1
,
4
}
,
{
2
,
3
}
,
{
2
,
4
}
,
{
3
,
4
}
}. Suppose that W
2
(
2
)
=
{
1
,
3
}. Then, all possible permutations generated from W
2
2 are Ψ
1
(
W
2
(
2
)
)
=
〈
1
,
3
〉 and Ψ
2
(
W
2
(
2
)
)
=
〈
3
,
1
〉, and the collection C
(
W
2
(
2
)
) of sequences with size 2 generated from W
2
(
2
) becomes {
〈
1
,
3
〉
,
〈
3
,
1
〉
}. Using the notations above, Ψ
∗
(
k
) can be redefined as the sequence with size k from W such that (14)
AOQ
Ψ
∗
k
=
min
⁡
AOQ
Ψ
j
W
i
k
,
1
≤
i
≤
m
k
,
j
=
1,2
,
…
,
k
!
.Suppose that the number of completed inspection-rework cycles isn for n
≥
2 and that the sequence with size n is represented as Ψ
(
n
)
=
〈
I
1
,
…
,
I
k
-
1
,
I
k
,
I
k
+
1
,
I
k
+
2
,
…
,
I
n
〉. By choosing the kth and (k
+
1)-st adjacent inspectors from Ψ
(
n
) and by swapping them, we can construct the swapped sequence; Ψ
′
(
n
)
=
〈
I
1
,
…
,
I
k
-
1
,
I
k
+
1
,
I
k
,
I
k
+
2
,
…
,
I
n
〉. The AOQ of the swapped sequence A
O
Q
(
Ψ
′
(
n
)
) turned out to be smaller than A
O
Q
(
Ψ
(
n
)
), if and only if the following necessary and sufficient condition holds.Lemma 3.
A
O
Q
(
Ψ
(
n
)
)
>
A
O
Q
(
Ψ
′
(
n
)
) if and only if λ
k
>
λ
k
+
1 for 1
≤
k
≤
n
-
1 and n
≥
2, where λ
k
=
β
k
(
1
-
α
k
)
-
1.Proof.
Consider two cases as follows: Case 1 forn
=
2 and Case 2 for n
≥
3.
Case
1. When n
=
2, by swapping I
1 and I
2 and using Lemma 1-(5), A
O
Q
(
Ψ
(
2
)
) and A
O
Q
(
Ψ
′
(
2
)
) can be derived, respectively, as(15)
AOQ
Ψ
2
=
p
β
1
+
β
2
γ
1
+
γ
1
γ
2
,
AOQ
Ψ
′
2
=
p
β
2
+
β
1
γ
2
+
γ
1
γ
2
.Since 1
-
γ
k
=
(
1
-
p
)
(
1
-
α
k
)
+
p
β
k, we have(16)
AOQ
Ψ
2
-
AOQ
Ψ
′
2
=
p
β
1
1
-
γ
2
-
β
2
1
-
γ
1
=
p
1
-
p
β
1
1
-
α
2
-
1
-
p
β
2
1
-
α
1
=
p
1
-
p
1
-
α
1
1
-
α
2
λ
1
-
λ
2
.Since p
(
1
-
p
)
(
1
-
α
1
)
(
1
-
α
2
)
>
0, Lemma 3 holds when n
=
2.
Case
2. When n
≥
3, two subcases are considered as follows: Subcase 1 for k
=
1 and Subcase 2 for 2
≤
k
≤
n
-
1.
Subcase
1. For k
=
1, from Lemma 1-(5), A
O
Q
(
Ψ
(
n
)
)
-
A
O
Q
(
Ψ
′
(
n
)
) can be derived as(17)
AOQ
Ψ
n
=
p
β
1
+
β
2
γ
1
+
∑
i
=
k
+
2
n
β
i
Γ
i
-
1
+
Γ
n
AOQ
Ψ
′
n
=
p
β
2
+
β
1
γ
2
+
∑
i
=
k
+
2
n
β
i
Γ
i
-
1
+
Γ
n
AOQ
Ψ
n
-
A
O
Q
Ψ
′
n
=
p
β
1
1
-
γ
2
-
β
2
1
-
γ
1
=
p
1
-
p
1
-
α
1
1
-
α
2
λ
1
-
λ
2
.Since p
(
1
-
p
)
(
1
-
α
1
)
(
1
-
α
2
)
>
0, Lemma 3 holds when n
≥
3 and k
=
1.
Subcase
2. When 2
≤
k
≤
n
-
1, from Lemma 1-(5), A
O
Q
(
Ψ
(
n
)
)
-
A
O
Q
(
Ψ
′
(
n
)
) can be derived as (18)
AOQ
Ψ
n
=
p
β
1
+
⋯
+
β
k
-
1
Γ
k
-
2
+
β
k
Γ
k
-
1
+
β
k
+
1
γ
k
Γ
k
-
1
+
β
k
+
2
Γ
k
+
1
+
⋯
+
β
n
Γ
n
-
1
+
Γ
n
AOQ
Ψ
′
n
=
p
β
1
+
⋯
+
β
k
-
1
Γ
k
-
2
+
β
k
+
1
Γ
k
-
1
+
β
k
γ
k
+
1
Γ
k
-
1
+
β
k
+
2
Γ
k
+
1
+
⋯
+
β
n
Γ
n
-
1
+
Γ
n
AOQ
Ψ
n
-
AOQ
Ψ
′
n
=
p
Γ
k
-
1
β
k
1
-
γ
k
+
1
-
β
k
+
1
1
-
γ
k
=
p
1
-
p
Γ
k
-
1
1
-
α
k
1
-
α
k
+
1
λ
k
-
λ
k
+
1
.
Sincep
(
1
-
p
)
Γ
k
-
1
(
1
-
α
k
)
(
1
-
α
k
+
1
)
>
0, Lemma 3 holds when n
≥
3 and 2
≤
k
≤
n
-
1. Therefore, Lemma 3 holds.Lemma 4.
Forn
≥
2, Ψ
∗
(
n
) is one of λ-increasing sequences with size n.Proof.
It is enough to prove that ifΨ
∗
(
n
) is not one of λ-increasing sequences, then Ψ
∗
(
n
) does not give a minimum AOQ among a set of Ψ
(
n
). If Ψ
∗
(
n
) does not satisfy λ-increasing order, then there must exist at least two adjacent inspectors violating λ-increasing order, and, using Lemma 3, we can further reduce AOQ by swapping the adjacent inspectors. Thus, Ψ
∗
(
n
) does not give a minimum AOQ among a set of Ψ
(
n
), and Lemma 4 holds.Suppose that we takem inspectors from W in λ-increasing order. Let this ordered set be W
o, expressed as W
1
,
W
2
,
…
,
W
m. Let Ψ
o
(
n
) be the sequence with size n, constructed by taking the first n inspectors from W
o. That is, Ψ
o
n
=
〈
W
1
,
W
2
,
…
,
W
n
〉. Then, it may be conjectured that Ψ
o
n will give the minimum AOQ if the optimal number of inspection-rework cycles is known as n. However, unfortunately, this is not always true. For a counterexample, when the input data for α
k
,
β
k
,
k
=
1,2
,
3,4 are given as in Table 1 and when q
G
,
p is given as (3,000 ppm, 5%), it turns out that n
∗
=
2 and we have W
o
=
1,2
,
3,4 and Ψ
o
2
=
1,2. However, Ψ
∗
2 is not Ψ
o
2
=
1,2 but 1,3 since A
O
Q
Ψ
o
2
=
2,538 ppm > A
O
Q
1,3 = 2,534 ppm as shown in Table 2.Note thatΨ
∗
n is not Ψ
o
n but one of λ-increasing sequences with size n out of m available inspectors. Also note that if all inspection error probabilities are zero, that is, (
α
i
,
β
i
)
=
0,0 for all i, then A
O
Q
Ψ
k converges to zero, since A
O
Q
Ψ
k can be reduced to p
k
+
1. If α
i
,
β
i
=
1,1 for all i, then A
O
Q
Ψ
k converges to one, since A
O
Q
Ψ
k can be reduced to 1
-
1
-
p
k
+
1. From the results, it can be said that our RIS does not always guarantee that A
O
Q
Ψ
k is a decreasing function of k. However, as proved in the following two lemmas, ifΨ
n
-
1 is given, we can construct Ψ
n such that A
O
Q
Ψ
n
<
A
O
Q
Ψ
n
-
1 by selecting the nth inspector with v
n
<
1. Similarly, if Ψ
∗
n
-
1 is given, we can construct Ψ
∗
n such that A
O
Q
Ψ
∗
n
<
A
O
Q
Ψ
∗
n
-
1 by selecting the nth inspector with v
n
<
1. Hence, A
O
Q
Ψ
∗
n can be a strictly decreasing function of n.Lemma 5.
For1
≤
n
≤
m, A
O
Q
Ψ
n
<
A
O
Q
Ψ
n
-
1 if and only if v
n
<
1, where A
O
Q
Ψ
0
=
p.Proof.
Sinceβ
k
+
γ
k
=
1
-
p
α
k
+
β
k
+
p, we have(19)
p
-
AOQ
Ψ
1
=
p
1
-
β
1
+
γ
1
=
p
1
-
p
1
-
α
1
-
β
1
.Since p
1
-
p
>
0, Lemma 5 holds when n
=
1. When 2
≤
n
≤
m, by using Lemma 1-(5), we have (20)
AOQ
Ψ
n
-
1
-
AOQ
Ψ
n
=
p
1
-
p
Γ
n
-
1
1
-
v
n
.Since p
1
-
p
Γ
n
-
1
>
0, Lemma 5 holds when 2
≤
n
≤
m. Therefore Lemma 5 holds.Lemma 6.
For1
≤
n
≤
m, A
O
Q
Ψ
∗
n
<
A
O
Q
Ψ
∗
n
-
1 if and only if v
n
<
1, where A
O
Q
Ψ
∗
0
=
p.Proof.
IfΨ
∗
n
-
1 is given for an integer with 1
≤
n
≤
m and if v
n
<
1, we can construct Ψ
n using Lemma 5 such that A
O
Q
Ψ
n
<
A
O
Q
Ψ
∗
n
-
1 by assigning the inspector I
n with v
n
<
1. Since A
O
Q
Ψ
∗
n
≤
A
O
Q
Ψ
n by definition, it follows that A
O
Q
Ψ
∗
n
<
A
O
Q
Ψ
∗
n
-
1. Reversely, if A
O
Q
Ψ
∗
n
<
A
O
Q
Ψ
∗
n
-
1, then, from Lemma 5, there exists I
n with v
n
<
1.It remains whether or not an inspector withα
n
,
β
n satisfying v
n
<
1 exists among unassigned inspectors of the set W. However, since v
n do not exceed 100% in most practical cases, we assume hereafter that v
i
<
1 for 1
≤
n
≤
m.


### 3.2. An Optimal Algorithm

Using the previously proven properties, we can construct an optimal algorithm, ALGSP, for determining bothn
∗ and Ψ
∗
n
∗ simultaneously. Our algorithm consists of three phases: an initialization phase, a local optimization phase, and a global optimization phase. In the initialization phase, in order to reduce the computational execution time in the local optimization phase, we construct the λ-increasing set W
o from W. Without loss of generality, let W
o be 1,2
,
…
,
m.In the local optimization phase, we findΨ
∗
n for 1
≤
n
≤
m. Let Ψ
W
i
k be the λ-increasing sequence with size k generated from a given ordered combination, W
i
k, such that A
O
Q
Ψ
W
i
k
=
min
⁡
A
O
Q
Ψ
j
W
i
k
,
1
≤
j
≤
k
!. For example, if W
i
k is given as W
1
,
W
2
,
…
,
W
k, then Ψ
W
i
k can be immediately obtained as I
1
,
I
2
,
…
,
I
k, where W
i
=
I
i for 1
≤
i
≤
k. In the local optimization phase, given k, we construct Ψ
W
i
k from W
i
k using W
o. Next, from Ψ
W
i
k, we find the sequence Ψ
∗
k such that A
O
Q
Ψ
∗
k
=
min
⁡
A
O
Q
Ψ
W
i
k
,
1
≤
i
≤
m
k. In the outer loop, changing k from one to m, we store a set of the local optimal sequences, Ψ
∗
k
,
k
=
1,2
,
…
,
m. In the global optimization phase, we search for n
∗ satisfying A
O
Q
Ψ
∗
n
∗
≤
q
G. If n
∗ is not found, we terminate our algorithm with a message “n
∗
←
g
r
e
a
t
e
r
t
h
a
n
m.” See Algorithm 1.Algorithm 1:ALGSP.
Step  1 (Initialization Phase):
Take inspectors inλ-increasing order using α
i
,
β
i
,
i
=
1,2
,
…
,
m and let this ordered set be W
o
←
1,2
,
…
,
m.
Step  2 (Local Optimization Phase)
Fork
=
1 to m do
Begin
Fori
=
1 to   m
k
Begin
min
⁡
←
1
Begin
ConstructW
i
k and Ψ
W
i
k
ComputeAOQ
Ψ
W
i
k using Lemma 1(5).
IfAOQ
Ψ
W
i
k
≤ min, then Ψ
∗
k
←
Ψ
W
i
k,
AOQ
Ψ
∗
k
←
A
O
Q
Ψ
W
i
k, min
⁡
←
A
O
Q
Ψ
W
i
k
End
End
End
Step  3 (Global Optimization Phase)
Forn
=
1 to m do
Begin
If(
AOQ
Ψ
∗
n
≤
q
G
), then n
∗
←
n, Ψ
∗
n
∗
←
Ψ
∗
n, AOQ
Ψ
∗
n
∗
←
A
O
Q
Ψ
∗
n
If(
AOQ
Ψ
∗
n
>
q
G and n
=
m
), then print “n
∗
← greater than m” and stop
EndTheorem 7.
Ψ
∗
(
n
∗
) determined by ALGSP is an optimal sequence to SP.Proof.
A
O
Q
Ψ
∗
n is a decreasing function of n from Lemma 6, and n
∗ determined by ALGSP is the smallest number of inspection-rework cycles such that A
O
Q
(
Ψ
∗
(
n
∗
)
)
≤
q
G. Hence, Ψ
∗
(
n
∗
) determined by ALGSP is an optimal sequence to SP.Theorem 8.
ALGSP solves SP inO
(
2
m
).Proof.
From Theorem7, Ψ
∗
n
∗ gives an optimal solution to SP. Steps 1 and 3 require O
(
n
log
⁡
n
) and O
(
m
), respectively. Step 2 requires O
(
2
m
), since Ψ
∗
k can be obtained by enumerating not all the permutations but all the combinations of k inspectors from W; that is, ∑
k
=
1
m
m
k
=
2
m
-
1. Hence, ALGSP solves SP in O
(
2
m
).Even though the time complexity of ALGSP isO
(
2
m
), our algorithm is practically efficient since the optimal number of inspection-rework cycles is usually less than five cycles in most practical cases.


### 3.3. A Numerical Example

Suppose that(
q
G
,
p
,
m
) = (2,500 ppm, 5%, 4) and that α
k
,
β
k
,
k
=
1,2
,
3,4 are given as shown in Table 1. Using ALGSP, the optimal solution to our example will be obtained as follows.Step 1.
Theλ-increasing sequence is 1,2
,
3,4 and W
o
←
{
1,2
,
3,4
}.Step 2.
As shown in Table3, when n
=
1, we generate four sequences I
1 for 1
≤
I
1
≤
4, and we have Ψ
∗
1
=
3 (or W
3) with A
O
Q
Ψ
∗
1
=
5,027 ppm. When n
=
2, we generate six sequences I
1
,
I
2 where I
1
,
I
2 is obtained by finding the combinations of two inspectors from W
o, and we have Ψ
∗
2
=
1,3 with A
O
Q
Ψ
∗
2
=
2,534 ppm. When n
=
3, we generate four sequences I
1
,
I
2
,
I
3 obtained by finding the combinations of three inspectors from W
o, and we have Ψ
∗
3
=
1,2
,
3 with A
O
Q
Ψ
∗
3
=
2,394 ppm. When n
=
4, we generate one sequence 1,2
,
3,4, which is the only λ-increasing sequence, and we have Ψ
∗
4
=
1,2
,
3,4 with A
O
Q
Ψ
∗
4
=
2,386 ppm. After Step 2, Ψ
∗
n and A
O
Q
Ψ
∗
n for 1
≤
n
≤
4 can be obtained as summarized in Table 4.Table 3
The changing values in Step2.
k
i
W
i
(
k
)
Ψ
(
W
i
k
)
AOQ
(
Ψ
(
W
i
k
)
)
Ψ
∗
(
k
)
AOQ
(
Ψ
∗
(
k
)
)
1
1
W
1
(
1
)
=
{
1
}
1
5075
1
5075
2
W
2
(
1
)
=
{
2
}
2
5103
1
5075
3
W
3
(
1
)
=
{
3
}
3
5027
3
5027
4
W
4
(
1
)
=
{
4
}
4
5364
3
5027
2
1
W
1
(
2
)
=
{
1,2
}
1,2
2538
1,2
2538
2
W
2
(
2
)
=
{
1,3
}
1,3
2534
1,3
2534
3
W
3
(
2
)
=
{
1,4
}
1,4
2553
1,3
2534
4
W
4
(
2
)
=
{
2,3
}
2,3
2541
1,3
2534
5
W
5
(
2
)
=
{
2,4
}
2,4
2561
1,3
2534
6
W
6
(
2
)
=
{
3,4
}
3,4
2593
1,3
2534
3
1
W
1
(
3
)
=
{
1,2
,
3
}
1,2
,
3
2394
1,2
,
3
2394
2
W
2
(
3
)
=
{
1,2
,
4
}
1,2
,
4
2395
1,2
,
4
2394
3
W
3
(
3
)
=
{
1,3
,
4
}
1,3
,
4
2396
1,3
,
4
2394
4
W
4
(
3
)
=
{
2,3
,
4
}
2,3
,
4
2403
1,3
,
4
2394
4
1
W
1
(
4
)
=
{
1,2
,
3,4
}
1,2
,
3,4
2386
1,2
,
3,4
2386Table 4
Ψ
∗
k and AOQ
(
Ψ
∗
k
), which resulted from Step 2.
k
Ψ
∗
(
k
)
AOQ
(
Ψ
∗
(
k
)
)
1
3
5027
2
1,3
2534
3
1,2
,
3
2394
4
1,2
,
3,4
2386Step 3.
SinceA
O
Q
Ψ
∗
2
=
2,534 ppm > q
G
=
2,500 ppm > A
O
Q
Ψ
∗
3
=
2,394 ppm, ALGSP terminates with n
∗
=
3 and Ψ
∗
3
=
1,2
,
3.For the reader’s convenience, we have included the computational results of all the possible sequences generated from the set{
1,2
,
3,4
} in Tables 5, 6, and 7.Table 5
W
i
2, Ψ
j
W
i
2, and AOQ
Ψ
j
W
i
2 when n
=
2.
W
i
(
2
)
Ψ
j
(
W
i
(
2
)
)
AOQ
(
Ψ
j
(
W
i
(
2
)
)
)
W
i
(
2
)
Ψ
j
(
W
i
(
2
)
)
AOQ
(
Ψ
j
(
W
i
(
2
)
)
)
W
1
(
2
)
=
{
1
,
2
}
Ψ
1
W
1
2
=
1,2
2538
W
4
(
2
)
=
{
2,3
}
Ψ
1
W
4
2
=
2,3
2541
Ψ
2
W
1
2
=
2,1
2544
Ψ
2
W
4
2
=
3,2
2578
W
2
(
2
)
=
{
1,3
}
Ψ
1
W
2
2
=
1,3
2534
W
5
(
2
)
=
{
2,4
}
Ψ
1
W
5
2
=
2,4
2561
Ψ
2
W
2
2
=
3,1
2577
Ψ
2
W
5
2
=
4,2
2873
W
3
(
2
)
=
{
1,4
}
Ψ
1
W
3
2
=
1,4
2553
W
6
(
2
)
=
{
3,4
}
Ψ
1
W
6
2
=
3,4
2593
Ψ
2
W
3
2
=
4,1
2872
Ψ
2
W
6
2
=
4,3
2869Table 6
W
i
3, Ψ
j
W
i
3, and AOQ
Ψ
j
W
i
3 when n
=
3.
W
i
(
3
)
Ψ
j
(
W
i
(
3
)
)
AOQ
(
Ψ
j
(
W
i
(
3
)
)
)
W
i
(
3
)
Ψ
j
(
W
i
(
3
)
)
AOQ
(
Ψ
j
(
W
i
(
3
)
)
)
W
1
(
3
)
=
{
1,2
,
3
}
Ψ
1
W
1
3
=
1,2
,
3
2394
W
3
(
3
)
=
{
1,3
,
4
}
Ψ
1
W
3
3
=
1,3
,
4
2396
Ψ
2
W
1
3
=
1,3
,
2
2396
Ψ
2
W
3
3
=
1,4
,
3
2412
Ψ
3
W
1
3
=
2,1
,
3
2399
Ψ
3
W
3
3
=
3,1
,
4
2439
Ψ
4
W
1
3
=
2,3
,
1
2402
Ψ
4
W
3
3
=
3,4
,
1
2457
Ψ
5
W
1
3
=
3,1
,
2
2438
Ψ
5
W
3
3
=
4,1
,
3
2731
Ψ
6
W
1
3
=
3,2
,
1
2439
Ψ
6
W
3
3
=
4,3
,
1
2733
W
2
(
3
)
=
{
1,2
,
4
}
Ψ
1
W
2
3
=
1,2
,
4
2395
W
4
(
3
)
=
{
2,3
,
4
}
Ψ
1
W
4
3
=
2,3
,
4
2403
Ψ
2
W
2
3
=
1,4
,
2
2412
Ψ
2
W
4
3
=
2,4
,
3
2418
Ψ
3
W
2
3
=
2,1
,
4
2400
Ψ
3
W
4
3
=
3,2
,
4
2440
Ψ
4
W
2
3
=
2,4
,
1
2419
Ψ
4
W
4
3
=
3,4
,
2
2457
Ψ
5
W
2
3
=
4,1
,
2
2731
Ψ
5
W
4
3
=
4,2
,
3
2731
Ψ
6
W
2
3
=
4,2
,
1
2731
Ψ
6
W
4
3
=
4,3
,
2
2733Table 7
W
i
4, Ψ
j
W
i
4, and AOQ
Ψ
j
W
i
4 when n
=
4.
W
i
(
4
)
Ψ
j
(
W
i
(
4
)
)
AOQ
(
Ψ
j
(
W
i
(
4
)
)
)
W
i
(
4
)
Ψ
j
(
W
i
(
4
)
)
AOQ
(
Ψ
j
(
W
i
(
4
)
)
)
W
1
(
4
)
=
{
1,2
,
3,4
}
Ψ
1
W
1
4
=
1,2
,
3,4
2386
W
1
(
4
)
=
{
1,2
,
3,4
}
Ψ
13
W
1
4
=
3,1
,
2,4
2431
Ψ
2
W
1
4
=
1,2
,
4,3
2387
Ψ
14
W
1
4
=
3,1
,
4,2
2432
Ψ
3
W
1
4
=
1,3
,
2,4
2388
Ψ
15
W
1
4
=
3,2
,
1,4
2431
Ψ
4
W
1
4
=
1,3
,
4,2
2389
Ψ
16
W
1
4
=
3,2
,
4,1
2432
Ψ
5
W
1
4
=
1,4
,
2,3
2404
Ψ
17
W
1
4
=
3,4
,
1,2
2449
Ψ
6
W
1
4
=
1,4
,
3,2
2404
Ψ
18
W
1
4
=
3,4
,
2,1
2449
Ψ
7
W
1
4
=
2,1
,
3,4
2392
Ψ
19
W
1
4
=
4,1
,
2,3
2723
Ψ
8
W
1
4
=
2,1
,
4,3
2392
Ψ
20
W
1
4
=
4,1
,
3,2
2723
Ψ
9
W
1
4
=
2,3
,
1,4
2394
Ψ
21
W
1
4
=
4,2
,
1,3
2723
Ψ
10
W
1
4
=
2,3
,
4,1
2395
Ψ
22
W
1
4
=
4,2
,
3,1
2723
Ψ
11
W
1
4
=
2,4
,
1,3
2411
Ψ
23
W
1
4
=
4,3
,
1,2
2725
Ψ
12
W
1
4
=
2,4
,
3,1
2411
Ψ
24
W
1
4
=
4,3
,
2,1
2725


## 3.1. Derivation of AOQ and Properties

Suppose that a sequence with sizen is given as Ψ
(
n
)
=
〈
I
1
,
I
2
,
…
,
I
n
〉 for 1
≤
n
≤
m. For an integer k with 1
≤
k
≤
n, letG
k = expected number of conforming items entering the (k
+
1)-st inspection cycle,
B
k = expected number of nonconforming items entering the (k
+
1)-st inspection cycle,
G
G
k = expected number of items correctly accepted by I
k,
B
G
k = expected number of items falsely rejected by I
k,
G
B
k = expected number of items falsely accepted by I
k,
B
B
k = expected number of items correctly rejected by I
k,
R
k = expected number of items entering the kth rework operation,
R
0 = expected number of items entering the first cycle,
L
k = expected number of items correctly or falsely accepted by I
k.Then, for an integer k with 1
≤
k
≤
n, we have G
G
k
=
(
1
-
α
k
)
G
k
-
1, B
G
k
=
α
k
G
k
-
1, G
B
k
=
β
k
B
k
-
1, and B
B
k
=
(
1
-
β
k
)
B
k
-
1, where G
0
=
(
1
-
p
)
R
0 and B
0
=
p
R
0. Since the items classified as conforming by I
k are accumulated in a specific storage area, we have L
k
=
G
G
k
+
G
B
k and R
k
=
B
G
k
+
B
B
k. Hence, we have(1)
L
k
=
1
-
α
k
G
k
-
1
+
β
k
B
k
-
1
(2)
R
k
=
α
k
G
k
-
1
+
1
-
β
k
B
k
-
1
.After reworking at thekth rework operation, we have(3)
G
k
=
1
-
p
R
k
(4)
B
k
=
p
R
k
.After completing thekth inspection-rework cycle, since the expected number of nonconforming items in the storage area will be the sum of the expected number of items falsely accepted and the expected number of nonconforming items in the kth rework operation, A
O
Q
(
Ψ
(
k
)
) can be derived as (5)
AOQ
Ψ
k
=
1
R
0
∑
i
=
1
k
G
B
i
+
B
k
=
1
R
0
∑
i
=
1
k
β
i
B
i
-
1
+
p
R
k
.For convenience, letγ
k
=
(
1
-
p
)
α
k
+
p
(
1
-
β
k
) and Γ
k
=
∏
i
=
1
k
γ
i for 1
≤
k
≤
m. Note that γ
k can be interpreted as the probability with which I
k classifies an item as nonconforming and that 0
<
γ
k
<
1. From the four recurrence relations equations (1) through (4), the mathematical expressions for R
k, G
k, B
k, L
k, and A
O
Q
(
Ψ
(
k
)
) can be derived as closed-form solutions in the following lemma.Lemma 1.
For an integerk with 1
≤
k
≤
m, (1)
R
k
=
R
0
Γ
k,
(2)
G
k
=
(
1
-
p
)
R
0
Γ
k,
(3)
B
k
=
p
R
0
Γ
k,
(4)
(6)
L
k
=
1
-
γ
1
R
0
f
o
r
k
=
1
1
-
γ
k
R
0
Γ
k
-
1
f
o
r
2
≤
k
≤
m
,
(5)
(7)
A
O
Q
Ψ
k
=
p
β
1
+
γ
1
f
o
r
k
=
1
p
β
1
+
∑
i
=
2
k
β
i
Γ
i
-
1
+
Γ
k
f
o
r
2
≤
k
≤
m
.Proof.
Using (3) and (4), R
k can be reduced to(8)
R
k
=
α
k
G
k
-
1
+
1
-
β
k
B
k
-
1
=
α
k
1
-
p
+
1
-
β
k
p
R
k
-
1
=
γ
k
R
k
-
1
=
R
0
Γ
k
for
1
≤
k
≤
m
.Using (8), we have(9)
G
k
=
1
-
p
R
0
Γ
k
,
B
k
=
p
R
0
Γ
k
.Since 1
-
γ
1
=
(
1
-
p
)
(
1
-
α
1
)
+
p
β
1, from (1), we have (10)
L
1
=
1
-
α
1
G
0
+
β
1
B
0
=
1
-
γ
1
R
0
.Using (9), since 1
-
γ
k
=
(
1
-
p
)
(
1
-
α
k
)
+
p
β
k, we have (11)
L
k
=
1
-
α
k
G
k
-
1
+
β
k
B
k
-
1
=
1
-
p
1
-
α
k
+
p
β
k
R
0
Γ
k
-
1
=
1
-
γ
k
R
0
Γ
k
-
1
for
2
≤
k
≤
n
.Using (5), (8), and (9), we have (12)
AOQ
Ψ
1
=
1
R
0
β
1
B
0
+
p
R
1
=
p
β
1
+
γ
1
,
AOQ
Ψ
k
=
1
R
0
∑
i
=
1
k
β
i
B
i
-
1
+
p
R
k
=
p
β
1
+
∑
i
=
2
k
β
i
Γ
i
-
1
+
Γ
k
for
k
≥
2
.Example 2.
When(
R
0
,
p
,
m
) = (10,000 units, 5%, 4) and α
i
,
β
i
,
i
=
1,2
,
3,4 are given as shown in Table 1, compute A
O
Q
(
Ψ
(
2
)
) for all possible sequences of Ψ
(
2
) and find the minimum of A
O
Q
(
Ψ
(
2
)
).Table 1
Input data ofα
i
,
β
i
,
i
=
1,2
,
3,4 and (
v
i
,
λ
i
).
i
α
i (%)
β
i (%)
v
i (%)
λ
i
i
α
i (%)
β
i (%)
v
i (%)
λ
i
1
0.92
4.50
5.42
0.0454
3
0.72
4.60
5.32
0.0463
2
0.97
4.51
5.48
0.0455
4
0.85
5.18
6.03
0.0522Suppose thatΨ
(
2
)
=
〈
3
,
1
〉 is scheduled; Inspector 3 is assigned to the first inspection cycle and Inspector 1 to the second. Since G
0
=
9,500 and B
0
=
500, Inspector 3 has G
G
1
=
9,432, B
G
1
=
68, G
B
1
=
23, and B
B
1
=
477 after completion of the first inspection cycle as shown in Table 2. It follows that the number of items sent to the storage area is L
1
=
G
G
1
+
G
B
1
=
9,455 since these items have been classified as conforming by Inspector 3 even though some of them have been falsely accepted. The number of items correctly or falsely rejected by Inspector 3 is R
1
=
545 and these items are sent to the rework shop, where they are repaired with G
1
=
518 and B
1
=
27 and sent to the second inspection cycle assigned by Inspector 1. Now, since G
1
=
518 and B
1
=
27, Inspector 1 has G
G
2
=
51
3, B
G
2
=
5, G
B
2
=
1, and B
B
2
=
26 after completion of the second inspection cycle. It follows that the number of items sent to the storage area is L
2
=
G
G
2
+
G
B
2
=
51
5 since those items have been classified as conforming by Inspector 1. The number of items rejected by Inspector 1 is R
2
=
31 and these items are sent to the rework shop, where they are repaired with G
2
=
29 and B
2
=
2, and they are sent to the storage area instead of the third inspection cycle since two inspection cycles are given.Table 2
All possible sequences with size 2 and AOQs.
Ψ
(
2
)
I
1
Repair
I
2
Repair
A
O
Q
Ψ
2 (ppm)
G
G
1
B
G
1
G
B
1
B
B
1
L
1
R
1
G
1
B
1
G
G
2
B
G
2
G
B
2
B
B
2
L
2
R
2
G
2
B
2
1,2
9,413
87
23
478
9,435
565
537
28
531
5
1
27
533
32
31
2
2,538
2,1
9,408
92
23
477
9,430
570
541
28
536
5
1
27
537
32
31
2
2,544
1,3
9,413
87
23
478
9,435
565
537
28
533
4
1
27
534
31
29
2
2,534
3,1
9,432
68
23
477
9,455
545
518
27
513
5
1
26
515
31
29
2
2,577
1,4
9,413
87
23
478
9,435
565
537
28
532
5
1
27
534
31
30
2
2,553
4,1
9,419
81
26
474
9,445
555
527
28
522
5
1
26
524
31
30
2
2,872
2,3
9,408
92
23
477
9,430
570
541
28
537
4
1
27
539
31
30
2
2,541
3,2
9,432
68
23
477
9,455
545
518
27
513
5
1
26
514
31
30
2
2,578
2,4
9,408
92
23
477
9,430
570
541
28
537
5
1
27
538
32
30
2
2,561
4,2
9,419
81
26
474
9,445
555
527
28
522
5
1
26
523
32
30
2
2,873
3,4
9,432
68
23
477
9,455
545
518
27
514
4
1
26
515
30
29
2
2,593
4,3
9,419
81
26
474
9,445
555
527
28
523
4
1
26
525
30
29
2
2,869Since the total number of nonconforming items in the storage area isG
B
1
+
G
B
2
+
B
2
=
25.77, the value of A
O
Q
(
〈
3
,
1
〉
) can be computed as 2,577 ppm, which can be also computed by using Lemma 1-(5). In the similar method above, the value of AOQ for each possible sequence with size 2 can be computed and summarized in Table 2. Note that the total number of possible sequences with size 2 is 4
2
2
!
=
12 and that the sequence 〈
1,3
〉 gives the smallest AOQ (=2,534 ppm) of all possible sequences with size 2.In fact, the input data given in the example are partially extracted from the original data sets of a Korean back-light unit supplier, and, from the data sets, the averages of the type I and type II errors were estimated as 0.8641% and 4.5031%, respectively, by Yang and Cho [15].Consider the minimization problem ofA
O
Q
(
Ψ
(
1
)
). Suppose that W
i with (
α
i
,
β
i
) from a set W of m available inspectors is assigned to the single inspection cycle. Then, from Lemma 1-(5), A
O
Q
(
Ψ
(
1
)
) can be expressed as p
1
-
p
v
i
+
p
2, where v
i
=
α
i
+
β
i. Since p is constant, A
O
Q
(
Ψ
(
1
)
) is minimized if and only if the inspector with v
m
i
n
=
min
1
≤
i
≤
m
⁡
[
v
i
] is assigned to the cycle. In the above example, since v
m
i
n
=
v
3
=
5.32%, Inspector 3 must be allocated in order to attain the minimum AOQ = 5,027 ppm.Consider the minimization problem ofA
O
Q
(
Ψ
(
2
)
). This minimization problem is not as easy as the minimization problem of A
O
Q
(
Ψ
(
1
)
). However, if the first inspector has been optimally assigned, that is, Ψ
∗
(
1
)
=
〈
I
1
〉, the minimization problem of A
O
Q
(
Ψ
(
2
)
) given Ψ
∗
(
1
)
=
〈
I
1
〉 can be easily solved. When W
i with (
α
i
,
β
i
) from a set of (m
-
1) available inspectors, expressed as W
-
{
I
1
}, is assigned to the second inspection cycle, A
O
Q
(
Ψ
(
2
)
) given Ψ
∗
(
1
) can be expressed as p
{
β
1
+
γ
1
p
+
γ
1
(
1
-
p
)
v
i
} from Lemma 1-(5). Since α
1, β
1, and p are constants, A
O
Q
(
Ψ
(
2
)
) given Ψ
∗
(
1
) can be minimized if and only if the inspector with the smallest value ofv
i among W
-
{
I
1
} is assigned to the second inspection cycle. Generally, when W
i with (
α
i
,
β
i
) from W
-
{
I
1
,
I
2
,
…
,
I
n
-
1
} is assigned to the nth inspection cycle for 3
≤
n
≤
m, A
O
Q
(
Ψ
(
n
)
) given Ψ
∗
(
n
-
1
)
=
〈
I
1
,
…
,
I
n
-
1
〉 can be derived as (13)
AOQ
Ψ
n
=
AOQ
Ψ
∗
n
-
1
-
p
Γ
n
-
1
-
β
n
Γ
n
-
1
-
γ
n
Γ
n
-
1
=
AOQ
Ψ
∗
n
-
1
-
p
1
-
p
Γ
n
-
1
1
-
v
n
since
β
k
+
γ
k
=
1
-
p
v
k
+
p
=
AOQ
Ψ
∗
n
-
1
-
δ
n
,where δ
n
=
p
(
1
-
p
)
Γ
n
-
1
(
1
-
v
n
). Since A
O
Q
(
Ψ
∗
(
n
-
1
)
) and p
(
1
-
p
)
Γ
n
-
1 are constants, A
O
Q
(
Ψ
(
n
)
) given Ψ
∗
(
n
-
1
) can be minimized if and only if the inspector with v
m
i
n among W
-
{
I
1
,
…
,
I
n
-
1
} is assigned to the nth inspection cycle. For this reason, it may be likely to conjecture that the optimal solution of the minimization of A
O
Q
(
Ψ
(
n
)
) is one of v-increasing sequences. This conjecture turned out to be wrong. The counterexample can be constructed from the above example. Consider the minimization problem of A
O
Q
(
Ψ
(
2
)
). Since Ψ
∗
(
1
)
=
〈
3
〉, v
1
=
5.4
2
%, v
2
=
5.48
%, and v
4
=
6.03
%, the optimal sequence of the minimization of A
O
Q
(
Ψ
(
2
)
) given Ψ
∗
(
1
) is 〈
3,1
〉. However, the optimal sequence of the minimization of A
O
Q
(
Ψ
(
2
)
) turned out to be 〈
1
,
3
〉 instead of 〈
3
,
1
〉, where A
O
Q
(
〈
3
,
1
〉
) = 2,577 ppm > A
O
Q
(
〈
1
,
3
〉
) = 2,534 ppm as shown in Table 2.Basically the minimization ofA
O
Q
(
Ψ
(
n
)
) is different from the minimization of A
O
Q
(
Ψ
(
n
)
) given Ψ
∗
(
n
-
1
). It turns out that when n
≥
2, the optimal sequence Ψ
∗
(
n
) of the minimization of A
O
Q
(
Ψ
(
n
)
) is one of λ-increasing sequences with size n, where λ is the ratio of the type II error to one minus the type I error. In the above example, since the λ-increasing sequence with size 4 is 〈
1
,
2
,
3
,
4
〉, the λ-increasing sequences with size 2 are 〈
1,2
〉, 〈
1
,
3
〉, 〈
1
,
4
〉, 〈
2
,
3
〉, 〈
2
,
4
〉, and 〈
3
,
4
〉, and the sequence with the smallest value of AOQ of them is optimal. Since A
O
Q
(
〈
1
,
3
〉
) gives the minimum value of AOQ as shown in Table 2, Ψ
∗
(
2
) becomes 〈
1
,
3
〉. Similarly, Ψ
∗
(
3
) is the sequence with the smallest value of AOQ of the candidate solutions: 〈
1
,
2
,
3
〉, 〈
1
,
2
,
4
〉, 〈
1
,
3
,
4
〉, and 〈
2
,
3
,
4
〉. It turns out that Ψ
∗
(
3
)
=
〈
1
,
2
,
3
〉 with AOQ = 2,394 ppm.In order to prove generally thatΨ
∗
(
k
) is one of λ-increasing sequences with size k when k
≥
2, letW
i
k = a subset ofk inspectors selected from W,
C
k = a collection of subsets with size k ofW; that is, C
k
=
{
W
i
(
k
)
,
i
=
1,2
,
…
,
m
k
},
Ψ
j
(
W
i
(
k
)
) = the jth sequence or permutation generated from W
i
(
k
),
C
(
W
i
(
k
)
) = a collection of sequences with size k generated from W
i
(
k
); that is, C
(
W
i
(
k
)
)
=
{
Ψ
j
(
W
i
(
k
)
)
,
j
=
1,2
,
…
,
k
!
}.In the above example, sinceW
=
{
1
,
2
,
3
,
4
}, the collection C
(
2
) of subsets with size 2 of W becomes {
{
1
,
2
}
,
{
1
,
3
}
,
{
1
,
4
}
,
{
2
,
3
}
,
{
2
,
4
}
,
{
3
,
4
}
}. Suppose that W
2
(
2
)
=
{
1
,
3
}. Then, all possible permutations generated from W
2
2 are Ψ
1
(
W
2
(
2
)
)
=
〈
1
,
3
〉 and Ψ
2
(
W
2
(
2
)
)
=
〈
3
,
1
〉, and the collection C
(
W
2
(
2
)
) of sequences with size 2 generated from W
2
(
2
) becomes {
〈
1
,
3
〉
,
〈
3
,
1
〉
}. Using the notations above, Ψ
∗
(
k
) can be redefined as the sequence with size k from W such that (14)
AOQ
Ψ
∗
k
=
min
⁡
AOQ
Ψ
j
W
i
k
,
1
≤
i
≤
m
k
,
j
=
1,2
,
…
,
k
!
.Suppose that the number of completed inspection-rework cycles isn for n
≥
2 and that the sequence with size n is represented as Ψ
(
n
)
=
〈
I
1
,
…
,
I
k
-
1
,
I
k
,
I
k
+
1
,
I
k
+
2
,
…
,
I
n
〉. By choosing the kth and (k
+
1)-st adjacent inspectors from Ψ
(
n
) and by swapping them, we can construct the swapped sequence; Ψ
′
(
n
)
=
〈
I
1
,
…
,
I
k
-
1
,
I
k
+
1
,
I
k
,
I
k
+
2
,
…
,
I
n
〉. The AOQ of the swapped sequence A
O
Q
(
Ψ
′
(
n
)
) turned out to be smaller than A
O
Q
(
Ψ
(
n
)
), if and only if the following necessary and sufficient condition holds.Lemma 3.
A
O
Q
(
Ψ
(
n
)
)
>
A
O
Q
(
Ψ
′
(
n
)
) if and only if λ
k
>
λ
k
+
1 for 1
≤
k
≤
n
-
1 and n
≥
2, where λ
k
=
β
k
(
1
-
α
k
)
-
1.Proof.
Consider two cases as follows: Case 1 forn
=
2 and Case 2 for n
≥
3.
Case
1. When n
=
2, by swapping I
1 and I
2 and using Lemma 1-(5), A
O
Q
(
Ψ
(
2
)
) and A
O
Q
(
Ψ
′
(
2
)
) can be derived, respectively, as(15)
AOQ
Ψ
2
=
p
β
1
+
β
2
γ
1
+
γ
1
γ
2
,
AOQ
Ψ
′
2
=
p
β
2
+
β
1
γ
2
+
γ
1
γ
2
.Since 1
-
γ
k
=
(
1
-
p
)
(
1
-
α
k
)
+
p
β
k, we have(16)
AOQ
Ψ
2
-
AOQ
Ψ
′
2
=
p
β
1
1
-
γ
2
-
β
2
1
-
γ
1
=
p
1
-
p
β
1
1
-
α
2
-
1
-
p
β
2
1
-
α
1
=
p
1
-
p
1
-
α
1
1
-
α
2
λ
1
-
λ
2
.Since p
(
1
-
p
)
(
1
-
α
1
)
(
1
-
α
2
)
>
0, Lemma 3 holds when n
=
2.
Case
2. When n
≥
3, two subcases are considered as follows: Subcase 1 for k
=
1 and Subcase 2 for 2
≤
k
≤
n
-
1.
Subcase
1. For k
=
1, from Lemma 1-(5), A
O
Q
(
Ψ
(
n
)
)
-
A
O
Q
(
Ψ
′
(
n
)
) can be derived as(17)
AOQ
Ψ
n
=
p
β
1
+
β
2
γ
1
+
∑
i
=
k
+
2
n
β
i
Γ
i
-
1
+
Γ
n
AOQ
Ψ
′
n
=
p
β
2
+
β
1
γ
2
+
∑
i
=
k
+
2
n
β
i
Γ
i
-
1
+
Γ
n
AOQ
Ψ
n
-
A
O
Q
Ψ
′
n
=
p
β
1
1
-
γ
2
-
β
2
1
-
γ
1
=
p
1
-
p
1
-
α
1
1
-
α
2
λ
1
-
λ
2
.Since p
(
1
-
p
)
(
1
-
α
1
)
(
1
-
α
2
)
>
0, Lemma 3 holds when n
≥
3 and k
=
1.
Subcase
2. When 2
≤
k
≤
n
-
1, from Lemma 1-(5), A
O
Q
(
Ψ
(
n
)
)
-
A
O
Q
(
Ψ
′
(
n
)
) can be derived as (18)
AOQ
Ψ
n
=
p
β
1
+
⋯
+
β
k
-
1
Γ
k
-
2
+
β
k
Γ
k
-
1
+
β
k
+
1
γ
k
Γ
k
-
1
+
β
k
+
2
Γ
k
+
1
+
⋯
+
β
n
Γ
n
-
1
+
Γ
n
AOQ
Ψ
′
n
=
p
β
1
+
⋯
+
β
k
-
1
Γ
k
-
2
+
β
k
+
1
Γ
k
-
1
+
β
k
γ
k
+
1
Γ
k
-
1
+
β
k
+
2
Γ
k
+
1
+
⋯
+
β
n
Γ
n
-
1
+
Γ
n
AOQ
Ψ
n
-
AOQ
Ψ
′
n
=
p
Γ
k
-
1
β
k
1
-
γ
k
+
1
-
β
k
+
1
1
-
γ
k
=
p
1
-
p
Γ
k
-
1
1
-
α
k
1
-
α
k
+
1
λ
k
-
λ
k
+
1
.
Sincep
(
1
-
p
)
Γ
k
-
1
(
1
-
α
k
)
(
1
-
α
k
+
1
)
>
0, Lemma 3 holds when n
≥
3 and 2
≤
k
≤
n
-
1. Therefore, Lemma 3 holds.Lemma 4.
Forn
≥
2, Ψ
∗
(
n
) is one of λ-increasing sequences with size n.Proof.
It is enough to prove that ifΨ
∗
(
n
) is not one of λ-increasing sequences, then Ψ
∗
(
n
) does not give a minimum AOQ among a set of Ψ
(
n
). If Ψ
∗
(
n
) does not satisfy λ-increasing order, then there must exist at least two adjacent inspectors violating λ-increasing order, and, using Lemma 3, we can further reduce AOQ by swapping the adjacent inspectors. Thus, Ψ
∗
(
n
) does not give a minimum AOQ among a set of Ψ
(
n
), and Lemma 4 holds.Suppose that we takem inspectors from W in λ-increasing order. Let this ordered set be W
o, expressed as W
1
,
W
2
,
…
,
W
m. Let Ψ
o
(
n
) be the sequence with size n, constructed by taking the first n inspectors from W
o. That is, Ψ
o
n
=
〈
W
1
,
W
2
,
…
,
W
n
〉. Then, it may be conjectured that Ψ
o
n will give the minimum AOQ if the optimal number of inspection-rework cycles is known as n. However, unfortunately, this is not always true. For a counterexample, when the input data for α
k
,
β
k
,
k
=
1,2
,
3,4 are given as in Table 1 and when q
G
,
p is given as (3,000 ppm, 5%), it turns out that n
∗
=
2 and we have W
o
=
1,2
,
3,4 and Ψ
o
2
=
1,2. However, Ψ
∗
2 is not Ψ
o
2
=
1,2 but 1,3 since A
O
Q
Ψ
o
2
=
2,538 ppm > A
O
Q
1,3 = 2,534 ppm as shown in Table 2.Note thatΨ
∗
n is not Ψ
o
n but one of λ-increasing sequences with size n out of m available inspectors. Also note that if all inspection error probabilities are zero, that is, (
α
i
,
β
i
)
=
0,0 for all i, then A
O
Q
Ψ
k converges to zero, since A
O
Q
Ψ
k can be reduced to p
k
+
1. If α
i
,
β
i
=
1,1 for all i, then A
O
Q
Ψ
k converges to one, since A
O
Q
Ψ
k can be reduced to 1
-
1
-
p
k
+
1. From the results, it can be said that our RIS does not always guarantee that A
O
Q
Ψ
k is a decreasing function of k. However, as proved in the following two lemmas, ifΨ
n
-
1 is given, we can construct Ψ
n such that A
O
Q
Ψ
n
<
A
O
Q
Ψ
n
-
1 by selecting the nth inspector with v
n
<
1. Similarly, if Ψ
∗
n
-
1 is given, we can construct Ψ
∗
n such that A
O
Q
Ψ
∗
n
<
A
O
Q
Ψ
∗
n
-
1 by selecting the nth inspector with v
n
<
1. Hence, A
O
Q
Ψ
∗
n can be a strictly decreasing function of n.Lemma 5.
For1
≤
n
≤
m, A
O
Q
Ψ
n
<
A
O
Q
Ψ
n
-
1 if and only if v
n
<
1, where A
O
Q
Ψ
0
=
p.Proof.
Sinceβ
k
+
γ
k
=
1
-
p
α
k
+
β
k
+
p, we have(19)
p
-
AOQ
Ψ
1
=
p
1
-
β
1
+
γ
1
=
p
1
-
p
1
-
α
1
-
β
1
.Since p
1
-
p
>
0, Lemma 5 holds when n
=
1. When 2
≤
n
≤
m, by using Lemma 1-(5), we have (20)
AOQ
Ψ
n
-
1
-
AOQ
Ψ
n
=
p
1
-
p
Γ
n
-
1
1
-
v
n
.Since p
1
-
p
Γ
n
-
1
>
0, Lemma 5 holds when 2
≤
n
≤
m. Therefore Lemma 5 holds.Lemma 6.
For1
≤
n
≤
m, A
O
Q
Ψ
∗
n
<
A
O
Q
Ψ
∗
n
-
1 if and only if v
n
<
1, where A
O
Q
Ψ
∗
0
=
p.Proof.
IfΨ
∗
n
-
1 is given for an integer with 1
≤
n
≤
m and if v
n
<
1, we can construct Ψ
n using Lemma 5 such that A
O
Q
Ψ
n
<
A
O
Q
Ψ
∗
n
-
1 by assigning the inspector I
n with v
n
<
1. Since A
O
Q
Ψ
∗
n
≤
A
O
Q
Ψ
n by definition, it follows that A
O
Q
Ψ
∗
n
<
A
O
Q
Ψ
∗
n
-
1. Reversely, if A
O
Q
Ψ
∗
n
<
A
O
Q
Ψ
∗
n
-
1, then, from Lemma 5, there exists I
n with v
n
<
1.It remains whether or not an inspector withα
n
,
β
n satisfying v
n
<
1 exists among unassigned inspectors of the set W. However, since v
n do not exceed 100% in most practical cases, we assume hereafter that v
i
<
1 for 1
≤
n
≤
m.


## 3.2. An Optimal Algorithm

Using the previously proven properties, we can construct an optimal algorithm, ALGSP, for determining bothn
∗ and Ψ
∗
n
∗ simultaneously. Our algorithm consists of three phases: an initialization phase, a local optimization phase, and a global optimization phase. In the initialization phase, in order to reduce the computational execution time in the local optimization phase, we construct the λ-increasing set W
o from W. Without loss of generality, let W
o be 1,2
,
…
,
m.In the local optimization phase, we findΨ
∗
n for 1
≤
n
≤
m. Let Ψ
W
i
k be the λ-increasing sequence with size k generated from a given ordered combination, W
i
k, such that A
O
Q
Ψ
W
i
k
=
min
⁡
A
O
Q
Ψ
j
W
i
k
,
1
≤
j
≤
k
!. For example, if W
i
k is given as W
1
,
W
2
,
…
,
W
k, then Ψ
W
i
k can be immediately obtained as I
1
,
I
2
,
…
,
I
k, where W
i
=
I
i for 1
≤
i
≤
k. In the local optimization phase, given k, we construct Ψ
W
i
k from W
i
k using W
o. Next, from Ψ
W
i
k, we find the sequence Ψ
∗
k such that A
O
Q
Ψ
∗
k
=
min
⁡
A
O
Q
Ψ
W
i
k
,
1
≤
i
≤
m
k. In the outer loop, changing k from one to m, we store a set of the local optimal sequences, Ψ
∗
k
,
k
=
1,2
,
…
,
m. In the global optimization phase, we search for n
∗ satisfying A
O
Q
Ψ
∗
n
∗
≤
q
G. If n
∗ is not found, we terminate our algorithm with a message “n
∗
←
g
r
e
a
t
e
r
t
h
a
n
m.” See Algorithm 1.Algorithm 1:ALGSP.
Step  1 (Initialization Phase):
Take inspectors inλ-increasing order using α
i
,
β
i
,
i
=
1,2
,
…
,
m and let this ordered set be W
o
←
1,2
,
…
,
m.
Step  2 (Local Optimization Phase)
Fork
=
1 to m do
Begin
Fori
=
1 to   m
k
Begin
min
⁡
←
1
Begin
ConstructW
i
k and Ψ
W
i
k
ComputeAOQ
Ψ
W
i
k using Lemma 1(5).
IfAOQ
Ψ
W
i
k
≤ min, then Ψ
∗
k
←
Ψ
W
i
k,
AOQ
Ψ
∗
k
←
A
O
Q
Ψ
W
i
k, min
⁡
←
A
O
Q
Ψ
W
i
k
End
End
End
Step  3 (Global Optimization Phase)
Forn
=
1 to m do
Begin
If(
AOQ
Ψ
∗
n
≤
q
G
), then n
∗
←
n, Ψ
∗
n
∗
←
Ψ
∗
n, AOQ
Ψ
∗
n
∗
←
A
O
Q
Ψ
∗
n
If(
AOQ
Ψ
∗
n
>
q
G and n
=
m
), then print “n
∗
← greater than m” and stop
EndTheorem 7.
Ψ
∗
(
n
∗
) determined by ALGSP is an optimal sequence to SP.Proof.
A
O
Q
Ψ
∗
n is a decreasing function of n from Lemma 6, and n
∗ determined by ALGSP is the smallest number of inspection-rework cycles such that A
O
Q
(
Ψ
∗
(
n
∗
)
)
≤
q
G. Hence, Ψ
∗
(
n
∗
) determined by ALGSP is an optimal sequence to SP.Theorem 8.
ALGSP solves SP inO
(
2
m
).Proof.
From Theorem7, Ψ
∗
n
∗ gives an optimal solution to SP. Steps 1 and 3 require O
(
n
log
⁡
n
) and O
(
m
), respectively. Step 2 requires O
(
2
m
), since Ψ
∗
k can be obtained by enumerating not all the permutations but all the combinations of k inspectors from W; that is, ∑
k
=
1
m
m
k
=
2
m
-
1. Hence, ALGSP solves SP in O
(
2
m
).Even though the time complexity of ALGSP isO
(
2
m
), our algorithm is practically efficient since the optimal number of inspection-rework cycles is usually less than five cycles in most practical cases.


## 3.3. A Numerical Example

Suppose that(
q
G
,
p
,
m
) = (2,500 ppm, 5%, 4) and that α
k
,
β
k
,
k
=
1,2
,
3,4 are given as shown in Table 1. Using ALGSP, the optimal solution to our example will be obtained as follows.Step 1.
Theλ-increasing sequence is 1,2
,
3,4 and W
o
←
{
1,2
,
3,4
}.Step 2.
As shown in Table3, when n
=
1, we generate four sequences I
1 for 1
≤
I
1
≤
4, and we have Ψ
∗
1
=
3 (or W
3) with A
O
Q
Ψ
∗
1
=
5,027 ppm. When n
=
2, we generate six sequences I
1
,
I
2 where I
1
,
I
2 is obtained by finding the combinations of two inspectors from W
o, and we have Ψ
∗
2
=
1,3 with A
O
Q
Ψ
∗
2
=
2,534 ppm. When n
=
3, we generate four sequences I
1
,
I
2
,
I
3 obtained by finding the combinations of three inspectors from W
o, and we have Ψ
∗
3
=
1,2
,
3 with A
O
Q
Ψ
∗
3
=
2,394 ppm. When n
=
4, we generate one sequence 1,2
,
3,4, which is the only λ-increasing sequence, and we have Ψ
∗
4
=
1,2
,
3,4 with A
O
Q
Ψ
∗
4
=
2,386 ppm. After Step 2, Ψ
∗
n and A
O
Q
Ψ
∗
n for 1
≤
n
≤
4 can be obtained as summarized in Table 4.Table 3
The changing values in Step2.
k
i
W
i
(
k
)
Ψ
(
W
i
k
)
AOQ
(
Ψ
(
W
i
k
)
)
Ψ
∗
(
k
)
AOQ
(
Ψ
∗
(
k
)
)
1
1
W
1
(
1
)
=
{
1
}
1
5075
1
5075
2
W
2
(
1
)
=
{
2
}
2
5103
1
5075
3
W
3
(
1
)
=
{
3
}
3
5027
3
5027
4
W
4
(
1
)
=
{
4
}
4
5364
3
5027
2
1
W
1
(
2
)
=
{
1,2
}
1,2
2538
1,2
2538
2
W
2
(
2
)
=
{
1,3
}
1,3
2534
1,3
2534
3
W
3
(
2
)
=
{
1,4
}
1,4
2553
1,3
2534
4
W
4
(
2
)
=
{
2,3
}
2,3
2541
1,3
2534
5
W
5
(
2
)
=
{
2,4
}
2,4
2561
1,3
2534
6
W
6
(
2
)
=
{
3,4
}
3,4
2593
1,3
2534
3
1
W
1
(
3
)
=
{
1,2
,
3
}
1,2
,
3
2394
1,2
,
3
2394
2
W
2
(
3
)
=
{
1,2
,
4
}
1,2
,
4
2395
1,2
,
4
2394
3
W
3
(
3
)
=
{
1,3
,
4
}
1,3
,
4
2396
1,3
,
4
2394
4
W
4
(
3
)
=
{
2,3
,
4
}
2,3
,
4
2403
1,3
,
4
2394
4
1
W
1
(
4
)
=
{
1,2
,
3,4
}
1,2
,
3,4
2386
1,2
,
3,4
2386Table 4
Ψ
∗
k and AOQ
(
Ψ
∗
k
), which resulted from Step 2.
k
Ψ
∗
(
k
)
AOQ
(
Ψ
∗
(
k
)
)
1
3
5027
2
1,3
2534
3
1,2
,
3
2394
4
1,2
,
3,4
2386Step 3.
SinceA
O
Q
Ψ
∗
2
=
2,534 ppm > q
G
=
2,500 ppm > A
O
Q
Ψ
∗
3
=
2,394 ppm, ALGSP terminates with n
∗
=
3 and Ψ
∗
3
=
1,2
,
3.For the reader’s convenience, we have included the computational results of all the possible sequences generated from the set{
1,2
,
3,4
} in Tables 5, 6, and 7.Table 5
W
i
2, Ψ
j
W
i
2, and AOQ
Ψ
j
W
i
2 when n
=
2.
W
i
(
2
)
Ψ
j
(
W
i
(
2
)
)
AOQ
(
Ψ
j
(
W
i
(
2
)
)
)
W
i
(
2
)
Ψ
j
(
W
i
(
2
)
)
AOQ
(
Ψ
j
(
W
i
(
2
)
)
)
W
1
(
2
)
=
{
1
,
2
}
Ψ
1
W
1
2
=
1,2
2538
W
4
(
2
)
=
{
2,3
}
Ψ
1
W
4
2
=
2,3
2541
Ψ
2
W
1
2
=
2,1
2544
Ψ
2
W
4
2
=
3,2
2578
W
2
(
2
)
=
{
1,3
}
Ψ
1
W
2
2
=
1,3
2534
W
5
(
2
)
=
{
2,4
}
Ψ
1
W
5
2
=
2,4
2561
Ψ
2
W
2
2
=
3,1
2577
Ψ
2
W
5
2
=
4,2
2873
W
3
(
2
)
=
{
1,4
}
Ψ
1
W
3
2
=
1,4
2553
W
6
(
2
)
=
{
3,4
}
Ψ
1
W
6
2
=
3,4
2593
Ψ
2
W
3
2
=
4,1
2872
Ψ
2
W
6
2
=
4,3
2869Table 6
W
i
3, Ψ
j
W
i
3, and AOQ
Ψ
j
W
i
3 when n
=
3.
W
i
(
3
)
Ψ
j
(
W
i
(
3
)
)
AOQ
(
Ψ
j
(
W
i
(
3
)
)
)
W
i
(
3
)
Ψ
j
(
W
i
(
3
)
)
AOQ
(
Ψ
j
(
W
i
(
3
)
)
)
W
1
(
3
)
=
{
1,2
,
3
}
Ψ
1
W
1
3
=
1,2
,
3
2394
W
3
(
3
)
=
{
1,3
,
4
}
Ψ
1
W
3
3
=
1,3
,
4
2396
Ψ
2
W
1
3
=
1,3
,
2
2396
Ψ
2
W
3
3
=
1,4
,
3
2412
Ψ
3
W
1
3
=
2,1
,
3
2399
Ψ
3
W
3
3
=
3,1
,
4
2439
Ψ
4
W
1
3
=
2,3
,
1
2402
Ψ
4
W
3
3
=
3,4
,
1
2457
Ψ
5
W
1
3
=
3,1
,
2
2438
Ψ
5
W
3
3
=
4,1
,
3
2731
Ψ
6
W
1
3
=
3,2
,
1
2439
Ψ
6
W
3
3
=
4,3
,
1
2733
W
2
(
3
)
=
{
1,2
,
4
}
Ψ
1
W
2
3
=
1,2
,
4
2395
W
4
(
3
)
=
{
2,3
,
4
}
Ψ
1
W
4
3
=
2,3
,
4
2403
Ψ
2
W
2
3
=
1,4
,
2
2412
Ψ
2
W
4
3
=
2,4
,
3
2418
Ψ
3
W
2
3
=
2,1
,
4
2400
Ψ
3
W
4
3
=
3,2
,
4
2440
Ψ
4
W
2
3
=
2,4
,
1
2419
Ψ
4
W
4
3
=
3,4
,
2
2457
Ψ
5
W
2
3
=
4,1
,
2
2731
Ψ
5
W
4
3
=
4,2
,
3
2731
Ψ
6
W
2
3
=
4,2
,
1
2731
Ψ
6
W
4
3
=
4,3
,
2
2733Table 7
W
i
4, Ψ
j
W
i
4, and AOQ
Ψ
j
W
i
4 when n
=
4.
W
i
(
4
)
Ψ
j
(
W
i
(
4
)
)
AOQ
(
Ψ
j
(
W
i
(
4
)
)
)
W
i
(
4
)
Ψ
j
(
W
i
(
4
)
)
AOQ
(
Ψ
j
(
W
i
(
4
)
)
)
W
1
(
4
)
=
{
1,2
,
3,4
}
Ψ
1
W
1
4
=
1,2
,
3,4
2386
W
1
(
4
)
=
{
1,2
,
3,4
}
Ψ
13
W
1
4
=
3,1
,
2,4
2431
Ψ
2
W
1
4
=
1,2
,
4,3
2387
Ψ
14
W
1
4
=
3,1
,
4,2
2432
Ψ
3
W
1
4
=
1,3
,
2,4
2388
Ψ
15
W
1
4
=
3,2
,
1,4
2431
Ψ
4
W
1
4
=
1,3
,
4,2
2389
Ψ
16
W
1
4
=
3,2
,
4,1
2432
Ψ
5
W
1
4
=
1,4
,
2,3
2404
Ψ
17
W
1
4
=
3,4
,
1,2
2449
Ψ
6
W
1
4
=
1,4
,
3,2
2404
Ψ
18
W
1
4
=
3,4
,
2,1
2449
Ψ
7
W
1
4
=
2,1
,
3,4
2392
Ψ
19
W
1
4
=
4,1
,
2,3
2723
Ψ
8
W
1
4
=
2,1
,
4,3
2392
Ψ
20
W
1
4
=
4,1
,
3,2
2723
Ψ
9
W
1
4
=
2,3
,
1,4
2394
Ψ
21
W
1
4
=
4,2
,
1,3
2723
Ψ
10
W
1
4
=
2,3
,
4,1
2395
Ψ
22
W
1
4
=
4,2
,
3,1
2723
Ψ
11
W
1
4
=
2,4
,
1,3
2411
Ψ
23
W
1
4
=
4,3
,
1,2
2725
Ψ
12
W
1
4
=
2,4
,
3,1
2411
Ψ
24
W
1
4
=
4,3
,
2,1
2725


## 4. Conclusion

Assuming that all the items rejected by an inspector are reworked in a constant defective rate and are sent to the next inspection-rework cycle, we have addressed the sequencing problem of inspectors from a set of available inspectors in order to meet a constraint on the outgoing quality level, subject to nonidentical errors and several assumptions. We provided a practical nonpolynomial time-optimal algorithm, which simultaneously determines the minimum number of inspection-rework cycles and an optimal sequence inO
(
2
m
).Our strong conjecture is that our problem is NP-complete. Not by our conjecture but by our computational experience, we would like to suggest two heuristic algorithms with the time complexity ofO
(
n
log
⁡
n
) based on λ-increasing or v-increasing order. The near-optimal sequence with size n can be determined just by taking the first n inspectors from the set of available inspectors listed in λ-increasing or v-increasing order. Further research may be concentrated on either proving that our problem is NP-complete or finding a polynomial-time algorithm by discovering more properties in our problem, while the combinatorial optimization problem for determining an optimal sequence in terms of total cost or the number of inspections may be studied in depth. Our basic methods used in proofs could be utilized for solving other similar sequencing problems.



---

*Source: 601029-2015-09-03.xml*