The economic lot and delivery scheduling problem: common cycle, rework, and variable production...

The economic lot and delivery scheduling problem is to simultaneously determine the production sequence of several assembly components at a supplier and the delivery interval of those components to the customer. The customer, an assembly facility, is assumed to use the components at a constant

rate. The objective is to find the production sequence and delivery interval that minimize the holding, setup, and transportation cost for the supply chain. Previous solutions to the problem assume a constant production rate for each component and that all components are of acceptable quality. These assumptions ignore volume flexibility and quality cost. Volume flexibility permits a system to adjust the production rate upwards or downwards within wide limits. Also, component quality may deteriorate with larger lot sizes and decreased unit production times. In this paper, we develop an algorithm for solving the economic lot and delivery scheduling problem for a supplier using a volume flexible production system where com ponent quality depends on both lot sizes and unit production times. We test the performance of the algorithm and illustrate the models with numerical examples.

1. Introduction

Consider the problem faced by a supplier that produces multiple components on a single production line or machine, accumulates these components, and then delivers them to an assembly facility [1-3]. The Economic Lot and Delivery Scheduling Problem (ELDSP) is to find the production sequence and delivery time interval that would minimize the costs of setup, holding, and shipping for the supply chain. The ELDSP was introduced by Hahm and Yano [1] in their study of the linkage between a large assembly facility such as an automotive assembly plant and its immediate suppliers that are large enough to have direct shipments to the assembly plant. The authors considered a situation where the supplier is captive and supplies many components to only one assembly plant. The assumptions of the ELDSP are:

(I) the supplier produces the components on a single machine one at a time;

(II) production and usage rates are deterministic and constant;

(III) the supplier incurs sequence independent setup cost and time;

(IV) there is a single delivery from the supplier to the assembly facility per cycle, during which one batch of each component is produced;

(V) the setup cost and time for the assembly facility are negligible;

(VI) all defective units are reworked off line, which does not affect the utilization of the system;

(VII) both the supplier and the assembler incur linear holding cost on component inventory; and

(VIII) the delivery charge per shipment is fixed.

Because of the accumulation of inventory at the supplier prior to each delivery, the sequence in which components are produced affects the costs. For example, consider a problem with three components. Six sequences for production are possible. Figure 1 shows the inventory levels at the supplier for two cycles of the {2, 1, 3} sequence for a given value of the delivery cycle T.

The ELDSP is an NP-hard problem. Hahm and Yano [1] provided an excellent review of models related to the ELDSP, developed an efficient heuristic algorithm for solving it, and tested the performance of the algorithm. The experimental results showed that the algorithm identified the optimal solution for a broad range of problems, and the authors were unable to generate problems for which the algorithm did not provide optimal solutions.

In the ELDSP model, as with many other models, unit production times are assumed to be constant and all units produced are assumed to be of perfect quality. However, volume flexibility of modern production systems and the quality management literature suggest that these two assumptions may not hold. Volume flexibility is defined as the ability of a system to operate profitably at different output levels [4,5].

Several authors have analyzed versions of the Economic Lot Scheduling Problem (ELSP) in which production rates can be slowed down from their maximum and showed that substantial savings can be obtained by doing so. Silver [6] has used the Common Cycle (CC) approach to the ELSP and analyzed a case in which a constant production rate can be selected for each production run. Moon et al. [7] have analyzed an ELSP in which production rates can be controlled dynamically during production runs. Gallego [8] has dealt with controllable production rates but allowed different items to have different cycle times. Khouja [9] has analyzed an ELSP in which production rates can be increased from the production rates which minimize average unit cost to avoid large order quantities. These large quantities are used when utilization is high to reduce the total setup time and increase the time available for production. Khouja [10] has extended Silver's [6] model to the case of imperfect quality. Khouja [11] has extended the singl e-item ELDSP analyzed by Hahm and Yano [12] to the case of imperfect quality and variable production rates.

The assumption of perfect quality has been found to be unrealistic in many cases [13,14]. Porteus [13] has assumed the production process to be functioning perfectly at the start of production. With the production of each unit the process may shift out-of-control, with a constant known probability, and start producing all defective units. Once the process is out of control, it stays that way while the remainder of the lot is produced. The production system is restored to perfect quality when it is set up again. Based on this assumption, the number of conforming units in a lot is a random variable that depends on the transition probabilities and the lot size. The author then derived the optimal lot size. Rosenblatt and Lee [14] have assumed that once the process shifts out-of-control, it starts to produce [alpha] percent of defective products. Cheng [15] has solved an extension to the economic order quantity model in which demand exceeds supply, quality is imperfect, and the amount of demand to be satisfied i s a decision variable. Khouja and Mehrez [16] have formulated an economic production lot size model that treats production rates as decision variables and assumes the percentage of conforming components in a lot decreases as the production rate increases. The authors used the quality assumptions of Rosenblatt and Lee [14].

Models relating production rates to quality have been developed for robots [17-19]. These models relate robot repeatability, which is defined as the robot's ability to return to the same point, to product quality. Repeatability of a robot is partially determined by its speed which determines production rates. The higher is the speed of the robot, the worse is the repeatability and the poorer is the quality of the product.

The goal of this paper is to solve an ELDSP in which unit production times are decision variables and output quality depends on unit production times and lot sizes. In Section 2, we introduce the model and its solutions for two cases. In the first case, output quality depends only on lot size. In the second case, output quality also depends on unit production times. In Section 3, we present some numerical examples and test the performance of the proposed algorithm. Section 4 contains the conclusion and suggestions for future research.

2. The proposed model and its solution

Notation

j = component index, j = 1, ...,J;

[D.sub.j] = demand for component j per unit time;

[S.sub.j] = setup cost for component j;

[s.sub.j] = setup time for component j;

[H.sub.j] = inventory holding cost per unit of component j per unit time;

A = transportation cost per delivery;

[R.sub.j] = cost to rework one defective unit of component j;

[p.sub.j] production time per unit of component j, a decision variable;

T = setup interval (time between setups); also equal to the delivery interval (time between deliveries), a decision variable.

Let [i] be the index of the component produced in the ith position. With fixed unit production times, the total cost for both the supplier and the assembly facility per unit time is:

TC = [frac{A + [[[sum].sup.J].sub.j=1] [S.sub.j]}{T}] + [frac{1}{2}] T [[[[sum].sup.J].sub.j=1] [D.sub.j][H.sub.j] + [[[sum].sup.J].sub.j=1] [[D.sup.2].sub.j][p.sub.j][H.sub.j]] + [[[sum].sup.J].sub.i=1] [D.sub.[i]][H.sub.[i]] [[[sum].sup.J].sub.j=i+1] (T[D.sub.[j]][p.sub.[j]] + [s.sub.[j]]), (1)

