An Optimal Ordering Rule for A Stochastic Sequencing Model by S.O. Duffuaa Department of Industrial and Operations Engineering University of Michigan Ann Arbor MI 48109 Technical Report Number 94-20 July 1994

An Optimal Ordering Rule for a Stochastic Sequencing Model by S.O. Duffuaa* Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 E-mail: SALIH.ENGIN.UMICH.EDU In this report an optimal sequencial rule is developed for a class of stochastic sequencial models. Based on pairwise interchange necessary and sufficient conditions for the optimality of the rule is given. The rule is applicable to many situations such as multicharacteristic sequencial testing and job processing on a single machine. The optimal sequencial rule generalizes the deterministic results given in [3,4], for situations when the parameter of the problem are random variables. Several examples are given to demonstrate the utility of the result in the paper. Keywords: Optimal Sequencial Rule, Random Parameters On Sabbatical leave from King Fahd University of Petroleum and Minerals, Dhahran, 31261, Saudi Arabia 1

1.0 Introduction In this report the problem of finding an optimal sequence for a class of problems with random parameters has been studied. An important example from this class is the stochastic multicharacteristic inspection problem, when characteristics need to be ordered for inspection in order to minimize the expected cost of inspection. In such a problem, components with several characteristics are supplied by vendors that have to be inspected. The characteristics have different defective rates and cost of inspection. The cost depends on the type of test and equipment needs in carrying out the quality assurance. The probability of characteristic i is defective is Pi > 0, and its cost of inspection is Ci > 0. Both Pi and Ci are not known precisely and are assumed to be independent random variables. Inspectors commit two types of errors. Type I error qi and type II bi. The inspection of characteristics are independent, and inspection will be carried out until one characteristic is rejected or all characteristics pass the inspection. The component is rejected if one characteristic is defective. The deterministic multicharacteristic inspection problem (where all parameters are assumed to be known constants) is first addressed in [1,2,3] and a rule is given for finding the optimal sequence, however the proofs given in [2,3], only give a sufficient condition for the optimality of the rule. Later the deterministic sequencing problem has been stated in general terms in [4], and necessary and sufficient conditions are given for the optimality of the sequencing rule. Moreover, many other examples from the literature are cited as special cases of the general sequencing model. The model considered in this paper generalizes the sequencial model given in [4] by allowing some of the input variables to be random. For example, for the multicharacteristic inspection problem usually characteristic's defective rates are not known precisely and the cost of inspection is not exactly a fixed value, the cost varies from component to component. Therefore, the sequencing model with random input 2

represents real life more appropriately and is worthy of study. The objective of the paper is to develop rules for finding optimal sequences that minimizes expected cost of inspection. The rest of the report is organized as follows: Section 2 provides a brief review of the deterministic sequencial model and the result to be used in the proof of the optimal sequence of the Stochastic Model. Section 3 formulates the Stochastic Sequencial Model and provides the main result of the paper. Section 4 presents examples pertinent to the stochastic case, and Section 5 concludes the report. 2.0 Deterministic Sequencial Model The general sequencing problem in [4] is defined as follows. Given n objects with no precedence relation among the objects, for each object i there are a positive weight wi, and a nonzero number Pi and a cost function f: RN zE R+, where RN is all ordered subsets of the set of objects (for example, (1,2,3,4) is different from (1,2,4,3)). The objective is to find the optimal ordering p: (/', j2...., n) that minimizes the total cost function. iTC(r) = Y.fji ul ) 2 i i) (1) It is assumedfe for each object i is independent of specific ordering of objects (j, j1s. ji-I). Consider a partial sequence B = (ji, 12'...' jir,) of the objects and an object 1 such that 1 ce B, the following relation is assumed for eachfi, i = 1,2,...,n fi j,(jJ2 j.....jalj+'j....i)- fj sJJ29.jaJaJ+...ji)=PlwjH(jl2,J...ji-) (2) where H is a positive set function on all subsets of the n objects and H(f) = 1. Note that the set function H does not depend on any specific index ordering. The main theorem given in [4] states: 3

