Dynamic quality control in assembly systems.

We study an assembly system, in which each end product consists of two different components. The components are produced in batches, with possible defective units. The proportion of defective units in each batch is itself a random variable, known only in terms of its distribution. Defective

units can be identified and corrected through an inspection-repair procedure, before final assembly taking place. We are concerned with developing an optimal inspection policy that minimizes the total expected cost due to inspection, repair, and warranty. Particularly, we focus on policies that have simple threshold structures and a near-optimal performance.

1. Introduction

Recently, Chen et al. (1998) studied the following quality control problem in a batch manufacturing setting. Products are produced in batches, and supplied to customers under some type of warranty or service contract. Each unit in the batch is either defective or non-defective, with different lifetime distributions. The defect rate in each batch is itself a random variable, with a known distribution. Defective units can be identified through inspection and repaired. In Chen et al. (1998), certain threshold type inspection policies are identified and proved to be optimal in minimizing the total cost (for inspection, repair and warranty). Specifically, the optimal policy is characterized by a sequence of thresholds: {[[d.sup.*].sub.n], n = 0,...,N}, where N is the size of the batch. Let D(n) be the number of defective units identified when n units have been inspected. The optimal policy is to inspect the units one at a time; each time compare D(n) against [[d.sup.*].sub.n], and stop inspection the first time wh en D(n) [less than] [[d.sup.*].sub.n] (i.e., ship the whole batch without inspecting any remaining units). Extensions of this model to systems with multiple stages, capacity constraints and other features include Chen (1997), Yao and Zheng (1999a,b).

In this paper we study a similar quality control problem in an assembly system. Suppose each end product consists of two different component subassemblies; and quality control of the components are carried out before the final assembly. The problem is to develop an inspection policy on the two component batches so that the total cost is minimized. While the optimal policy can be derived from solving a dynamic programming problem, there is no guarantee that this will result in a simple control policy such as the threshold-type sequential inspection policies in Chen et al. (1998). This is because in the current model the inspection decision for the two components are interleaved together, and the optimal inspection in general will switch back and forth between the two components, destroying any threshold structure. Our focus here is on a class of easily implementable policies that have a simple "single-switch" structure. We show that this class of policies are optimal for a special case of the original problem when one of the two components has a constant defect rate. Furthermore, we illustrate through numerical examples that such policies have a near-optimal performance when applied to the original problem.

There are many papers discussing different aspects of assembly systems, e.g., Glasserman and Wang (1998), Song et al. (1999), and Yao (1988). In the quality control literature, most studies focus on single-stage or serial systems, e.g., Ballou and Pazer (1982), Eppen and Hurst (1974), Tapiero and Lee (1989), Djamaludin et al. (1994), and Yao and Zheng (1999b). There are also studies considering non-serial systems including assembly lines (Britney, 1972; and Gunter and Swanson, 1985), but the emphases are not usually on deriving optimal inspection policies.

Briefly, the rest of this paper is organized as follows: in Section 2 we describe the model in detail and derive certain basic properties of the model. A dynamic programming formulation is presented in Section 3. In Section 4 we identify an optimal policy that has a threshold structure for the case when one of the components has a constant defect rate. Based on this result, we develop in Section 5 a heuristic inspection policy for the original problem, and illustrate its near-optimal performance through two numerical examples.

2. Model description and the cost structure

Suppose two components, termed component 1 and component 2, are produced in batches with N units per batch for both components. They are then assembled into N end products, which, in turn, are supplied to customers under some types of warranty (or service contract). Suppose the defective rates of the two components are [[theta].sub.1] and [[theta].sub.2], respectively. Here, [[theta].sub.i] [epsilon] [0, 1] is itself a random variable with a known distribution, representing the defect rate of component i. This works as follows: [[theta].sub.i] is first sampled from its distribution; suppose the sample value is [[theta].sub.i], then each unit in the batch is defective with probability [[theta].sub.i]. The distribution of [[theta].sub.i], which is common for all the units in the batch, naturally captures the statistical dependence among the units. In this paper [[theta].sub.1] and [[theta].sub.2] are supposed to be independent, and we assume that the assembly procedure itself does not produce defective, i.e., a s long as the two components are both nondefective, they will be assembled into an end product that is nondefective.

For i = 1, 2, suppose the life time of a defective component i is [Y.sub.i], while a nondefective component i has a life time [X.sub.i]. Assume [X.sub.i] [[greater than or equal to].sub.st] [Y.sub.i], i.e., P[X [greater than or equal to] a] [greater than or equal to] P[Y [greater than or equal to] a] for all a [greater than or equal to] 0. This is the so-called stochastic ordering; refer to, e.g., Ross (1983). Assume the life times of the components are independent of one another. If the life times of the two components are [Z.sub.1] and [Z.sub.2] respectively, then the life time of the end product is assumed to be [Z.sub.1] [conjuction] [Z.sub.2] := min([Z.sub.1], [Z.sub.2]). Let [Z.sub.i]([[theta].sub.i]) denote the random variable that equals in distribution to [Y.sub.i](resp. [X.sub.i]) with probability [[theta].sub.i](resp. 1 - [[theta].sub.i]).

Defectives of both components can be detected by inspection. Suppose the inspection is perfect (i.e., a component is identified as defective if and only if it is defective), and the per unit inspection cost is [[C.sup.(1)].sub.I] and [[C.sup.(2)].sub.I], respectively, for the two components. A defective unit can be corrected via repair or rework (and become a nondefective unit) at a per unit cost of [[C.sup.(1)].sub.R] or [[C.sup.(2)].sub.R], respectively, for the two components.

Similar to Chen et al. (1998), we will first consider a cumulative warranty cost function of the end products. Specifically, if the total life time of the N assembled units is t, then the warranty cost is C(t), with C(t) assumed to be a convex and decreasing function of t. (Throughout the paper, we shall use "decreasing" and "increasing" in the nonstrict sense, to mean nonincreasing and nondecreasing, respectively. And for other aspects of a cumulative warranty, please refer to Blischke (1990).) When C(t) is an additive function, we have the individual warranty case in which the warranty applies to each individual unit. To provide adequate incentive to the repair of any defective unit, we assume

[[C.sup.(1)].sub.R] [less than or equal to] EC ([[[sigma].sup.N-1].sub.j=1] [X.sub.1j] [conjuction] [X.sub.2j] + [Y.sub.1] [conjuction] [Y.sub.2]) - EC ([[[sigma].sup.N-1].sub.j=1] [X.sub.1j] [conjuction] [X.sub.2j] + [X.sub.1] [conjuction] [Y.sub.2]), (1)

and

[[C.sup.(2)].sub.R] [less than or equal to] EC ([[[sigma].sup.N-1].sub.j=1] [X.sub.1j] [conjuction] [X.sub.2j] + [Y.sub.1] [conjuction] [Y.sub.2]) - EC ([[[sigma].sup.N-1].sub.j=1] [X.sub.1j] [conjuction] [X.sub.2j] + [Y.sub.1] [conjuction] [X.sub.2]). (2)

In the above inequalities, [X.sub.1j] and [X.sub.2j] are i.i.d. replicas of [X.sub.1] and [X.sub.2], respectively. (Below, we shall apply the same notation to component lifetimes, Y and Z.)

Our problem here is to design a procedure to inspect the components, so as to minimize the total (expected) cost for inspection, possible repair work, and for the warranty.

We first derive some basic results for the model.

Lemma 1. For any given constant [tau] [greater than or equal to] 0, the expectation