and the ELDSP is to minimize TC subject to:

[[[sum].sup.J].sub.j=1] ([s.sub.j] + [p.sub.j][D.sub.j]T) [leq] T. (2)

Constraint (2) ensures that there is sufficient time within the delivery interval T to set up and produce the components needed at the assembly facility during T. Implicit in the construction of Equation (1) is the assumption that the supply chain is vertically integrated. Otherwise, transfer prices between the supplier and assembler, timing and terms of payment, and different costs of capital for each party will have to be considered. The heuristic algorithm of Hahm and Yano [1] builds on some results of scheduling theory [20]. Components with long processing times and low holding costs are produced early in the sequence and components with short processing time and high holding cost are produced late in the sequence. This policy ensures that components with high holding cost will not wait long to be shipped.

For small values of the transition probability [q.sub.j], Porteus [13] showed that E([U.sub.j]) = [Q.sub.j] - [[beta].sub.j](1 - [[[beta].sup.[Q.sub.j]].sub.j])/[q.sub.j], where [U.sub.j] is the number of defectives per lot of size [Q.sub.j] and [[beta].sub.j] = 1 - [q.sub.j]. Porteus showed that E([U.sub.j]) is a strictly increasing, strictly convex function of [Q.sub.j]. The expected proportion of defectives is given by:

E([U.sub.j])/[Q.sub.j] = ([Q.sub.j] - [[beta].sub.j](1 - [[[beta].sup.[Q.sub.j]].sub.j])/[q.sub.j])/[Q.sub.j],

and the direct rework cost per unit time is:

[D.sub.j][R.sub.j][([Q.sub.j] - [[beta].sub.j](1 - [[[beta].sup.[Q.sub.j]].sub.j])/[q.sub.j])/[Q.sub.j]].

Adding the rework cost to TC in (1) and simplifying gives the total expected cost per unit time:

TC1 = [frac{S + A}{T}] + [frac{1}{2}] T [[omega] + [[[sum].sup.J].sub.j=1] [[omega].sub.j][D.sub.j][p.sub.j]] + [Z.sub.1](v) + [Z.sub.2](v)T + [[[sum].sup.J].sub.j=1] [[D.sub.j][R.sub.j] - [frac{[R.sub.j][[beta].sub.j](1 - [[[beta].sup.[Q.sub.j]].sub.j])}{[q.sub.j]T}]]. (3)

where v [epsilon] C, the set of all possible production sequences,

[Z.sub.1](v) = [[[sum].sup.J].sub.i=1] [[omega].sub.[i]] [[[sum].sup.J].sub.j=i+1] [s.sub.[j]],

[Z.sub.2](v) = [[[sum].sup.J].sub.i=1] [[omega].sub.[i]] [[[sum].sup.J].sub.j=i+1] [D.sub.[j]][p.sub.[j]],

S = [[[sum].sup.J].sub.j=1] [S.sub.j],

s = [[[sum].sup.J].sub.j=1] [s.sub.j],

[[omega].sub.j] = [D.sub.j][H.sub.j], and

[omega] = [[[sum].sup.J].sub.j=1][D.sub.j][H.sub.j].

If [q.sub.j] is close to zero, then Porteus [13] shows that;

([Q.sub.j] - [[beta].sub.j](1 - [[[beta].sup.[Q.sub.j]].sub.j])/[q.sub.j])/[Q.sub.j] [cong] [q.sub.j][Q.sub.j]/2.

Thus, the total expected cost per unit time, including rework cost, is approximately:

TC1 = [frac{S + A}{T}] + [frac{1}{2}] T [[omega] + [[[sum].sup.J].sub.j=1][D.sub.j]([[omega].sub.j][p.sub.j] + [D.sub.j][R.sub.j][q.sub.j])] + [Z.sub.1](v) + [Z.sub.2](v)T. (4)

The ELDSP with rework (ELDSPR) is to minimize TC1 subject to (2) and

[p.sub.j] [geq] [[p.sup.L].sub.j] j = 1,2,...,J. (5)

Constraint (5) ensures that unit production time for component j does not go below a minimum time ([[p.sup.L].sub.j]) determined by the production technology.

For fixed production rates, the algorithm developed by Hahm and Yano [1] is modified by taking the rework cost into consideration in computing the cycle time which gives:

T1 = [sqrt{[frac{2(S + A)}{[omega] + [gamma] + [Z.sub.2](v)}]}], (6)

where

[gamma] = [[[sum].sup.J].sub.j=1][D.sub.j]([[omega].sub.j][p.sub.j] + [D.sub.j][R.sub.j][q.sub.j]).

Since (6) may not always yield a feasible solution, the optimal delivery cycle for a given production sequence is given by:

[T.sup.*] = max{T1, [tau]}, (7)

where

[tau] = [frac{[[[sum].sup.J].sub.j=1] [s.sub.j]}{1 - [[[sum].sup.J].sub.j=1][p.sub.j][D.sub.j]}] (8)

When the [p.sub.j]'s are decision variables, the transition probabilities (the [q.sub.j]'s) are expected to be a function of the [p.sub.j]'s. The smaller the unit production time of a component, the larger is the [q.sub.j]. Thus, [q.sub.j] = [f.sub.j]([p.sub.j]) where [f.sub.j] is a decreasing function.

For the remainder of the paper, we assume [q.sub.j] = [[alpha].sub.j]/[p.sub.j], which implies that the transition probability increases at an increasing rate with decreased unit production times. Substituting in (4) gives the new objective function:

Minimize TC1 = [frac{S + A}{T}] + [frac{1}{2}]T[[omega] + [[[sum].sup.J].sub.j=1][[omega].sub.j][D.sub.j][p.sub.j] + [[[sum].sup.J].sub.j=1][[D.sup.2].sub.j][R.sub.j][frac{[[alpha].sub.j ]}{[p.sub.j]}]] + [[[sum].sup.J].sub.i=1] [[omega].sub.[i]] [[[sum].sup.J].sub.j=i+1] (T[D.sub.[j]][p.sub.[j]] + [s.sub.[j]]). (9)

Because [q.sub.j] is a probability, it must satisfy 0 [leq] [q.sub.j] [leq] 1, which implies [[alpha].sub.j] [leq] [p.sub.j]. At [p.sub.j] = [[alpha].sub.j], all units produced are defective. Therefore, we assume [[alpha].sub.j] [leq] [[p.sup.L].sub.j] which implies that the lower bound on unit production times will not allow all units produced to be defective. This assumption makes the constraint [[alpha].sub.j][leq][p.sub.j] redundant. Note that for a fixed cycle time T, TC1 is convex in each [p.sub.j](because 1/[p.sub.j] is convex for [p.sub.j][greater than] 0 and other terms are linear in [p.sub.j] or are constants). Since the sum of convex functions is convex, TC1 is convex in the [p.sub.j]'s for a fixed T. Suppose [i] = j, and let [lambda] and [[lambda].sub.j] = 1,2, ...,J be the Lagrange multipliers. The Kuhn-Tucker (K-T) necessary optimality conditions for a given sequence are:

T and [p.sub.j] j= 1,2,...,J, are feasible

- [frac{S + A}{[T.sup.2]}] + [frac{1}{2}] [[omega] + [[[sum].sup.j].sub.j=1] [[omega].sub.j][D.sub.j][p.sub.j] + [[[sum].sup.J].sub.j=1] [[D.sup.2].sub.j][R.sub.j][frac{[[alpha].sub.j]}{[p.sub.j]}]] + [[[sum].sup.J].sub.i=1] [[omega].sub.[i]] [[[sum].sup.J].sub.j=i+1] [D.sub.[j]][p.sub.[j]] + [lambda] ([[[sum].sup.J].sub.j=1][p.sub.j][D.sub.j]-1) = 0, (10)

[frac{1}{2}] T [[omega].sub.j][D.sub.j] - [frac{1}{2}] T[[D.sup.2].sub.j] [R.sub.j] [frac{[[alpha].sub.j]}{[[p.sup.2].sub.j]}] + T[D.sub.j] [[[sum].sup.i-1].sub.k=1] [[omega].sub.[k]] + [lambda]T[D.sub.j] - [[lambda].sub.j] = 0 j = 1,2,...,J, (11)

[lambda]([[[sum].sup.J].sub.j=1] [s.sub.j] + T ([[[sum].sup.J].sub.j=1] [p.sub.j][D.sub.j] - 1)) = 0,(12)

[[lambda].sub.j]([[p.sup.L].sub.j] - [p.sub.j]) = 0, j = 1, 2,...,J (13)

[lambda] [geq] 0, and [[lambda].sub.j] [geq] 0, j = 1, 2,...,J (14)

From (11) when [[lambda].sub.j]= 0,

[frac{1}{2}] T[[[omega].sub.j] - [D.sub.j][R.sub.j] [frac{[[alpha].sub.j]}{[[p.sup.2].sub.j]}] + 2 [[[sum].sup.i-1].sub.k=1] [[omega].sub.[k]] + 2[lambda]] = 0 j = 1, 2,..., J, (15)

and

[[p.sup.1].sub.j] = [sqrt{[frac{[D.sub.j][R.sub.j][[alpha].sub.j]}{[[omega].sub.j] + 2 [[[sum].sup.i-1].sub.k=1] [[omega].sub.[k]] + 2[lambda]}]}], j = 1, 2,..., J (16)

Let asterisks denote variable values that satisfy the Kuhn-Tucker necessary conditions. When [[[lambda].sup.*].sub.j] [greater than] 0, (13) yields [[p.sup.*].sub.j] = [[p.sup.L].sub.j]. Thus, unit production times are:

[[p.sup.*].sub.j] = max{[[p.sup.L].sub.j], [[p.sup.1].sub.j]} j = 1, 2,..., J. (17)

If [[lambda].sup.*] = 0, then (10) yields,

T1 = [sqrt{[frac{2(S + A)}{[omega] + [[[Sigma].sup.J].sub.j=1] [[omega].sub.j][D.sub.j][p.sub.j] + 2 [[[Sigma].sup.J].sub.i=1] [[omega].sub.[i]] [[[Sigma].sup.J].sub.j=i+1] [D.sub.[j]][p.sub.[j]] + [[[Sigma].sup.J].sub.j=1] [[D.sup.2].sub.j][R.sub.j] ([[alpha].sub.j]/[p.sub.j])}]}] (18)

If T1 from (18) does not satisfy constraint (2), then T is given by (8). Thus:

[T.sup.*] = max{T1,[tau]}, (19)

and from (10), if [T.sup.*] = [tau],[[lambda].sup.*] is given by:

[lambda] = [frac{[(2(S + A)/[[tau].sup.2]) - [omega] - [[[sum].sup.J].sub.j=1] [[omega].sub.j][D.sub.j][p.sub.j]]}{2[[[[sum].sup.J].sub.j=1][p.sub.j ][D.sub.j]-1]}]+

+ [frac{[- [[[sum].sup.J].sub.j=1] [[D.sup.2].sub.j][R.sub.j]([[alpha].sub.j]/[p.sub.j]) - 2 [[[sum].sup.J].sub.i=1] [[omega].sub.[i]] [[[sum].sup.J].sub.j=i+1] [D.sub.[j]][p.sub.[j]]]}{2[[[[sum].sup.J].sub.j=1] [p.sub.j][D.sub.j]-1]}] (20)

For a given sequence, Lemma 1 shows that for reasonable values of problem parameters, a unique value of [lambda] solves the K-T necessary conditions. A sufficient condition for Lemma 1 to hold is for the [p.sub.j]'s to satisfy [[sum].sub.j[neq]h] [[D.sup.2].sub.j][R.sub.j][[alpha].sub.j]/[p.sub.j] [greater than](s/T - [p.sub.h][D.sub.h])[D.sub.h][R.sub.h][[alpha].sub.h]/[[p.sup.2].sub.h ], h = 1,2,...,J. This inequality is easily satisfied since the left-hand side involves the sum over J - 1 components of a term which includes [[D.sup.2].sub.j], while the right-hand side is for a single component and is multiplied by (s/T - [p.sub.h][D.sub.h]). The term s/T is the fraction of a year spent setting up while [p.sub.h][D.sub.h], is the time devoted to producing component h per year and, thus, (s/T - [p.sub.h][D.sub.h]) may be negative. The proof of Lemma 1 holds for a much larger solution space than that specified in the inequality above (see proof of Lemma 1). The condition of Lemma 1 is also sufficient for TC1 [T, T([[p.sup.*].sub.j])] to be convex.

Let V = J! be the number of possible sequences. Because a unique value of [lambda] solves the K-T necessary conditions for each sequence, a problem can have up to V unique values of optimal [lambda], each corresponding to a different sequence. A problem can have less than V unique values of [lambda] because two or more sequences can have an optimal [lambda] of zero. The proposed algorithm identifies the sequence with the smallest value of [lambda]. In other words, the algorithm identifies the sequence for which the value of an extra unit of time capacity is smallest.