Theorem 1: For any sequencing problem defined above, a sequence n minimizes the total cost given in (1) if and only if we have h(jl) < h( j2) <... _< h(j,) (3) where h(ji) = Pji I wji. The proof is based on pairwise comparisons and is given in [4]. 3.0 The Stochastic Sequencing Model The stochastic sequencing problem can be stated as follows: There are n objects with no precedence relation associated with the objects. Each object i is associated with a positive random weight wi and a nonzero random variable Pi, both with finite expectations and independent. Also a random cost functionfi: RN -* R+, where RN is all ordered subsets of the n objects (for example, (1,2,3,4) is different from (1,2,4,3)). All random variables are assumed to be independent. The objective is to find an ordering n = (j', j2,..., jjn) of the n objects to minimize the expected total cost. E[TC(T)] = E[fj, (jl, J 2...i)] (4) i=1 It is assumed thatfi for each object i is independent of specific ordering of the objects (I. i2,..., i- l). Consider a partial sequence B of the objects and an object 1, such that lIB, the following relation is assumed for each functionfi, i = 1,2,...,n. fi (J li2,...2iaLia+,.ii) - f~ J,,"l',2*ja *aa+1..j) = PwiiH(jJ2,...,J, ia+, 9... Ji-) (5) where H is a random set function defined on all subsets of the n objects with a positive expectation and H(O) = 1. Note that the set function H does not depend on any specific job ordering and has finite expectation. Taking the expected value operator of equation (5) we get E[f j, (.i', I2,'. IalIa+,-"'.) f fj,(J, Ji"2' **.Ia, a+'." *,ji)] = E[Pt]E[wji]E[H(Ij,j2,...,jaja+i,...,I,_i)] (6) 4

Theorem 2: For any stochastic sequencing problem defined above, a sequence n will minimize expected total cost if and only if h(jl) < h(j2)h <... ) h(j) (7) where h(j1)= E[P,]/ E[wj,] fori = 1,2,...,n. Proof: Let x be a sequence of n objects and let E1 be a sequence obtained from K by changing the position of ith and (i + 1)th objects, then we have E[TC(r)] - E[TC(7' )] = E[f, (B, j,, ji ) - fj+, (B, j+ )] = E[f, (B, j,1,ji) - fj, (B, j)] = E[H(B)]E[PI ]E[w,.[ ] - E[H(B)]E[Pi,. ]E[wj, ] = E[H(B)][E[Pj ]E[wj,. ] - E[Pji+, ]E[wj ]] Since E[H(B)] and E[wi] are positive then E[TC(Il)] E[TC(nl)] if and only if h(ji ) < h(jil ) and this is independent of H(B). Since the value of h for each specific object i is equal to h(i) = E[Pi] / E[w,] and positive, then it satisfies the transitivity relation i.e for three objects ij and k, if h(i) < h(j) and h(j) < h(k), then h(i) < h(k). It follows from transitivity of h that 7t is an optimal sequence if and only if h(j) < h(j2) <...- < h(jn). In the following section, generalizations of the deterministic examples in [2,4] are given to demonstrate the utility of theorem 2 in the paper. 4.0 Examples of the Stochastic Model 4.1 The Stochastic Multicharacteristic Inspection Problem Consider a component with n characteristics such that each characteristic has to be inspected separately. It is assumed that the inspection of characteristics are independent from each other. Each characteristic i has a cost of inspection Ci > 0, Ci is 5

not known exactly it is a random variable with finite expectation. Also it has a probability of rejection Ri, Ri is a random variable between zero and one, and is a function of the defective rate Pi and inspectors errors Oi and Pi. All Ri's and Ci's are independent random variables. The objective is to find the optimal sequence (order the characteristics for inspections) to minimize the expected total cost. n r-1 TC(r) = Cj, + Cj n (1-R, ) (8) r=2 t=1 Since all random variables are independent, the expected total cost is given by: E[TC()] = E[Cj, ] + E[Cj, ] n (1- E[Rj,]) (9) r=2 t=1 where n = (i, j2,....Jn) is an ordering policy (a sequence) andjr is the rth characteristic to be inspected. The multicharacteristic inspection problem with random inspection cost and rejection rate is a special case of theorem 2. It can be easily shown if we define: wj = Cj, and P, = -Rj, E[w, ] = E[C, ] and E[P, ] = -E[R, ] fjl = Cjl for all objects, and E(f, ) = E(C,) i-1 fi (l J2,, Ji) C, =C (1 - Rj, )) fori = 2,...,n i-i and E[fj (j,,j2,..., )]= E[Ci ](n (1 - E[Ri ])) and H()) = 1. All the conditions of theorem 2 are satisfied and X is the optimal sequence if and only if E[Cj, ] / ] < E [C[R ] < E[[Cj ] E[Rj ] (10) The above result in (10) can be obtained from the approach given in [3] for the deterministic case. 6

4.2 The Stochastic Candidate Selection Problem This is a generalization of the sequencing selection problem given in [4,5] by making some of its variables random. Assume there are n acceptable candidates to fill a position. Suppose the benefits from candidate i, (i = 1,..., n) for the next M years is a random variable bj, and the probability of acceptance of the job by candidate i is a random variable O<Ri < 1 (the probability of rejecting the offer is (1-Ri)). When a candidate receives an offer, there is a fixed period of time, he/she can accept or reject the offers and during this period no offer is made to other candidates. As soon as a candidate accepts the offer the search is terminated. The cost of an offering a job is random variable C. All random variables are assumed to be independent of each other. The objective is to find an optimal selection ordering (i, j2,..., in) among n! permutations to maximize the expected benefit. The total benefit, TB is given as: TB(n) = (R, bj - C) + n(l - R )(Rj bj -C) (11) r=2 i=1 The expected total benefit is given by E[TB] = (E[R1 ]E[b, ] - E[C])+ hI n(l - )E[R ])(E[]E[b ] - E[C]) (12) r=2 i=1 The candidate selection problem with random parameters can easily be shown to be a special case of theorem 2. Let the random variables wi, Pi and functions H andfi for all objects i be defined as follows: wi = (RJ, bj, - C) and Pj, = -Rj, f, (j) = (Rj, bj - C) for all objects i-1 fj, (Jl i2...ji)= (Rjbj, -C)( (1- Rij)) for i = 2,3,..., n. * *^)=t j i (n(l- R)) and h() = 1 H(j, i2 j2,j) = (Hl- Rt)) and H(O) 1 The candidate selection problem satisfies the condition of the theorem 2 and hence the Sequence i7 is optimal (maximizes expected total benefit) if and only if h(j,)<h(j2)<...<h(j,), where E[Rj ]/(E[Rj,][b ]-E[C]) fori = 1,2,...,n (13) 7