E[C([tau] + [X.sub.1] [conjuction] [X.sub.2] + C([tau] + [Y.sub.1] [conjuction] [Y.sub.2]) - C([tau] + [X.sub.1] [conjuction] [Y.sub.2]) - C([tau] + [Y.sub.1] [conjuction] [X.sub.2])] [less than or equal to] 0,

And is increasing in [tau].

Proof. Let

F(t) := [F.sub.[X.sub.1](t)[F.sub.[X.sub.2](t) := P[X.sub.1] [greater than or equal to] t]P[X.sub.1] [greater than or equal to] t].

Noticing that

EC([tau] + [X.sub.1] [conjuction] [X.sub.2] = - [[[integral].sup.[infinity]].sub.0] C([tau] + t)dF(t)

= C([tau]) + [[[integral].sup.[infinity]].sub.0] [F.sub.[X.sub.1](t)[F.sub.[X.sub.2](t)dC([tau] + t),

we have

E[C([tau] + [X.sub.1] [conjuction] [X.sub.2]) + C([tau] + [Y.sub.1] [conjuction] [Y.sub.2] - C([tau] + [X.sub.1] [conjuction] [Y.sub.2]) - C([tau] + [Y.sub.1] [conjuction] [X.sub.2])],

= [[[integral].sup.[infinity]].sub.0] [[F.sub.[X.sub.1](t)[F.sub.[X.sub.2](t) + [F.sub.[Y.sub.1](t)[F.sub.[Y.sub.2](t) - [F.sub.[X.sub.1](t)[F.sub.[Y.sub.2](t) - [F.sub.[Y.sub.1](t)[F.sub.[X.sub.2](t)]dC([tau] + t). (3)

- F[Y.sub.1](t)F[X.sub.2](t)]dC([tau] + t). (3)

Note in the integral above, C(*) is decreasing, and the expression in the square brackets is nonnegative, which follows from

[F.sub.[X.sub.1] (t) [greater than or equal to] [F.sub.[Y.sub.1] (t) and [F.sub.[X.sub.2] (t) [greater than or equal to] [F.sub.[Y.sub.2] (t),

for all t. Hence, the integral in (3) is non-positive. The desired increasingness in [tau] follows from the convexity of C(*).

By conditioning on the value of [[[sigma].sup.N-1].sub.j=1] [X.sub.1j] [conjuction] [X.sub.2j], an immediate consequence of Lemma 1 is that from (1) and (2), we have

[[C.sup.(1)].sub.R] [less than or equal to] EC ([[[sigma].sup.N-1].sub.j=1] [X.sub.1j] [conjuction] [X.sub.2j] + [Y.sub.1] [conjuction] [X.sub.2]) - EC ([[[sigma].sup.N-1].sub.j=1] [X.sub.1j] [conjuction] [X.sub.2j] + [X.sub.1] [conjuction] [X.sub.2]), (4)

and

[[C.sup.(2)].sub.R] [less than or equal to] EC ([[[sigma].sup.N-1].sub.j=1] [X.sub.1j] [conjunction] [X.sub.2j] + [X.sub.1] [conjunction] [Y.sub.2]) - EC ([[[sigma].sup.N-1].sub.j=1] [X.sub.1j] [conjunction] [X.sub.2j] + [X.sub.1] [conjunction] [X.sub.2]). (5)

This is because the right-hand sides of the above dominate the right-hand sides of (1) and (2), respectively.

Lemma 2. It is always better, in terms of reducing the warranty cost, to match confirmed (via inspection) non-defective units when doing the assembly.

Proof. We prove this by an interchange argument. Suppose there is an end product consisting of a confirmed non-defective component 1 and an uninspected component 2, while another end product consisting of an uninspected component 1 and a confirmed nondefective component 2. We will show that it is better to assemble together the two nondefective components, and the two uninspected components. Let [tau] denote the total life time of the other N - 2 end products in the batch. Then it suffices to show the following:

EC([tau] + [X.sub.1] [conjuction] [X.sub.2] + [Z.sub.1] [conjuction] [Z.sub.2]) [less than or equal to] EC([tau] + [X.sub.1] [conjuction] [Z.sub.2] + [Z.sub.1] [conjuction] [X.sub.2]), (6)

where [Z.sub.1] and [Z.sub.2] are the life times of the uninspected component 1 and 2 respectively. Note that

min[[x.sub.1], [x.sub.2]] + min[[y.sub.1], [y.sub.2]] [greater than or equal to] min[[x.sub.1], [y.sub.2]] + min[[y.sub.1], [x.sub.2]],

for all real numbers with [x.sub.1] [greater than or equal to] [y.sub.1], [x.sub.2] [greater than or equal to] [y.sub.2]. Hence, based on [X.sub.1] [[greater than or equal to].sub.st] [Z.sub.i], for i = 1,2, and a standard coupling argument, we can conclude that the argument of the C(*) function on the left side of (6) dominates, stochastically, the argument of C(*) on the right side. As C(*) is decreasing, (6) must hold.

3. A dynamic programming formulation

Let [phi]([n.sub.1], [[theta].sub.1], [n.sub.2], [[theta].sub.2]) denote the minimal expected warranty cost, given [[theta].sub.1] = [[theta].sub.1], [[theta].sub.2] = [[theta].sub.2], and exactly [n.sub.1] and [n.sub.2] items of component 1 and 2 are inspected. Then, from Lemma 2, we have

[phi]([n.sub.1],[[theta].sub.1],[n.sub.2],[[theta].sub.2]) = EC ([[[sigma].sup.[n.sub.1].sub.i=1] [X.sub.1i] [conjuction] [X.sub.2i] + [[[sigma].sup.[n.sub.2].sub.i=[n.sub.1]+1] [Z.sub.1i]([[theta].sub.1]) [conjuction] [X.sub.2i] + [[[sigma].sup.N].sub.i=[n.sub.2]+1] [Z.sub.1i]([[theta].sub.1]) [conjuction] [Z.sub.2i]([[theta].sub.2])),

when [n.sub.1] [less than] [n.sub.2]; and

[phi]([n.sub.1],[[theta].sub.1],[n.sub.2],[[theta].sub.2]) := EC([[[sigma].sup.[n.sub.1].sub.i=1] [X.sub.1i] [conjuction] [X.sub.2i] + [[[sigma].sup.[n.sub.i].sub.i=[n.sub.2]+1] [X.sub.1i] [conjuction [Z.sub.2i]([[theta].sub.1]) + [[[sigma].sup.N].sub.i=[n.sub.1]+1] [Z.sub.1i]([[theta].sub.1]) [conjuction] [Z.sub.2i]([[theta].sub.2])),

when [n.sub.1] [greater than or equal to] [n.sub.2].

To identify the optimal inspection policy, we formulate a dynamic programming problem as follows. Denote ([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2]) as the state, with [n.sub.j] as the number of inspected units in component j, and [d.sub.j] as the number of defective units identified from those inspected from component j, j = 1, 2. Note that when [n.sub.1],[n.sub.2] [less than] N, there are three control actions available at ([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2]): to stop inspection, to continue inspection with component 1, and to continue inspection with component 2. (And when [n.sub.j] = N, the action of inspecting component j is not available, for j = 1, 2.) Let V([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2]) denote the optimal expected cost-to-go, starting from the state ([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2]). Let [phi]([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2]), [[psi].sub.1]([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2]) and [[psi].sub.2]([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2]), denote the cost-to-go, starting from ([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2]), respectively, for the actions: to stop inspection, to continue inspection with component 1, and to continue inspection with component 2.

Then, for 0 [less than or equal to] [n.sub.1],[n.sub.2] [less than] N, we have

[phi]([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2] = E[[phi]([n.sub.1],[[theta].sub.1],[n.sub.2],[[theta].sub.2])\[D.sub.1 ]([n.sub.1]) = [d.sub.1],[D.sub.2]([n.sub.2] = [d.sub.2]], (7)

[[psi].sub.1]([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2]) = [[C.sup.(1)].sub.I] + [[C.sup.(1)].sub.R][[theta].sub.1]([n.sub.1],[d.sub.1]) + E[V([n.sub.1], + 1,[d.sub.1], + [I.sub.1]([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2])], (8)

[[psi].sub.2]([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2] = [[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2]([n.sub.2],[d.sub.2]) + E[V([n.sub.1],[d.sub.1],[n.sub.2] + 1, [d.sub.2] + [I.sub.2]([n.sub.2],[d.sub.2]))], (9)

and

V([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2] = min{[phi]([[n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2]), [[psi].sub.1]([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2]), [[psi].sub.2]([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2])}, (10)

V(N,[d.sub.1],[n.sub.2],[d.sub.2]) = min{[phi](N,[d.sub.1],[n.sub.2],[d.sub.2]), [[psi].sub.2](N,[d.sub.1],[n.sub.2],[d.sub.2])}, (11)

V([n.sub.1],[d.sub.1]N,[d.sub.2]) = min{[phi]([n.sub.1],[d.sub.1],N,[d.sub.2]), [[psi].sub.1]([n.sub.1],[d.sub.1]N,[d.sub.2])} (12)

with

V(N,[d.sub.1],N[d.sub.2]) = [phi](N,[d.sub.1]N,[d.sub.2]).

Here and below, [D.sub.j](n) denotes the (random) number of defective units identified from inspecting n units of component j,[[theta].sub.j]([n.sub.j],[d.sub.j]) := E[[[theta].sub.j]\[D.sub.j]([n.sub.j]) = [d.sub.j]], and [I.sub.j]([n.sub.j],[d.sub.j]) is a binary (0-1) random variable that equals to one with probability [[theta].sub.j]([n.sub.j],[d.sub.j]), for j = 1,2. An optimal policy is one which prescribes actions (in each state) that minimize the right-hand sides of the equations in (10) through (12).

Since the inspection decisions for the two components are interleaved together, there is no simple threshold-type optimal policies in general. Below, we consider a special case: component 2 has a constant (i.e., deterministic) defect rate, and derive the optimal policy, which, in turn, will lead to a heuristic policy for the original problem (i.e., component 2, like component 1, has a random defect rate).

For ease of discussion, we shall focus on the case of individual warranty costs. In this case a warranty cost of C([Z.sub.1] [conjuction] [Z.sub.2]) is associated with each individual end product that consists of two components with life times [Z.sub.1] and [Z.sub.2]. Note that in the place of Lemma 1, what we need in this case is

E[C([X.sub.1] [conjuction] [X.sub.2]) + C([Y.sub.1] [conjuction] [Y.sub.2])-C([X.sub.1] [conjuction] [Y.sub.2])-C([Y.sub.1] [conjuction] [X.sub.2])] 0, [less than or equal to] 0, (13)

which only requires C(*) to be a decreasing function: convexity is not needed. As before, the inequality in (13) implies that it is always better to match confirmed non-defective components when doing assembly. Also, to provide incentive for repairing any identified defective component, we assume

[[C.sup.(1)].sub.R] [less than or equal to] E[C([Y.sub.1] [conjuction] [Y.sub.2]) - C([X.sub.1] [conjuction] [Y.sub.2])],

[[C.sup.(2)].sub.R] [less than or equal to] E[C([Y.sub.1] [conjuction] [Y.sub.2]) - C([Y.sub.1] [conjuction] [X.sub.2])]. (14)

These, together with (13), imply that

[[C.sup.(1)].sub.R] [less than or equal to] E[C([Y.sub.1] [conjuction] [X.sub.2]) - C([X.sub.1] [conjuction [X.sub.2])],

[[C.sup.(2)].sub.R] [less than or equal to] E[C([X.sub.1] [conjuction] [Y.sub.2]) - C([X.sub.1] [conjuction] [X.sub.2])]. (15)

Note that in this case [phi] is a linear function of [n.sub.l] and [n.sub.2], and can be expressed as follows

[phi]([n.sub.1],[[theta].sub.1],[n.sub.2],[[theta].sub.2]) =[n.sub.2]EC([X.sub.1] [conjuction] [X.sub.2])

+ ([n.sub.1] - [n.sub.2])EC([X.sub.1] [conjuction] [Z.sub.2]([[theta].sub.2]))

+ (N - [n.sub.1])EC([Z.sub.1]([[theta].sub.1]) [conjuction] [Z.sub.2]([[theta].sub.2])),

when [n.sub.1] [greater than or equal to] [n.sub.2]; and

[phi]([n.sub.1],[[theta].sub.1],[n.sub.2],[[theta].sub.2]) =[n.sub.1]EC([X.sub.1] [conjuction] [X.sub.2])

+([n.sub.2] - [n.sub.1])EC([Z.sub.1]([[theta].sub.1]) [conjuction] [X.sub.2])

+ (N - [n.sub.2])EC([Z.sub.1]([[theta].sub.1]) [conjuction] [Z.sub.2]([[theta].sub.2])),

when [n.sub.1] [less than] [n.sub.2]. For convenience, denote

[[delta].sub.1] :=EC([X.sub.1] [conjuction] [Y.sub.2]) - EC([X.sub.1] [conjuction] [X.sub.2]),

[[delta].sub.2] :=EC([Y.sub.1] [conjuction] [Y.sub.2]) - EC([Y.sub.1] [conjuction] [X.sub.2]). (16)

Clearly [[delta].sub.1] [greater than or equal to] 0 and [[delta].sub.2] [greater than or equal to] 0. From (13), we also have [[delta].sub.1] [greater than or equal to] [[delta].sub.2].

Now suppose component 2 has a constant defect rate, i.e., [[theta].sub.2] [equivalent] [[theta].sub.2]. In this case, [[theta].sub.2]([n.sub.2],[d.sub.2]) [equivalent] [[theta].sub.2] for any [n.sub.2] and [d.sub.2], and we can see from (7) to (12) that [d.sub.2] plays no role in the decision. Hence, we can simplify the state of the dynamic program to ([n.sub.1], [d.sub.1], [n.sub.2]).

4. One component with a constant defect rate

We start with two key lemmas, which spell Out how the inspection of component 2, which is assumed to have a constant defect rate, should be carried out.

Lemma 3. If it is strictly better to inspect batch 2 than to inspect batch 1 in state ([n.sub.1], [d.sub.1], [n.sub.2]), then it is optimal not to inspect any more component 1, starting from state ([n.sub.1], [d.sub.1], [n.sub.2]).

Proof. It suffices to prove that, if

[[psi].sub.2]([n.sub.1],[d.sub.1],[n.sub.2]) [less than] [[psi].sub.1]([n.sub.1],[d.sub.1],[n.sub.2]), (17)

then

min{[phi]([n.sub.1],[d.sub.1],[n.sub.2] + 1), [[psi].sub.2]([n.sub.1],[d.sub.1],[n.sub.2] + 1)} [less than] [[psi].sub.1]([n.sub.1],[d.sub.1],[n.sub.2] + l) for [n.sub.2] [less than] N - 1, (18)

and

[phi]([n.sub.1],[d.sub.1],[n.sub.2] + 1) [less than] [[psi].sub.1] ([n.sub.1],[d.sub.1],[n.sub.2] + 1) for [n.sub.2] = N - 1. (19)

We shall prove the above by contradiction. For [n.sub.2] [less than] N - 1, if (18) is not true, then

V([n.sub.1],[d.sub.1],[n.sub.2] + 1) = [[psi].sub.1]([n.sub.1],[d.sub.1],[n.sub.2] + 1).

From this we have

[[psi].sub.2]([n.sub.1],[d.sub.1],[n.sub.2]) = [[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R] [[theta].sub.2] + V([n.sub.1],[d.sub.1],[n.sub.2] + 1)

= [[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2] + [[psi].sub.1]([n.sub.1],[d.sub.1],[n.sub.2] + 1)

= [[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2] + [[C.sup.(1)].sub.I] [[C.sup.(1)].sub.R][[theta].sub.1]([n.sub.1],[d.sub.1]) + E[V([n.sub.1] + 1,[d.sub.1] + [I.sub.1]([n.sub.1],[d.sub.1]),[n.sub.2] + 1)].

But

[[psi].sub.1]([n.sub.1],[d.sub.1],[n.sub.2]) = [[C.sup.(1)].sub.I] + [[C.sup.(1)].sub.R][[theta].sub.1]([n.sub.1],[d.sub.1])

+ E[V([n.sub.1] + 1,[d.sub.1] + [I.sub.1]([n.sub.1],[d.sub.1]),[n.sub.2])] [less than or equal to] [[C.sup.(1)].sub.I] + [[C.sup.(1)].sub.R][[theta].sub.1]([n.sub.1],[d.sub.1])

+E[[[psi].sub.2]([n.sub.1] + 1,[d.sub.1] + [I.sub.1]([n.sub.1],[d.sub.1]),[n.sub.2])]

= [[C.sup.(1)].sub.I] + [[C.sup.(1)].sub.R][[theta].sub.1]([n.sub.1],[d.sub.1]) + [[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2]

+ E[V([n.sub.1] + 1,[d.sub.1] + [I.sub.1]([n.sub.1],[d.sub.1]),[n.sub.2] + 1)]

= [[psi].sub.2]([n.sub.1],[d.sub.1],[n.sub.2]),

which contradicts (17).

For [n.sub.2] = N - 1, if (19) is not true, then

[[psi].sub.1]([n.sub.1],[d.sub.1],N) = V([n.sub.1],[d.sub.1],N) [less than or equal to] [phi]([n.sub.1],[d.sub.1],N).

On the other hand, we can rewrite (17) as:

[[psi].sub.2]([n.sub.1],[d.sub.1],[n.sub.2]) = [[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2] + V([n.sub.1],[d.sub.1],N),

[less than] [[psi].sub.1]([n.sub.1],[d.sub.1],[n.sub.2]),

= [[C.sup.(1)].sub.I] + [[C.sup.(1)].sub.R][[theta].sub.1]([n.sub.1],[d.sub.1])

+ E[V([n.sub.1] + 1,[d.sub.1] + [I.sub.1]([n.sub.1],[d.sub.1]),N - 1)].

Hence,

[[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2] + [[psi].sub.1]([n.sub.1],[d.sub.1],N) [less than] = [[C.sup.(1)].sub.I] + [[C.sup.(1)].sub.R][[theta].sub.1]([n.sub.1],[d.sub.1])

+ E[V([n.sub.1] + 1,[d.sub.1] + [I.sub.1]([n.sub.1],[d.sub.1]),N - 1)],

or equivalently,

[[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2] + E[V([n.sub.1] + 1,[d.sub.1] + [I.sub.1]([n.sub.1],[d.sub.1]),N)]. [less than] E[V([n.sub.1] + 1,[d.sub.1] + [I.sub.1]([n.sub.1],[d.sub.1]),N - 1].

Since

E[V([n.sub.1] + 1,[d.sub.1] + [I.sub.1]([n.sub.1],[d.sub.1]),N - 1] [less than or equal to] E[[[psi].sub.2]([n.sub.1] + 1,[d.sub.1] + [I.sub.1]([n.sub.1],[d.sub.1]),N - 1]

[[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2] + E[V([n.sub.1] + 1,[d.sub.1] + [I.sub.1]([n.sub.1],[d.sub.1]),N)].

we have reached a contradiction.

Lemma 4. Given [[theta].sub.1] = [[theta].sub.1], and that exactly [n.sub.1] units of component 1 are inspected, the optimal inspection rule for component 2 is as follows:

(a) Inspect all N units, if [[C.sup.(2)].sub.I] [less than or equal to] [(1 - [[theta].sub.1])[[delta].sub.1] + [[theta].sub.1][[delta].sub.2] - [[C.sup.(2)].sub.R]][[theta].sub.2].

(b) Inspect no units, if [[C.sup.(2)].sub.I] [greater than] ([[delta].sub.1] - [[C.sup.(2)].sub.R])[[theta].sub.2].

(c) Inspect [n.sub.1] units, if [(1 - [[theta].sub.1])[[delta].sub.1] + [[theta].sub.1][[delta].sub.2] - [[C.sup.(2)].sub.R]][[theta].sub.2] [less than] [[C.sup.(2)].sub.I] [less than or equal to] ([[delta].sub.1] - [[C.sup.(2)].sub.R])[[theta].sub.2].

Here, [[delta].sub.1] and [[delta].sub.2] are defined in (16).

Proof. When [n.sub.2] [less than] [n.sub.1], we have

[[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2] + [phi]([n.sub.1],[[theta].sub.1],[n.sub.2] + 1) - [phi]([n.sub.1],[[theta].sub.1],[n.sub.2])

= [[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2] + EC([X.sub.1] [conjuction] [X.sub.2]) - EC([X.sub.1] [conjuction] [Z.sub.2])

= [[C.sup.(2)].sub.I] + [[theta].sub.2]([[C.sup.(2)].sub.R]- [[delta].sub.1]). (20)

When [n.sub.2] [greater than or equal to] [n.sub.1], we have

[[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2] + [phi]([n.sub.1],[[theta].sub.1],[n.sub.2] + 1) - [phi]([n.sub.1],[[theta].sub.1],[n.sub.2])

= [[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2] + EC([Z.sub.1] [conjuction] [X.sub.2]) - EC([Z.sub.1] [conjuction] [Z.sub.2])

= [[C.sup.(2)].sub.I] + [[theta].sub.2][[[C.sup.(2)].sub.R] - (1 - [[theta].sub.1])[[delta].sub.1] - [[theta].sub.1][[delta].sub.2]]. (21)

Here and below, we write [Z.sub.i] := [Z.sub.i]([[theta].sub.i]), for i= 1,2. Note that both (20) and (21) are independent of [n.sub.2]. If [[C.sup.(2)].sub.I] falls into the range in case (a), then both (20) and (21) are nonpositive, taking into account [[delta].sub.1] [greater than or equal to] [[delta].sub.2]. This means that it is better to stop inspection after [n.sub.2] + 1 (instead of [n.sub.2]) units have been inspected, for any [n.sub.2] [less than] N. Therefore, all units of component 2 should be inspected.

In the case of (b), both (20) and (21) are nonnegative. And hence, it is always better to stop inspection at [n.sub.2] than at [n.sub.2] + 1, which implies that it is optimal to inspect no units at all.

In the case of (c), (20) is nonpositive while (21) is nonnegative. This means that continuing inspection is better than stopping inspection when [n.sub.2] [less than] [n.sub.1], while stopping becomes better if [n.sub.2] [greater than or equal to] [n.sub.1]. Therefore, exactly [n.sub.2] = [n.sub.1] units of component 2 should be inspected.

Let

[phi]'([n.sub.1],[[theta].sub.1]) := [min.sub.[0[less than or equal to][n.sub.2][less than or equal to]N] {[phi]([n.sub.1],[[theta].sub.1][n.sub.2]) + [n.sub.2]([[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2])} (22)

denote the expected cost-to-go given [[theta].sub.1] = [[theta].sub.1], and exactly [n.sub.1] units of component 1 have been inspected. Then, from Lemma 4, we have

[phi]'([n.sub.1],[[theta].sub.1]) = [n.sub.1]EC([X.sub.1] [conjuction] [Z.sub.2]) + (N - [n.sub.1])EC([Z.sub.1] [conjuction] [Z.sub.2]) (23)

if [[C.sup.(2)].sub.I] [greater than] [[theta].sub.2]([[delta].sub.1] - [[C.sup.(2)].sub.R]);

[phi]'([n.sub.1],[[theta].sub.1]) = [n.sub.1]EC([X.sub.1] [conjuction] [X.sub.2]) + (N - [n.sub.1])EC([Z.sub.1] [conjuction] [X.sub.2])

+ [[NC.sup.(2)].sub.I] + [[NC.sup.(2)].sub.R][[theta].sub.2] (24)

if [[C.sup.(2)].sub.I] [less than or equal to] [[theta].sub.2][(1 - [[theta].sub.1])[[delta].sub.1] + [[theta].sub.1][[delta].sub.2] - [[C.sup.(2)].sub.R]; and

[phi]'([n.sub.1],[[theta].sub.1]) = [n.sub.1]EC([X.sub.1] [conjuction] [X.sub.2]) + (N - [n.sub.1])EC([Z.sub.1] [conjuction] [Z.sub.2])

+ [n.sub.1][[C.sup.(2)].sub.I] + [n.sub.1] [[C.sup.(2)].sub.R][[theta].sub.2] (25)

if [[theta].sub.2][(1 - [[theta].sub.1])[[delta].sub.1] + [[theta].sub.1][[delta].sub.2] - [[C.sup.(2)].sub.R]] [less than] [[C.sup.(2)].sub.I] [less than or equal to] [[theta].sub.2]([[delta].sub.1] - [[C.sup.(2)].sub.R]).

Denote

[phi]'([n.sub.1],[d.sub.1]) := E[[phi]'([n.sub.1],[[theta].sub.1])\[D.sub.1]([n.sub.1]) = [d.sub.1]]. (26)

Note that from the dynamic programming formulation, in general we may have different optimal actions (i.e., in terms of inspecting component 1 or 2, or stopping inspection) in different states, and may switch actions many times between the two components before stopping the inspection. Let us now focus on a specific class of policies, which we call a single-switch policy: starting from (0, 0, 0), we begin with inspecting component 1; and once we decide to switch to inspecting component 2, we will never again switch back to inspecting component 1. Note that with a single-switch policy, if we stop inspecting component 1 at ([n.sub.1],[d.sub.1]) (i.e., when [n.sub.1] units have been inspected, of which [d.sub.1] are defective), the expected cost-to-go is [phi]'([n.sub.1],[d.sub.1]), which can be obtained by inspecting component 2 following the optimal inspection rule in Lemma 4, with [[theta].sub.1] = [[theta].sub.1]([n.sub.1],[d.sub.1]), the conditional defect rate of component 1 at ([n.sub.1],[d.sub.1]). Let [psi]'([n.sub.1],[d.sub.1]) be the expected cost-to-go, if we continue to inspect component 1; and let V'([n.sub.1],[d.sub.1]) be the minimal expected cost-to-go by following a single-switch policy, starting from ([n.sub.1],[d.sub.1]). Then,

V'([n.sub.1],[d.sub.1]) = min{[phi]'([n.sub.1],[d.sub.1]), [psi]'([n.sub.1],[d.sub.1])} if [n.sub.1] [less than] N,

V'([n.sub.1],[d.sub.1]) = [phi]'([n.sub.1],[d.sub.1]) if [n.sub.1] = N,

and

[psi]'([n.sub.1],[d.sub.1]) = [[C.sup.(1)].sub.I] + [[C.sup.(1)].sub.R][[theta].sub.1]([n.sub.1],[d.sub.1]) + E[V'([n.sub.1] + 1, [d.sub.1] + [I.sub.1]([n.sub.1],[d.sub.1]))] if [n.sub.1] [less than] N. (27)

Theorem 1 below points Out that the optimal inspection policy (for the case of component 2 having a constant defective rate) lies within the class of single-switch policies.

Recall that [phi]([n.sub.1],[d.sub.1],[n.sub.2]), [[psi].sub.1]([n.sub.1],[d.sub.1],[n.sub.2]), [[psi].sub.2]([n.sub.1],[d.sub.1],[n.sub.2]) and V([n.sub.1],[d.sub.1],[n.sub.2]) denote the expected costs-to-go starting from state ([n.sub.1],[d.sub.1],[n.sub.2]), respectively, for stopping inspection, continuing inspecting component 1, continuing inspecting component 2, and following the global optimal policy.

Theorem 1. V'([n.sub.1],[d.sub.1]) = V([n.sub.1],[d.sub.1],0) for all ([n.sub.1],[d.sub.1]). Consequently, it is optimal to follow a single-switch policy that starts with inspecting component 1, and then switches to inspecting component 2 following the rule described in Lemma 4 (with [[theta].sub.1] = [[theta].sub.1]([n.sub.1],[d.sub.1]), provided the switching takes place at ([n.sub.1],[d.sub.1])).

Proof. Obviously, we have V'([n.sub.1],[d.sub.1]) [greater than or equal to] V([n.sub.1],[d.sub.1],0), following the optimality of V. Below, we prove

V'([n.sub.1],[d.sub.1]) [less than or equal to] V([n.sub.1],[d.sub.1],0), (28)

by induction on [n.sub.1]. When [n.sub.1] = N, there is no uninspected component 1, and hence,

V([N.sub.1],[d.sub.1],0) = V'([N.sub.1],[d.sub.1]),

holds trivially.

Assuming (28) holds true for all [n.sub.1] [greater than or equal to] k + 1, we now prove it holds for [n.sub.1] = k. Let [phi]'([n.sub.1],[d.sub.1]) and [psi]'([n.sub.1],[d.sub.1]) denote the cost-to-go functions, respectively, for stopping and continuing inspection, in the single-switch policy. Clearly, we have [phi]([n.sub.1],[d.sub.1],0) [greater than or equal to] [phi]'([n.sub.1],[d.sub.1]), since there might be some inspected component 2 included in [phi]', whereas there is no such component in [phi]. Note that we also have

[[psi].sub.1]([n.sub.1],[d.sub.1],0) = [[C.sup.(1)].sub.I] + [[C.sup.(1)].sub.R][[theta].sub.1]([n.sub.1],[d.sub.1])

+ EV([n.sub.1] + 1,[d.sub.1] + [I.sub.1]([n.sub.1],[d.sub.1]),0)

[greater than or equal to] [[C.sup.(1)].sub.I] + [[C.sup.(1)].sub.R][[theta].sub.1]([n.sub.1],[d.sub.1])

+ EV'([n.sub.1] + 1,[d.sub.1] + [I.sub.1]([n.sub.1],[d.sub.1]))

= [psi]'([n.sub.1],[d.sub.1]),

where the inequality follows from the induction hypothesis. If

[[psi].sub.2]([n.sub.1],[d.sub.1],0) [greater than or equal to] min{[phi]([n.sub.1],[d.sub.1],0), [[psi].sub.1]([n.sub.1],[d.sub.1],0)}, (29)

then

V([n.sub.1],[d.sub.1],0) = min{[phi]([n.sub.1],[d.sub.1],0), [[psi].sub.1]([n.sub.1],[d.sub.1],0)}

[greater than or equal to] min{[phi]'([n.sub.1],[d.sub.1]), [psi]([n.sub.1],[d.sub.1])}

= V'([n.sub.1],[d.sub.1]),

which is what is desired. On the other hand, if

[[psi].sub.2]([n.sub.1],[d.sub.1],0) [less than] min{[phi]([n.sub.1],[d.sub.1],0), [[psi].sub.1]([n.sub.1],[d.sub.1],0)},

then following Lemma 3, starting from ([n.sub.1],[d.sub.1],[n.sub.2]), we should not inspect any more units of component 1. Hence,

V([n.sub.1],[d.sub.1],0) = [phi]'([n.sub.1],[d.sub.1]) [greater than or equal to] V'([n.sub.1],[d.sub.1]).

Below, we develop the optimal inspection policy for component 1, i.e., the policy before switching to inspecting component 2. To this end, we need to show that the [phi]' function in (22) satisfies a stronger form of submodularity, called K-submodularity in Chen et al. (1998). A bivariate function, g(x,y), is K-submodular for some K [greater than or equal to] 0, if we have,

[g([x.sub.1],[y.sub.2]) + g([x.sub.2],[y.sub.1])] - [g([x.sub.1],[y.sub.1]) + g([x.sub.2],[y.sub.2])] [greater than or equal to] K([x.sub.1] - [x.sub.2])([y.sub.1] - [y.sub.2]),

for all [x.sub.1] [greater than or equal to] [x.sub.2] and [y.sub.1] [greater than or equal to] [y.sub.2]. When K = 0, K-submodularity specializes to the standard submodularity property (Topkis, 1978).

Lemma 5. [phi]'([n.sub.1],[[theta].sub.1]) is K-submodular in ([n.sub.1],[[theta].sub.1]) with K = [[C.sup.(1)].sub.R].

Proof. Suppose [[theta].sub.1] [less than] [[theta]'.sub.1]. We want to show

[phi]'([n.sub.1],[[theta].sub.1]) - [phi]'([n.sub.1] + 1,[[theta].sub.1]) + [phi]'([n.sub.1] + 1,[[theta]'.sub.1]) - [phi]'([n.sub.1],[[theta]'.sub.1])

+ [[C.sup.(1)].sub.R] ([[theta]'.sub.1] - [[theta].sub.1]) [less than or equal to] 0. (30)

We shall establish the above inequality considering several cases corresponding to the range of values of [[C.sup.(2)].sub.I]. For convenience, denote [Z'.sub.i] := [Z.sub.i]([[theta]'.sub.i]) for i = 1,2.

If [[C.sup.(2)].sub.I] [greater than] [[theta].sub.2]([[delta].sub.1] - [[C.sup.(2)].sub.R]), by (23) the LHS (Left Hand Side) of (30) becomes

EC([Z.sub.1] [conjunction] [Z.sub.2]) - EC([X.sub.1] [conjunction] [Z.sub.2]) + EC([X.sub.1] [conjunction] [Z.sub.2])

- EC([Z'.sub.1] [conjunction] [Z.sub.2]) + [[C.sup.(1)].sub.R]([[theta]'.sub.1] - [[theta].sub.1])

= {[[C.sup.(1)].sub.R] - [EC([Y.sub.1] [conjunction] [Z.sub.2]) - EC([X.sub.1] [conjunction] [Z.sub.2])]}([[theta]'.sub.1] - [[theta].sub.1])

= [[[theta].sub.2]{[[C.sup.(1)].sub.R] - [EC([Y.sub.1] [conjunction] [Y.sub.2]) - EC([X.sub.1] [conjunction] [Y.sub.2])]} + (1 - [[theta].sub.2])

x {[[C.sup.(1)].sub.R] - [EC([Y.sub.1] [conjunction] [X.sub.2]) - EC([X.sub.1] [conjunction] [X.sub.2])]}]([[theta]'.sub.1] - [[theta].sub.1])

[less than or equal to] 0,

where the inequality follows from (14, 15).

If [[C.sup.(2)].sub.I] [less than or equal to] [(1 - [[theta]'.sub.1])[[delta].sub.1] + [[theta]'.sub.1][[delta].sub.2] - [[C.sup.(2)].sub.R]][[theta].sub.2], since [[delta].sub.1] [greater than or equal to] [[delta].sub.2], we have

[[C.sup.(2)].sub.I] [less than or equal to] [(1 - [[theta].sub.1])[[delta].sub.1] + [[theta].sub.1][[delta].sub.2] - [[C.sup.(2)].sub.R]][[theta].sub.2],

and hence, the LHS of (30) is equal to

EC([Z.sub.1] [conjunction] [X.sub.2]) - EC([X.sub.1] [conjunction] [X.sub.2]) + EC([X.sub.1] [conjunction] [X.sub.2])

- EC([Z'.sub.1] [conjunction] [X.sub.2]) + [[C.sup.(1)].sub.R]([[theta]'.sub.1] - [[theta].sub.1])

= {[[C.sup.(1)].sub.R] - [EC([Y.sub.1] [conjunction] [X.sub.2]) - EC([X.sub.1] [conjunction] [X.sub.2])]}([[theta]'.sub.1] - [[theta].sub.1])

[less than or equal to] 0.

Here the inequality, again, follows from (14).

Next, suppose

(1 - [[theta].sub.1])[[delta].sub.1] + [[theta].sub.1][[[delta].sub.2] - [[C.sup.(2)].sub.R]][[theta].sub.2] [less than] [[C.sup.(2)].sub.I] [less than or equal to] [[theta].sub.2]([[delta].sub.1] - [[C.sup.(2)].sub.R]).

Note that this implies

[[C.sup.(2)].sub.I] [greater than or equal to] [(1 - [[theta]'.sub.1])[[delta].sub.1] + [[theta]'.sub.1][[delta].sub.2] - [[C.sup.(2)].sub.R]][[theta].sub.2].

The LHS of (30) is then equal to

EC([Z.sub.1] [conjunction] [Z.sub.2]) - EC([Z'.sub.1] [conjunction] [Z.sub.2]) + [[C.sup.(1)].sub.R]([[theta]'.sub.1] - [[theta].sub.1])

= ([[theta]'.sub.1] - [[theta].sub.1]){[[theta].sub.2][EC([X.sub.1] [conjunction] [Y.sub.2]) - EC([Y.sub.1] [conjunction] [Y.sub.2]) + [[C.sup.(1)].sub.R]]

+ (1 - [[theta].sub.2])[EC([X.sub.1] [conjunction] [X.sub.2]) - EC([Y.sub.1] [conjunction] [X.sub.2]) + [[C.sup.(1)].sub.R]]}

[less than or equal to] 0.

The last case is

[(1 - [[theta]'.sub.1])[[delta].sub.1] + [[theta]'.sub.1][[delta].sub.2] - [[C.sup.(2)].sub.R]][[theta].sub.2]

[less than] [[C.sup.(2)].sub.I] [less than or equal to] [(1 - [[theta].sub.1])[[delta].sub.1] + [[theta].sub.1][[delta].sub.2] - [[C.sup.(2)].sub.R]][[theta].sub.2]. (31)

In this case, (30) becomes

[[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2] + EC([Z.sub.1] [conjunction] [X.sub.2]) - EC([Z'.sub.1] [conjunction] [Z.sub.2])

+ ([[theta]'.sub.1] - [[theta].sub.1])[[C.sup.(1)].sub.R] [less than or equal to] 0,

which is equivalent to

[[C.sup.(2)].sub.I] + [[C.sup.(2)].sub.R][[theta].sub.2] + [[theta]'.sub.1][[theta].sub.2]([[delta].sub.1] - [[delta].sub.2]) - [[theta].sub.2][[delta].sub.1] - ([[theta]'.sub.1] - [[theta].sub.1])

x [EC([Y.sub.1] [conjunction] [X.sub.2]) - EC([X.sub.1] [conjunction] [X.sub.2]) - [[C.sup.(1)].sub.R]] [less than or equal to] 0.

With condition (31), it suffices to show:

([[theta]'.sub.1] - [[theta].sub.1]){[[theta].sub.2]([[delta].sub.1] - [[delta].sub.2]) - [EC([Y.sub.1] [conjunction] [X.sub.2]) - EC([X.sub.1] [conjunction] [X.sub.2]) - [[C.sup.(1)].sub.R]]}

[less than or equal to] 0,

or equivalently,

(1 - [[theta].sub.2])[EC([Y.sub.1] [conjunction] [X.sub.2]) - EC([X.sub.1] [conjunction] [X.sub.2]) - [[C.sup.(1)].sub.R]]

+ [[theta].sub.2][EC([Y.sub.1] [conjunction] [Y.sub.2]) - EC([X.sub.1] [conjunction] [Y.sub.2]) - [[C.sup.(1)].sub.R]] [greater than or equal to] 0,

which follows from (1) and (4).

In view of the above results, with the [phi]'([n.sub.1],[d.sub.1]) and [phi]'([n.sub.1], [d.sub.1]) defined in (26) and (27), by exactly the same argument as in Theorem 5.2 and Theorem 5.4 of Chen et al. (1998), we can prove

Lemma 6. [phi]'([n.sub.1], [d.sub.1]) - [phi]'([n.sub.1], [d.sub.1]) is decreasing in [d.sub.1] and increasing in [n.sub.1].

For 0 [less than or equal to] [n.sub.1] [less than or equal to] N, let

[[d.sup.*].sub.1,[n.sub.1]] := min{[d.sub.1] [less than or equal to] [n.sub.1] : [phi]'([n.sub.1], [d.sub.1]) [less than] [phi]'([n.sub.1], [d.sub.1])}. (32)

If [phi]'([n.sub.1], [d.sub.1]) [greater than or equal to] [phi]'([n.sub.1], [d.sub.1]) for all [d.sub.1] [less than or equal to] [n.sub.1], we define [[d.sup.*].sub.1,[n.sub.1]] := [n.sub.1] + 1.

Theorem 2. (a) It is optimal to stop inspecting component 1 at ([n.sub.1], [d.sub.1]) if and only if [d.sub.1] [less than] [[d.sup.*].sub.1,[n.sub.1]] . (b) [[d.sup.*].sub.1,[n.sub.1]] is increasing in [n.sub.1], i.e., [[d.sup.*].sub.1,[n.sub.1]] [less than or equal to] [[d.sup.*].sub.1,[n.sub.1]+1].

Proof. Note that it is optimal to stop inspecting component 1 at ([n.sub.1], [d.sub.1]) if and only if

[phi]'([n.sub.1], [d.sub.1]) [greater than or equal to] [phi]'([n.sub.1], [d.sub.1]),

which is equivalent to [d.sub.1] [less than] [[d.sup.*].sub.1,[n.sub.1]], since [phi]'([n.sub.1], [d.sub.1]) - [phi]'([n.sub.1], [d.sub.1]) is decreasing in [d.sub.1] from Lemma 6. This proves (a). For (b), note that [phi]'([n.sub.1] + 1, [d.sub.1]) [less than] [phi]'([n.sub.1] + 1, [d.sub.1]) implies [phi]'([n.sub.1], [d.sub.1]) [less than] [phi]'([n.sub.1], [d.sub.1]), since [phi]'([n.sub.1], [d.sub.1]) - [phi]'([n.sub.1], [d.sub.1]) is increasing in [n.sub.1]. Hence,

{[d.sub.1] [less than or equal to] [n.sub.1] : [phi]'([n.sub.1], [d.sub.1]) [less than] [phi]'([n.sub.1], [d.sub.1])}

[contains or equal to] {[d.sub.1] [less than or equal to] [n.sub.1] : [phi]'([n.sub.1] + 1,[d.sub.1]) [less than] [phi]'([n.sub.1] + 1, [d.sub.1])},

which implies [[d.sup.*].sub.1,[n.sub.1]] [less than or equal to] [[d.sup.*].sub.1,[n.sub.1]+1].

Note that from (26),

[phi]'([n.sub.1], [d.sub.1]) = E[[phi]'([n.sub.1], [[theta].sub.1])\[D.sub.1]([n.sub.1]) = [d.sub.1]],

and for given [[theta].sub.1], [phi]'([n.sub.1], [[theta].sub.1]) is calculated through (23), (24) or (25), corresponding to different values of [[theta].sub.2]. Hence, in general, both [phi]'([n.sub.1], [d.sub.1]) and [phi]'([n.sub.1], [d.sub.1]), as well as [[d.sup.*].sub.1,[n.sub.1]], depend on [[theta].sub.2], the defective rate of component 2.

In summary, we have

Theorem 3. In the case when component 2 has a constant defect rate [[theta].sub.2], the following single-switch policy is optimal:

* First inspect the batch of component 1, then inspect the batch of component 2.

* Component 1 is inspected following the threshold rule in Theorem 2.

* Suppose the inspection of component 1 stops at ([n.sub.1],[d.sub.1]) (i.e., [n.sub.l] units have been inspected, of which [d.sub.1] units are found to be defective), then component 2 is inspected following the rule in Lemma 4, with [[theta].sub.1] = E[[[theta].sub.1]\[D.sub.1]([n.sub.1]) = [d.sub.1]].

Note that by symmetry, if component 1, instead of component 2, has a constant defect rate, we have the same inspection policy, simply by switching the role of the two components in the above discussion.

To conclude this section, we consider the further specialized case when both components have constant defective rates, i.e., [[theta].sub.1] [equivalent] [[theta].sub.1], and [[theta].sub.2] [equivalent] [[theta].sub.2], the problem is much simpler. Since there is no information concerning the quality of the two components as inspection progresses in this case, it becomes a static optimization with decision variables [n.sub.1] and [n.sub.2], the number of units to inspect from the two components. Note that there is a symmetry among all assembled end products, such that every product should follow the same (optimal) decision regarding whether or not to inspect the two components that are assembled to form the product. In other words, all we need is to find the best among the four decisions, for each pair of components (any pair among the N pairs): inspect both components, inspect component 1 only, inspect component 2 only, and inspect neither. These correspond to the following costs:

[[C.sup.(1)].sub.I] + [[theta].sub.1][[C.sup.(1)].sub.R] + [[C.sup.(2)].sub.I] + [[theta].sub.2][[C.sup.(2)].sub.R] + EC([X.sub.1] [conjunction] [X.sub.2]),

[[C.sup.(1)].sub.I] + [[theta].sub.1][[C.sup.(1)].sub.R] + EC([X.sub.1] [conjunction] [Z.sub.2]),

[[C.sup.(2)].sub.I] + [[theta].sub.2][[C.sup.(2)].sub.R] + EC([Z.sub.1] [conjunction] [X.sub.2]), EC([Z.sub.1] [conjunction] [Z.sub.2]).

(In particular, note that here N plays no role in the decision.)

By comparing the four costs above we can easily specify the ranges for the values of [[theta].sub.1] and [[theta].sub.2], and the corresponding optimal solution ([[n.sup.*].sub.1],[[n.sup.*].sub.2]), which are summarized below:

(a) [[n.sup.*].sub.1] = 0, [[n.sup.*].sub.2] = N if [[theta].sub.1] [less than] [[[theta].sup.*].sub.1a] and [[theta].sub.2] [greater than or equal to] [[[theta].sup.*].sub.2b];

(b) [[n.sup.*].sub.1] = [[n.sup.*].sub.2] = N if [[theta].sub.1] [greater than or equal to] [[[theta].sup.*].sub.1a] and [[theta].sub.2] [greater than or equal to] [[[theta].sup.*].sub.2b], or if [[theta].sub.1] [greater than or equal to] [[[theta].sup.*].sub.1c] and [[[theta].sup.*].sub.2a] [less than or equal to] [[theta].sub.2] [less than] [[[theta].sup.*].sub.2b];

(c) [[n.sup.*].sub.1] = [[n.sup.*].sub.2] = 0 if [[theta].sub.1] [less than] [[[theta].sup.*].sub.1b] and [[theta].sub.2] [less than] [[[theta].sup.*].sub.2a], or if [[theta].sub.1] [less than] [[[theta].sup.*].sub.1c] and [[[theta].sup.*].sub.2a] [less than or equal to] [[theta].sub.2] [less than] [[[theta].sup.*].sub.2b];

(d) [[n.sup.*].sub.1] = N, [[n.sup.*].sub.2] = 0 if [[theta].sub.1] [greater than or equal to] [[[theta].sup.*].sub.1b] and [[theta].sub.2] [less than] [[[theta].sup.*].sub.2a].

Here

[[[theta].sup.*].sub.1a] := [[C.sup.(1)].sub.I]/[[delta]'.sub.1] - [[C.sup.(1)].sub.R], [[[theta].sup.*].sub.1b] := [[C.sup.(1)].sub.I]/(1 - [[theta].sub.2])[[delta]'.sub.1] + [[theta].sub.2][[delta]'.sub.2] - [[C.sup.(1)].sub.R],

[[[theta].sup.*].sub.1c] := [[C.sup.(1)].sub.I] + [[C.sup.(2)].sub.I] - [[theta].sub.2]([[delta].sub.1] - [[C.sup.(2)].sub.R])/(1 - [[theta].sub.2])[[delta]'.sub.1] + [[theta].sub.2][[delta]'.sub.2] - [[C.sup.(1)].sub.R],

[[[theta].sup.*].sub.2a] := [[C.sup.(2)].sub.I]/[[delta].sub.1] - [[C.sup.(2)].sub.R], and [[[theta].sup.*].sub.2b] := [[C.sup.(2)].sub.I]/(1 - [[theta].sub.1])[[delta].sub.1] + [[theta].sub.1][[delta].sub.2] - [[C.sup.(2)].sub.R],

with

[[delta]'.sub.1] := E[C([Y.sub.1] [conjunction] [X.sub.2]) - C([X.sub.1] [conjunction] [X.sub.2])],

[[delta]'.sub.2] := E[C([Y.sub.1] [conjunction] [Y.sub.2]) - C([X.sub.1] [conjunction] [Y.sub.2])],

and [[delta].sub.1] and [[delta].sub.2] defined in (16).

5. A heuristic policy

Here we propose a threshold type single-switch heuristic policy to the original problem (i.e., with both components having random defect rates), based on the optimal policy for the special case (of component 2 having a constant defect rate) in Theorem 3.

For each pair of ([n.sub.2],[d.sub.2]), with [n.sub.2] = 0, 1,...,N, and [d.sub.2] [less than or equal to] [n.sub.2], denote [[d.sup.*].sub.1,[n.sub.1]]([n.sub.2],[d.sub.2]), [n.sub.1] = 0, 1,...,N - 1, as the thresholds for inspecting component 1 as in Theorem 2, by assuming component 2 has a constant defect rate [[theta].sub.2] = E[[[theta].sub.2]\[D.sub.2]([n.sub.2]) = [d.sub.2]]. Similarly, by switching the role of component 1 and component 2, we can define [[d.sup.*].sub.2,[n.sub.2]]([n.sub.1],[d.sub.1]); [n.sub.2] = 0, 1,...,N - 1 as the thresholds for inspecting component 2 for each pair of ([n.sub.1],[d.sub.1]), assuming component 1 has constant defect rate [[theta].sub.1] = E[[[theta].sub.1]\[D.sub.1]([n.sub.1]) = [d.sub.1]].

Based on these thresholds, we have the following two policies:

* Policy I. Start with inspecting component 1 in state (0, 0, 0, 0), following the single-switch threshold rule below:

(1) inspect component 1 one unit at a time, and switch to inspecting component 2 at ([n.sub.1], [d.sub.1], 0, 0) if and only if [d.sub.1] [less than] [[d.sup.*].sub.1,[n.sub.1]] := [[d.sup.*].sub.1,[n.sub.1]] (0,0), or [n.sub.1] = N;

(2) inspect component 2 one unit a time, and stop inspection in state ([n.sub.1], [d.sub.1], [n.sub.2], [d.sub.2]) if and only if [d.sub.2] [less than] [[d.sup.*].sub.2,[n.sub.2]] ([n.sub.1],[d.sub.1]) or [n.sub.2] = N.

* Policy II. Start with inspecting component 2 in state (0, 0, 0, 0), following the single-switch threshold rule below:

(1) inspect component 2 one unit at a time, and switch to inspecting component 1 at (0, 0, [n.sub.2], [d.sub.2]) if and only if [d.sub.2] [less than] [[d.sup.*].sub.2,[n.sub.2]] := [[d.sup.*].sub.2,[n.sub.2]] (0, 0), or [n.sub.2] = N;

(2) inspect component 1 one unit a time, and stop inspection at state ([n.sub.1], [d.sub.1], [n.sub.2], [d.sub.2]) if and only if [d.sub.1] [less than] [[d.sup.*].sub.1,[n.sub.1]]([n.sub.2],[d.sub.2]) or [n.sub.1] = N.

For a given problem, we can easily calculate the expected cost under each of these two policies. The one with a lower cost is then chosen as our heuristic inspection policy.

Numerical examples have shown that the heuristic policy has a very good performance: the difference between the expected cost of the heuristic policy and the optimal expected cost is negligible in all examples we tested.

Below, we illustrate the performance of this heuristic policy in two examples, and compare it against the optimal policy. In addition, we also compare it against the solution obtained by treating the defect rates of both components as constants, i.e., assuming [[theta].sub.1] [equivalent] E[[[theta].sub.1]] and [[theta].sub.2] [equivalent] E[[[theta].sub.2]].

Example 1 Suppose N = 30; [[C.sup.(1)].sub.I] = 6.5, [[C.sup.(2)].sub.I] = 6.3; [[C.sup.(1)].sub.R] = 1.0, [[C.sup.(2)].sub.R] = 2.0; E[C([X.sub.1] [conjunction] [X.sub.2])] = 3.5, E[C([X.sub.1] [conjunction] [Y.sub.2])] = 18.5; E[C([Y.sub.1] [conjunction] [X.sub.2])] = 20.0, E[C([Y.sub.1] [conjunction] [Y.sub.2])] = 33.5; [[theta].sub.1] and [[theta].sub.2] are both uniformly distributed on (0,1). Note that both inequalities in (13) and (14) are satisfied in this case. The results under the different policies mentioned above are summarized below:

(i) Following the optimal policy, which is derived by solving the dynamic programming in Section 3, the expected total cost is 465.609.

(ii) Following the heuristic policy, the expected total cost is 465.614 (corresponding to Policy I, whereas the expected total cost under Policy II is 465.649). Under this policy, we start with inspecting component I in state (0,0,0,0), and switch to inspecting component 2 at ([n.sub.1],[d.sub.1],0,0) if and only if [d.sub.1] [less than] [[d.sup.*].sub.1,[n.sub.1]] or [n.sub.1] = N. Suppose we switch to inspecting component 2 at ([n.sub.1],[d.sub.1],0,0), then we stop inspection at ([n.sub.1],[d.sub.1],[n.sub.2],[d.sub.2]) if and only if [d.sub.2] [less than] [[d.sup.*].sub.2,[n.sub.2]] ([n.sub.1],[d.sub.1]) or [n.sub.2] = N. Here [[d.sup.*].sub.1,[n.sub.1]], [n.sub.1] = 0,1,...,N - 1 are given in Table 1: And [[d.sup.*].sub.2,[n.sub.2]] ([n.sub.1],[d.sub.1]), [n.sub.2] = 0,1,...,N - 1, when [n.sub.1] = 15 and [d.sub.1] = 5 for instance, are given in Table 2.

(iii) Suppose we treat the defect rates of both components as constants by assuming [[theta].sub.1] [equivalent] 0.5 and [[theta].sub.2] [equivalent] 0.5. Then, following the results derived at the end of the last section, we derive the optimal policy as to inspect all units of the two components, resulting in an expected total cost of 534.00, which is much higher that the cost achieved under the heuristic policy.

Example 2 Suppose N = 30; [[C.sup.(1)].sub.I] = 3.5, [[C.sup.(2)].sub.I] = 2.3; [[C.sup.(1)].sub.R] = 2.0, [[C.sup.(2)].sub.R] = 2.5; E[C([X.sub.1] [conjunction] [X.sub.2])] = 3.5, E[C([X.sub.1] [conjunction] [Y.sub.2])] = 18.5, E[C([Y.sub.1] [conjunction] [X.sub.2])] = 20.0, E[C([Y.sub.1] [conjunction] [Y.sub.2])] = 33.5; [[theta].sub.1] is uniformly distributed on (0.05, 0.40), and [[theta].sub.2] uniformly distributed on (0.05, 0.50).

For this problem, the total costs under the optimal policy, the heuristic policy, and the policy corresponding to treating both defect rates as constants are, respectively, 297.357, 297.360 and 306.00.

6. Concluding remarks

In discussion above, we focus on the case of individual warranty costs. We expect that the results are applicable to the case with more general warranty cost functions, discussed in Section 2. Besides, the model studied in this paper can be extended to include M components, with M [greater than] 2. Analogous to the heuristic policy that treats one of the two components as having a constant defect rate, in the general case we will need to treat M - 1 components, i.e., all but one component, as having constant defect rates. The main difficulty is then to prove the K - submodularity of the [phi]'(.) function, which still follows the definition in (22) but with [n.sub.1] replaced by an M - 1 dimensional vector. Another possible extension is to allow inspection for the end product. In this case we need to consider the coordination of quality control between the components and the end products, in addition to the coordination among the components. In this case, the two-stage coordination model studied in Yao and Zheng (1999b) will help.

Biography

Shaohui Zheng received an M.S. degree in Operations Research/Optimal Control from the Academy of Sciences of China, Beijing in 1987, and a Ph.D. degree in Operations Research from Columbia Univeristy, New York in 1994. He has been an Assistant Professor at the School of Business and Management at the Hong Kong University of Science and Technology since 1994. While on sabbatical in 1997, he was an Adjunct Assistant Professor at the Industrial Engineering and Operations Research Department at Columbia University. His research interests include quality control, production and inventory management, and Markov decision programming. He is a holder of a patent in manufacturing management.

Acknowledgement

Research supported in part by Hong Kong RGC Competitive Earmarked Research Grant HKUST622O/97H. The author thanks David Yao and Jinfa Chen for their valuable input, in particular at the earlier stages of this research.

References

Ballou, D. and Pazer, H. (1982) The impact of inspector facility on the inspection policy in serial production systems. Management Science, 28, 387-399.

Blischke, W.R. (1990) Mathematical models for analysis of warranty policies. Mathematical and Computer Modelling, 13, 1-16.

Britney, R.R. (1972) Optimal screening plans for non-serial production systems. Management Science, 18, 550-559.

Chen, J. (1997) Substitution and inspection models in production-inventory systems. Ph.D. Dissertation, IEOR Dept., Columbia University, New York.

Chen, J., Yao, D.D. and Zheng, S. (1998) Quality control for finished products under warranty. Operations Research, 46, 107-115.

Djamaludin, I., Murthy, D.N,P. and Wilson, R.J. (1994) Quality control through lot sizing for items sold with warranty. International Journal of Production Economics, 33, 97-107.

Eppen, G.D. and Hurst, E.G. (1974) Optimal location of inspection stations in a multistage production process. Management Science, 20, 1194-1200.

Glasserman, P. and Wang, Y. (1998) Leadtime-inventory trade-offs in assemble-to-order systems. Operations Research, 46, 858-871.

Gunter, S.I. and Swanson L.A. (1985) Inspector location in convergent production lines. International Journal of Production Research, 23, 1153-1169.

Ross, S.M. (1983) Stochastic Processes, John Wiley & Sons, New York.

Song, J., Xu, S. and Liu, B. (1999) Order-fulfillment reliability in an assemble-to-order system with stochastic leadtimes. Operations Research, 47, 131-149.

Tapiero, C.S. and Lee, H.L. (1989) Quality control and product servicing: a decision framework. European Journal of Operations Research, 39, 261-273.

Topkis, D.M. (1978) Minimizing a submodular function on a lattice. Operations Research, 26, 305-321.

Yao, D.D. (1988) Optimal run quantities for an assembly system with random yields. IIE Transactions, 20(4), 399-403.

Yao, D.D. and Zheng, S. (1999a) Sequential inspection under capacity constraints. Operations Research, 47, 410-421.

Yao, D.D. and Zheng, S. (1999b) Coordinated quality control in a two-state system. IEEE Transactions on Automatic Control, 44, 1166-1179.