A flow diagram of the algorithm is shown in Fig. 2. In both the figure and the algorithm, [v.sup.([cdotp])],[g.sup.([cdotp])], and [b.sup.([cdotp])] denote sequence. As the figure shows, for a given value of 2, after the repeated application of Hahm and Yano's algorithm converge to the same values of the [[p.sup.(h)].sub.j]'s, the resulting sequence is compared to the sequence for the previous value of [lambda]. If the sequence does not change, then Lemmas 2 and 3 provide the rules needed to tighten the interval on the optimal value of [lambda] for the sequence. If the sequence changes, then the lower bound on [lambda] is reassigned a value of zero (because we are searching for the smallest unique [lambda]). Let [[[lambda].sup.*].sub.v] be the optimal value of [lambda] for sequence v. If the smallest [[[lambda].sup.*].sub.v] v =1,..., V is greater than zero, the algorithm will converge to that smallest value and its corresponding sequence. If only one sequence has [[[lambda].sup.*].sub.v] = 0, the algorithm will converge to that sequence. If two or more sequences have [[[lambda].sup.*].sub.v] = 0, the algorithm will converge to one of these sequences. Results from testing the performance of the algorithm in the next section show that the algorithm performs better when capacity is tight.

This can be attributed to the fact that in this case the smallest [[[lambda].sup.*].sub.v] for all sequences satisfies [[[lambda].sup.*].sub.v] [greater than] 0 and the algorithm identified this unique [[[lambda].sup.*].sub.v] and the corresponding sequence. When capacity is not tight, many sequences have a [[[lambda].sup.*].sub.v] of zero and there is no corresponding unique sequence.

Lemma 1. If the ELDSPR for a fixed sequence is feasible, then there is a unique value of [lambda] that satisfies the Kuhn--Tucker necessary conditions.

Proof. See Appendix.

Lemma 2. For a given sequence

(i) If using [[lambda].sup.A] in (16) yields [[p.sup.A].sub.j], j=1,2,...,J, which gives T = [tau] in (19) and [lambda] [greater than] [[lambda].sup.A] in (20) then [[lambda].sup.A] [less than] [[lambda].sup.*] [less than] [lambda].

(ii) If using [[lambda].sup.A] in (16) yields [[p.sup.A].sub.j], J = 1,2,...,J, which gives T = [tau] in (19) and [lambda] [less than] [[lambda].sup.A] in (20) then [[lambda].sup.A] [greater than] [[lambda].sup.*] greater than] [lambda].

Proof. See Appendix.

Lemma 3. For a given sequence

(i) If using [[lambda].sup.A] in (16) yields [[p.sup.A].sub.j], j = 1,2,...,J, which gives T1 from (18) and [tau] from (8) satisfying T1 [greater than] [tau] [greater than ] 0 then [[lambda].sup.*] [less than] [[lambda].sup.A].

(ii) If using [[lambda].sup.A] in (16) yields [[p.sup.A].sub.j] j = 1,2,...,J, which gives T1 from (18) and [tau] from (8) satisfying T1 [greater than] 0 [greater than] [tau] then [[lambda].sup.*] [greater than] [[lambda].sup.A].

Proof. See Appendix.

Algorithm

Step 0. If [[[sum].sup.J].sub.j=1] [D.sub.j][[p.sup.L].sub.j=1] [geq] 1 then stop, problem is infeasible.

Set k=0, h=0, [[lambda].sup.(k)] = 0 and [[p.sup.(h)].sub.j] = max{[sqrt{[D.sub.j][R.sub.j][[alpha].sub.j]/([[omega].sub.j] + 2[[lambda].sup.(k)])}], [[p.sup.L].sub.j]}, j = 1,...,J.

Compute [[[sum].sup.J].sub.j=1] [D.sub.j][[p.sup.(h)].sub.j] and increase [[lambda].sup.(k)] until 0.98 [leq] [[[sum].sup.J].sub.j=1] [D.sub.j][[p.sup.(h)].sub.j] [less than] 1.

Set [[lambda].sup.MAX] = M, where M is a very large number.

Step 1. Set n = 0.

Sequence the components in non-increasing order of [[p.sup.(h)].sub.j]/[h.sub.j]. Let this sequence be [v.sup.(0)].

Step 2. Set n = n + 1. Compute [T.sup.(n)] using (19).

Step 3. Determine a new sequence by sorting all components in non-increasing order of (l/[[omega].sub.j]) ([T.sup.(n)][[p.sup.(h)].sub.j] [D.sub.j] + [s.sub.j]). Let this sequence be [v.sup.(n)]. If [v.sup.(n)] is not the same as [v.sup.(n-1)] and [T.sup.(n)] [neq] [tau] then go to Step 2.

Set h = h + 1, and [b.sup.(h)] = [v.sup.(n)].

Step 4. If k [leq] 1, compute [[p.sup.(h)].sub.j] = max{[[p.sup.L].sub.j],[p.sup.1].sub.j]}, and if [[p.sup.(h)].sub.j] [neq][[p.sup.(h-1)].sub.j] go to Step 1.

Set k = k + 1.

Set [g.sup.(k)] = [b.sup.(h)].

If [g.sup.(k)] [neq] [g.sup.(k-1)] then [[lambda].sup.MIN] = 0.

If [g.sup.(k)] = [g.sup.(k-1)] then set [[p.sup.(k)].sub.j] = [[p.sup.(h)].sub.j].

If [T.sup.(n)] = [tau] then compute [lambda] using (20) and if [lambda] [greater than] [[lambda].sup.(k-1)] then [[lambda].sup.MIN] = [[lambda].sup.(k=1)] otherwise [[lambda].sup.MAX] = [[lambda].sup.(k=1)].

If [T.sup.(n)] = [tau] than if [tau] [greater than] 0 then [[lambda].sup.MAX] = [[lambda].sup.(k=1)] otherwise [[lambda].sup.MIN] = [[lambda].sup.(k=1)]

[[lambda].sup.(k)] = ([[lambda].sup.MIN] + [[lambda].sup.MAX])/2

Set h = 0.

Step 5. Compute [[p.sup.(k)].sub.j] using (17).

If [[p.sup.(k)].sub.j] [approx] [[p.sup.(k-1)].sub.j] and [[lambda].sup.(k)] [approx] [[lambda].sup.(k-1)] then stop, solution is optimal. Otherwise set [[p.sup.(h)].sub.j] = [[p.sup.(k)].sub.j] and go to Step 1.