4.3 Optimization of Jobs with Random Processing Time on a Single Machine This is a generalization of the problem in [4,6] by making some of its variable random. Consider a set of n independent single operation jobs to be processed by a single machine. Once processing of a job starts, it continues until the processing of all jobs finish. No preemption is assumed. Let ti, Fi = tl+...+ti and fi(t) = ai exp(t) be processing time, flow time (completion time) and cost function of job i, (i = 1,2,...,n), respectively. Assume ti to be a positive random variable and ac is a constant. Therefore, Fi andfi(t) are also random variables, since they are functions of t. The random variables ti's are independent. The objective is to find an optimal ordering (optimal sequencing) to minimize the expected total cost. The total cost is given by TC(7) = Ifj,(F,) (14) The expected total cost is given as: E[TC(r)] = E[f, (F, ) i=1 let wi, Pi, ti and H for all jobs as follows: wi = a exp(ti), Pi = exp(ti) -1 fj( Ul i2'..ji) = j1, exp(F, ), H( 2,'-.,i) = exp(F,_, ) for i = 1,2,...,n, and H(O) = 1. Then the condition of theorem 2 is satisfied and 7r is optimal if and only if h(jl,) < h(j2) <... < h(jn) where h(j) = E[exp(ti )] -1/ aij E[exp(tj)], i = 1,2,...,n (16) In the above problem if we assume the cost function is linear instead of exponential, i.e. fi(t) = acj t. Then the stochastic version of the problem in [7] is 8

obtained. The expected total cost is given as: E[TC()] = aj E[tjI + t+... ] *-1 = a i(E[th ] + E[t, ]+...+E[t ]) (17) i=1 If wi, Pi, f and H are defined for all jobs as: wi = a, Pi = -ti for all jobs f i, (j,, j2- i) = a, (Fii ) = aj, (t, + t +...+ti ) and H(jl, j2,... i) = 1 for all jobs. The conditions of theorem 2 are met and a sequence n is optimal if and only if h(j) < h(j2) <... < h(jpg) where h(ji)= E[ti]/ a, for i = 1,2,...,n (16) 5.0 Conclusion In this paper a stochastic sequencing problem has been defined. The necessary and sufficient conditions for finding the optimal sequence has been derived. The stochastic sequencing problem generalizes the deterministic sequencing problem given [4] by considering some of the input variables as random. The stochastic sequencing problem represent many practical situations such as sequencing characteristic for inspection, jobs processing and candidate selection. When the random variables are assumed constants in the stochastic sequencing model the results of this paper specialize to results in [3,4]. 6.0 Acknowledgment The author would like to acknowledge the support provided by King University of Petroleum and Minerals, Dhahran, 31261, Saudi Arabia, during his Sabbatical leave. Also, the industrial and Operations Engineering Department is acknowledged for hosting the author and extending its facilities. 9

7.0 References 1. Raouf, A., J.K. Jain, and P.T. Sathe. A Cost Minimization Model for Multicharacteristic Component Inspection, IIE Transaction, Vol. 15, No. 3, pp. 187-194, 1983. 2. Lee, H.L. On the Optimality of a Simplified Multicharacteristic Inspection Model, IIE Transactions, Vol. 20, No. 4, pp. 392-398, 1988. 3. Duffuaa, S.O., and A. Raouf. An Optimal Sequence in Multicharacteristic Inspection, Journal of Optimization Theory and Applications (JOTA), Vol. 67, No. 1, pp. 79-86, 1990. 4. Alidaee, B. On Optimal Ordering Policy of a Sequencial Model, Journal of Optimization Theory and Applications (JOTA). (Accepted) 5. Kwan, C.C., and Y. Yuan. A Sequencial Selection Problem, Decision Science, Vol. 19, pp. 762-770, 1988. 6. Lawler, E.L., and B.D. Sivazlian. Minimization of Time-Varying Costs in Single-Machine Scheduling, Operations Research, Vol. 26, No. 4, pp. 563569, 1978. 7. Smith, W.E. Various Optimizers for Single-Stage Production, Naval Research Logistics Quarterly, Vol. 3, pp. 54-56, 1956. 10