To ensure convergence of the algorithm, the termination of the loops in Steps 2 and 3, 1-4, and 1-5 in a finite number of iterations must be demonstrated. Steps 2 and 3 solve the subproblem of finding the optimal value of T and [v.sup.([cdotp])] for fixed values of the [p.sub.j]'s, which is the problem Hahm and Yano [1] developed an algorithm for and provided a proof of convergence. Steps 1-4 solve the subproblem of finding the optimal [p.sub.j]'s for a fixed value of [lambda]. If Step 3 gives a new sequence, then for that sequence, Step 4 gives new values of the [[p.sup.(h)].sub.j]'s with lower total cost (because these are the unique values that satisfy the K-T conditions). These new values of the [[p.sup.(h)].sub.j]'s are now used in Hahm and Yano's algorithm (Steps 1-3) and either the sequence will remain the same resulting in convergence in Steps 1-4, or, by the properties of Hahm and Yano's algorithm, a new sequence with lower total cost will be identified. Since the number of sequences is finite and every it eration gives a sequence with lower total cost, convergence of Steps 1-4 in a finite number of iterations is guaranteed. Steps 1-5 solve the subproblem of finding the optimal value of [lambda] for a fixed sequence. If two iterations of Step 5 have the same sequence, then the search interval of [lambda] is reduced by 50% and a new value of [lambda], [[lambda].sup.(k)], is computed. If [[lambda].sup.(k)] [approx] [[lambda].sup.(k-1)]then the algorithm converges to the optimal solution for the sequence and it terminates. Otherwise, more iterations of the algorithm are performed until convergence to the optimal value of [lambda] of a sequence, or until the sequence changes to a new one with smaller optimal value of [lambda]. Since the number of sequences is finite and the interval of the optimal value of [lambda] for a given sequence is tightened or a new sequence with lower optimal value of [lambda] is identified at each iteration, convergence of Steps 1-5 in a finite number of iterations is guaranteed. In testi ng the algorithm, it solved 18 problems, each with nine components, in less than 30 seconds on a Pentium II 330 MHz Personal Computer.

Another possibility for treating controllable unit production times is one in which average unit costs are functions of unit production times. Stability of production costs over varying production volumes has been suggested as a measure of volume flexibility by Falkner [21]. Ramasesh and Jayakumar [22] have used the shape of the average unit cost curve to measure volume flexibility. The more volume flexible is the system, the flatter is its average unit cost curve. Average unit cost initially decreases because fixed costs are spread over more units. At higher volumes, increases in tool wearout cause average unit cost to increase [23,24]. For this case, unit production times should be set to values greater than unit production times that minimize average unit costs [25].

3. Numerical examples and experimental results

3.1. Example 1: fixed unit production times

Consider the five-component problem in Table 1 with 3000 hours of operating time per year. Demand and unit production times result in a utilization of Y = [[[sum].sup.5].sub.i=1] [D.sub.i][p.sub.i] = 0.95 (i.e., 95%). Ignoring quality cost and using Hahm and Yano's algorithm [1], the optimal cycle time is [T.sup.*] = 217.4 hours (18.12 days, based on 12 hour days) and [TC.sup.*] = $57 272 of which $45 908 is due to rework. The optimal sequence is shown in Table 1. When quality cost is taken into account, the optimal T is [T.sup.*] = 71.67 hours (5.97 days) and [TC.sup.*] = $34 209 of which $15 133 is due to rework. The reduction in the optimal cycle time when quality cost is taken into account is 67% and the saving in total annual expected cost is 40%.

3.2. Example 2: output quality depends on unit production times

Reconsider the five-component problem in Table 1 with the exception that unit production times are decision variables and [q.sub.j] = [[alpha].sub.j]/[p.sub.j] with [[alpha].sub.j] as shown in Table 2. The [[alpha].sub.j] in Table 2 will result in the same [q.sub.j]'s of Table 1 when the [p.sub.j]'s of Table 1 are used. The optimal sequence and unit production times resulting from the algorithm are shown in Table 2. Volume flexibility has resulted in a new production sequence. The new cycle time is [T.sup.*] = 77.52 hours (6.46 days) and [TC.sup.*] =$32 105 of which $13 874 is due to rework. The saving due to volume flexibility is 6.2%.

Several insights about the effects of controllable production rates on the sequence and, in turn, the effects of the sequence on the production rates can be discerned from Equation (16) and the sequencing rules of the algorithm. The unconstrained optimal production rate of component j is given by 1/[[p.sup.1].sub.j] where [[p.sup.1].sub.j] is given by (16). Equation (16) shows that components produced late in the sequence will have high pressure to have their production rates speeded up. This pressure is brought about by the term 2 [[sum].sup.i-1].sub.k=1] [[omega].sub.[k]], which is the sum of [D.sub.i][H.sub.i], for all the components produced prior to the component at hand in the denominator. Intuitively, increasing the production rates for components late in the sequence is worthwhile because the savings from holding all the components produced before them for a shorter duration can be significant. Also, from (16), the increase in the production rate of a component as it is moved later in the sequence occurs at a decreasing rate. This occurs because the transition probabilities increase at an increasing rate with production rates.

Equation (16) also implies that, all else being equal, components with high rework cost and large [[alpha].sub.j] will have lower production rates (or longer unit production times) to avoid excessive rework cost. This in turn will cause these components to be pushed to earlier slots in the production sequence as indicated by Step 3 of the algorithm. The position of a component in the sequence is further determined by its holding cost. The smaller the holding cost, the earlier the component is produced because it is inexpensive to hold for a long duration.

3.3. Experimental results

As discussed earlier, the performance of Hahm and Yano's algorithm (for perfect quality) yielded optimal solutions for a broad range of problems [1]. To verify the performance of the algorithm with the modification to account for imperfect quality under the assumption [q.sub.j] = [[alpha].sub.j]/[p.sub.j] with the [p.sub.j]'s fixed, its solutions were compared to the global optimal solutions for a number of randomly generated problems. For each problem, the global optimal solution was found by enumerating all sequences and then finding the optimal cycle time and the minimum total cost for each sequence. In generating the problems, we consider the three factors used by Hahm and Yano [1]: (i) the spread of the unconstrained natural frequencies; (ii) the tightness of the capacity constraint; and (iii) the size of problems. For each component, the unconstrained optimal delivery cycle time is:

[[T.sup.U].sub.j] = [sqrt{[frac{2[p.sub.j]([S.sub.j] + A)}{[D.sub.j]([H.sub.j][p.sub.j](1 + [D.sub.j][p.sub.j]) + [D.sub.j][R.sub.j][[alpha].sub.j])}] j = 1,2,...,J. (21)

Since we are dealing with the fixed production rate case, the [p.sub.j]'s in (21) are fixed and given. We use the ratio of the maximum [[T.sup.U].sub.j] to the minimum [[T.sup.U].sub.j], j = 1,2,...,J as a measure of the spread of the unconstrained natural frequencies. Problem parameters (i.e., [R.sub.j], [q.sub.j], [H.sub.j], [S.sub.j], [D.sub.j], and A) were generated using the uniform distribution and half of the problems were selected on the ratio interval of [1.0,2.5] and the other half on [4.5, 6.0].

The tightness of the capacity constraint is measured by how close Y = [[[sum].sup.J].sub.j=1] [D.sub.j][p.sub.j] is to one. A value of one implies that the problem is infeasible when production rates are fixed because there is no time left for setup. One-third of the problems were selected from the Y interval of [0.2,0.4] (not tight), one-third from the interval [0.5,0.7] (moderately tight), and one-third from the interval [0.8,0.97] (tight). An equal number of problems with five and seven components were generated. The three factors result in (2 x 3 x 2) different combinations. For each combination, three problems were generated, resulting in 36 problems. For each problem, the solution obtained using a modification of Hahm and Yano's algorithm was compared to the global optimal solution obtained by enumerating all sequences. The algorithms found the optimal solution for 35 problems. For the remaining seven-component problem, the algorithm identified a solution that switched the order of the fifth and sixt h components. However, the expected total annual cost was identical to the expected total annual cost of the global optimal solution (the difference was less than 0.000 0003%) which implies that the problem may have an alternate optimal solution.

For the case of flexible production rates, the algorithm was tested on a set of 72 problems. For these problems the transition probabilities are given by [q.sub.j] = [[alpha].sub.j]/[p.sub.j] and unit production times are unrestricted. In generating the test problems, the same three factors used for the case of fixed production rates were considered. Because production rates are now controllable, we substitute the unconstrained optimal unit production times for the single component problems given by:

[[p.sup.U].sub.j] = [sqrt{[frac{[R.sub.j][[alpha].sub.j]}{[H.sub.j]}] j = 1,2,...,J, (22)

in (21) to obtain the unconstrained optimal delivery cycle times. Half of the problems were selected on the ratio interval of [1.0,2.5] and the rest on [4.5,6.0].

Similarly, we use the unconstrained optimal unit production times to obtain tightness of the capacity constrained [Y.sup.U] = [[[sum].sup.J].sub.j=1] [D.sub.j][[p.sup.U].sub.j]. Because unit production time for a component can be reduced below [[p.sup.U].sub.j], [Y.sup.U] can be greater than one. One-third of the problems were selected from the [Y.sup.U] interval of [0.4,0.7] (not tight), one-third from the interval [1.0,1.4] (moderately tight), and one-third from the interval [2.0,2.3] (tight). The reason for choosing such a tight capacity is that the [[p.sup.U].sub.j]'s are the single component optimal unit production times. In computing the [[p.sup.U].sub.j] for a component, the holding cost of components produced prior to it, which will cause its production rate to be speeded up in the multi-component solution, are not taken into account. For problem size, equal number of problems with three, five, seven, and nine components were generated. The three factors resulted in (2 x 3 x 4) different combinatio ns. For each combination, three problems were generated. All possible sequences were enumerated for each problem size and the optimal cycle time and unit production times were computed for each sequence. The global optimal solution to each problem was then identified. The solutions from the algorithm were then compared to the global optimal solutions for these 72 problems.

The results of the experiment are shown in Table 3. For problems in which the algorithm gave suboptimal solutions, we report both the worst and the average performance of the algorithm. Therefore, if there is more than one problem in a cell of column 7, then the problem in which the algorithm performed worst in terms of deviation from the minimum total cost is chosen for reporting in columns 8 and 9. The average performance for each group of problems for which the algorithm did not find the optimal solution is reported in columns 10 and 11. Solution rank in Table 3 refers to the rank of the solution of the algorithm when all sequences are ranked in descending order of their total expected cost.

Overall, the algorithm performed very well. For the 72 problems, the algorithm identified the global optimal solution for 49 (68%) problems. Even when the algorithm did not identify the global optimal solution, the algorithm identified a solution having total annual expected cost very close to it. When the algorithm identified a suboptimal solution, these solutions had a TC above the global minimum by an average of 0.21% for the worst cases and 0.15% on average. For the seven- and nine-component problems, when the algorithm identified suboptimal solutions, these solutions still ranked among the 0.08% lowest cost solutions.

Table 4 shows the number and percentage of problems for which the algorithm identified the optimal solution in each problem category. As can be seen, the algorithm performs better for problems in which capacity is tight. These problems are more likely to have [[[lambda].sup.*].sub.v] [greater than] 0 for all V sequences and the algorithm identified the sequence with the minimum [[[lambda].sup.*].sub.v]. When capacity is not as tight, two or more sequences can have [[[lambda].sup.*].sub.v] = 0 and the algorithm may identify one of these sequences which is suboptimal. For problems with tight capacity, production rates and sequence have a significant effect on total expected costs. The ability of the algorithm to identify the global optimal solutions for these problems can lead to substantial cost savings.

4. Conclusion and suggestions for future research

This paper extends the economic lot scheduling and delivery problem to the case of imperfect quality. Two cases of output quality are considered. In the first case, output quality deteriorates with larger lot sizes but is independent of unit production times which are fixed. In the second case, output quality deteriorates with larger lot sizes and decreased unit production times. For the first case, the explicit consideration of quality using rework cost results in smaller cycle time and lot sizes which support JIT inventory management. For the second case, an algorithm that was found to perform well for a broad range of problems was developed. Linking quality to unit production times resulted in changing the unit production times and sequence of production. Components with large rework cost will be produced at slower rates than others and, other things being equal, will be produced earlier in the sequence. The proposed model dealt with a transition probability given by [q.sub.j] = [[alpha].sub.j]/[p.sub.j]. Other models for transition probability, in spite of being convex such as [q.sub.j] = [[alpha].sub.j]/[[p.sup.2].sub.j], are considerably more difficult because closed-form expressions for [[p.sup.1].sub.j]'s similar to Equation (16) cannot be obtained. For concave transition probabilities, such as [q.sub.j] = [[eta].sub.j] - [[gamma].sub.j][[p.sup.2].sub.j], where [[eta].sub.j] and [[gamma].sub.j] are constants, the uniqueness of a solution satisfying the K-T conditions can no longer be proved and the problem becomes much harder.

Future research can investigate the case in which volume flexibility is exercised at a cost. In such a case, changes in unit production times from set values which minimize average unit costs of components result in an increase in average unit costs. Further extensions that may merit research efforts include cases of stepwise or exponential deterioration of output quality with decreased unit production times.

Acknowledgements

The author would like to thank the Department Editor and the referees for their helpful suggestions. This work was supported, in part, by funds provided by the University of North Carolina at Charlotte.

Moutaz Khouja is an Associate Professor of Operations Management at the University of North Carolina at Charlotte. He holds a Ph.D. in Operations Management from Kent State University. His areas of interest include technology selection and inventory management. His publications have appeared in Decision Sciences, IIE Transactions, European Journal of Operational Research, Journal of the Operational Research Society, International Journal of Operations and Production Management, Interfaces, Computers and Operations Research, and other journals. He is a member of the American Production and Inventory Control Society (APICS) and the Decision Sciences Institute (DSI).

References

(1.) Hahm, J. and Yano, C.A. (1995) The economic lot delivery scheduling problem: the common cycle case. IIE Transactions, 27, 113-125.

(2.) Hahm, J. and Yano, C.A. (1995) The economic lot delivery scheduling problem: models for nested schedules. IIE Transactions, 27, 126--139.

(3.) Hahm, J. and Yano, CA. (1995) The economic lot delivery scheduling problem: powers of two policies. Transportation Science, 29(3), 222--241.

(4.) Slack, N. (1987) The flexibility of manufacturing systems. International Journal of Operations and Production Management, 7(4), 35--45.

(5.) Sethi, A.K. and Sethi, P.S. (1990) Flexibility in manufacturing: a survey. The International Journal of Flexible Manufacturing Systems, 2, 289--328.

(6.) Silver, E.A. (1990) Deliberately slowing down output in a family production context. International Journal of Production Research, 28(1), 17--27.

(7.) Moon, I., Gallego, G. and Simchi-Levi, D. (1991) Controllable production rates in a family production context. International Journal of Production Research, 29, 2459--2470.

(8.) Gallego, G. (1993) Reduced production rates in the economic lot scheduling problem. International Journal of Production Research, 31(5), 1035--1046.

(9.) Khouja, M. (1997) The scheduling of economic lot sizes on volume flexible production systems. The International Journal of Production Economics, 48, 73--86.

(10.) Khouja, M. (1999) A note on "deliberately slowing down output in a family production context." International Journal of Production Research, 37, 4067--4077.

(11.) Khouja, M. (1996) A supply chain inventory model with rework cost and variable unit production times. Management Science and Regional Development, 1(2) 3--21.

(12.) Hahm, J. and Yano, C.A. (1992) The economic lot delivery scheduling problem: the single item case. International Journal of Production Economics, 28, 235--252.

(13.) Porteus, E.L. (1986) Optimal lot sizing, process quality improvement, and setup cost reduction. Operations Research, 34, 137--144.

(14.) Rosenblatt, M.J. and Lee, H.L. (1986) Economic production cycles with imperfect production processes. IIE Transactions, 17, 48-54.

(15.) Cheng, T.C.E. (1991) An economic order quantity model with demand-dependent unit production cost and imperfect production processes. IIE Transactions, 23(1), 23--28.

(16.) Khouja, M. and Mehrez, A. (1994) An economic production lot size model with imperfect quality and variable production rate. Journal of the Operational Research Society, 45(12), 1405--1417.

(17.) Khouja, M., Rabinowitz, G. and Mehrez, A. (1995) Optimal robot operation and selection using quality and output trade-off. The International Journal of Advanced Manufacturing Technology, 10, 342--355.

(18.) Mehrez, A., Offodile, O.F. and Ahn, B. (1995) A decision analysis view of the effect of robot repeatability on profit. IIE Transactions, 27, 60--71.

(19.) Mehrez, A. and Offodile, O.F. (1994) A statistical-economic framework for evaluating the effect of robot repeatability on profit. IIE Transaction, 26(3), 101--110.

(20.) Baker, K.R. (1974) Introduction to Sequencing and Scheduling, John Wiley, New York, NY.

(21.) Falkner, C.H. (1986) Flexibility in manufacturing plants, in Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems, Elsevier, New York, NY. pp. 95--106.

(22.) Ramasesh, R.V. and Jayakumar, M.D. (1991) Measurement of manufacturing flexibility. Journal of Operations Management, 10(4), 446--467.

(23.) Schweitzer, P.J. and Seidmann, A. (1991) Optimizing processing rates for flexible manufacturing systems. Management Science, 37, 454--466.

(24.) Drozda, T.J. and Wick, C. (eds) (1983) Tool and Manufacturing Engineers Handbook, Vol. 1, Society of Mechanical Engineers, Dearborn, MI

(25.) Khouja, M. (1999) Speeding up production to reduce cost in the economic lot and delivery scheduling problem. Technical Report, University of North Carolina at Charlotte, Charlotte, NC 28223.

Appendix

Proof of Lemma 1. Suppose [[lambda].sup.A] [greater than] [[lambda].sup.B] are two values of [lambda] that satisfy the Kuhn-Tucker conditions. From (16) [[p.sup.A].sub.j] [less than] [[p.sup.B].sub.j] j = l,2,...,J. Let [k] = h. Since constraint (2) is binding, [lambda] is given by (20). Taking the partial derivative of [lambda] in (20) with respect to [p.sub.h] gives:

[frac{[partial][lambda]}{[partial][p.sub.h]}] = [D.sub.h][(1 - [[[sum].sup.J].sub.j=1] [p.sub.j][D.sub.j])([[omega].sub.h] - [D.sub.h][R.sub.h] [frac{[[alpha].sub.h]}{[[p.sup.2].sub.h]}] + 2 [[[sum].sup.k-1].sub.i=1] [[omega].sub.[i]])

+ [omega] + [[[sum].sup.J].sub.j=1] [[omega].sub.j][D.sub.j][p.sub.j] + [[[sum].sup.J].sub.j=1][[D.sup.2].sub.j][R.sub.j] [frac{[[alpha].sub.j]}{[p.sub.j]}] + 2 [[[sum].sup.J].sub.i=1] [[omega].sub.[i]]

x [[sum].sup.J].sub.j=i+1] [D.sub.[j]][p.sub.[j]]]/([2[(1 - [[[sum].sup.J].sub.j=1] [p.sub.j][D.sub.j]).sup.2]] + (S + A)[p.sub.h]/[s.sup.2]). (A1)

which is positive if:

([[omega].sub.h] + 2 [[[sum].sup.k-1].sub.i=1] [[omega].sub.[i]]) + [[omega] + [[[sum].sup.J].sub.j=1] [[omega].sub.j][D.sub.j][p.sub.j] + [[[sum].sup.J].sub.j=1] [[D.sup.2].sub.j][R.sub.j][frac{[[alpha].sub.j]}{[p.sub.j]}]

+ 2 [[[sum].sup.J].sub.i=1] [[omega].sub.[i]] [[[sum].sup.J].sub.j=i+1] [D.sub.[j]] [p.sub.[j]]]/(1 - [[[sum].sup.J].sub.j=1] [p.sub.j][D.sub.j])

+ 2 (1 - [[[sum].sup.J].sub.j=1] [p.sub.j][D.sub.j]) (S + A) [p.sub.h]/([D.sub.h][s.sup.2]) [greater than] [D.sub.h][R.sub.h] [frac{[[alpha].sub.h]}{[[p.sup.2].sub.h]}] (A2)

Inequality (A2) is satisfied if:

[[[sum].sup.J].sub.j=1] [[D.sup.2].sub.j][R.sub.j] [frac{[[alpha].sub.j]}{[p.sub.j]}] / (1 - [[[sum].sup.J].sub.j=1] [p.sub.j] [D.sub.j]) [greater than] [D.sub.h][R.sub.h] [frac{[[alpha].sub.h]}{[[p.sup.2].sub.h]}], (A3)

which simplifies to:

[[[sum].sup.J].sub.j[neq]h] [[D.sup.2].sub.j] [R.sub.j] [frac{[[alpha].sub.j]}{[p.sub.j]}] [greater than] [D.sub.h][R.sub.h] [frac{[[alpha].sub.h]}{[[p.sup.2].sub.h]}] (1 - [[[sum].sup.J].sub.j=1] [p.sub.j][D.sub.j] - [D.sub.h][p.sub.h]) (A4)

For any [lambda] [greater than] 0, (12) gives

[p.sub.h][D.sub.h] = 1 - s/T - [[sum].sub.j[neq]h] [D.sub.j][p.sub.j] (A5)

Using (A5) in (A4) gives the following sufficient condition for [partial][lambda]/[partial][p.sub.j] [greater than] 0,

[[sum].sub.j[neq]h] [[D.sup.2].sub.j][R.sub.j] [frac{[[alpha].sub.j]}{[p.sub.j]}] [greater than] [D.sub.h][R.sub.h] [frac{[[alpha].sub.h]}{[[p.sup.2].sub.h]}](s/T - [p.sub.h][D.sub.h]). (A6)

Since [[p.sup.A].sub.j] [less than] [[p.sup.B].sub.j] and [partial][lambda]/[partial][p.sub.j] [greater than] 0, j = 1,...,J, (20) gives [[lambda].sup.A] [less than] [[lambda].sup.B] which is a contradiction.

Proof of Lemma 2. The proof of part 1 of the lemma is provided in two parts:

1a. Suppose [[lambda].sup.*] [less than] [[lambda].sup.A] is used in (16). From (l6) [[p.sup.*].sub.j] [greater than] [[p.sup.A].sub.j], j = 1,2,...,J. From the proof of Lemma 1, [lambda] is increasing in [p.sub.j] and thus using [[p.sup.*].sub.j], j = 1,2, ...,J in (20) gives [[lambda].sup.B1] [greater than] [[lambda].sup.B] and there is no value of [lambda] in the interval [0, [[lambda].sup.A]] that satisfies the Kuhn-Tucker conditions.

1b. Suppose [[lambda].sup.*] [greater than] [[lambda].sup.B] is used in (16). From (16) [[p.sup.*].sub.j] [less than] [[p.sup.A].sub.j], j = 1,2,...,J. From the proof of Lemma 1, [lambda] is increasing in [p.sub.j] and thus using [[p.sup.*].sub.j] j = 1,2,...,J in (20) gives [[lambda].sup.B1] [less than] [[lambda].sup.B] and there is no value of [lambda] in the interval [[[lambda].sup.B], [infty]] that satisfies the Kuhn-Tucker conditions.

From (1a) and (1b), the optimal value of [lambda] can only be in the interval [[[lambda].sup.A], [[lambda].sup.B]].

Similarly, the proof of part 2 of the lemma is provided in two parts

2a. Suppose [[lambda].sup.*] [greater than] [[lambda].sup.A] is used in (16). From (16) [[p.sup.*].sub.j] [less than] [[p.sup.A].sub.j], j = 1,2,...,J. From the proof of Lemma 1, [lambda] is increasing in [p.sub.j] and thus using [[p.sup.*].sub.j], j = 1,2,...,J in (20) gives [[lambda].sup.B1] [less than] [[lambda].sup.B] and there is no value of [lambda] in the interval [[[lambda].sup.A], [infty]] that satisfies the Kuhn-Tucker conditions.

2b. Suppose [[lambda].sup.*] [less than] [[lambda].sup.B] is used in (16). From (16) [[p.sup.*].sub.j] [greater than] [[p.sup.A].sub.j], j = 1,2,...,J. From the proof of Lemma 1, [lambda] is increasing in [p.sub.j] and thus using [[p.sup.*].sub.j] j = 1,2,...,J in (20) gives [[lambda].sup.B1] [greater than] [[lambda].sup.B] and there is no value of [lambda] in the interval [0, [[lambda].sup.B]] that satisfies the Kuhn-Tucker conditions.

From (2a) and (2b), the optimal value of [lambda] can only be in the interval [[[lambda].sup.B], [[lambda].sup.A]].

Proof of Lemma 3.

1. Suppose that using [[lambda].sup.A] in (16) yields [[p.sup.A].sub.j], j = 1,2,...J, which give T1 and [tau] in (18) and (8) satisfying T1 [greater than] [tau] [greater than] 0, then using [lambda] = 0 in (16) will result in values of [p.sub.j], j = 1,2,...J, that when used in (8) and (18) will lead to one of the following:

1a. T1 [greater than] [tau] [greater than] 0. Thus, the constraint is not binding and [[lambda].sup.*] = 0.

1b. [tau] [greater than] T1 [greater than] 0. Thus, there is an interval of values of [lambda] on the interval [0, [[lambda].sup.A]] for which T = [tau] = max{T1, [tau]}. By Lemma 1, a single value of [lambda] in that interval is optimal.

1c. T1 [greater than] 0 [greater than] [tau]. Thus, from (8) there is a value of [lambda] (say [[lambda].sup.F]) on the interval [0, [[lambda].sup.A]] for which [[[sum].sup.J].sub.j=1] [p.sub.j][D.sub.j] = 1. From (8), for some interval of values of [lambda] just above [[lambda].sup.F] but below [[lambda].sup.A], T [tau] = max{T1, [tau]}. By Lemma 1, a unique value of [lambda] in that interval is optimal.

In all three cases, 1a, 1b, and 1c, [[lambda].sup.*] [less than] [[lambda].sup.A].

2. Suppose using [[lambda].sup.A] in (16) yields [[p.sup.A].sub.j], j = 1,2, .. .J, which give T1 and [tau] in (18) and (8) satisfying T1 [greater than] 0 [greater than] [tau] then [[[sum].sup.J].sub.j=1] [p.sub.j][D.sub.j] [greater than] 1. Thus, the values [p.sub.j], j = 1,2,...J, must be reduced. From (16), to reduce [p.sub.j], j = 1,2,...J, the value of [lambda] must be increased and thus [[lambda].sup.*] [greater than] [[lambda].sup.A].