An Operational Decision Model for Lead-Time and Price Quotation in Congested Manufacturing Systems

European Journal of Operational Research 126 (2000) 355±370 www.elsevier.com/locate/dsw Theory and Methodology An operational decision model for lead-time and price quotation in congested manufacturing systems Mohsen ElHafsi Anderson Graduate School of Management, University of California, Riverside, CA 92521-0203, USA Received 1 June 1998; accepted 1 May 1999 Abstract This paper considers the problem of determining the lead-time and price to be quoted to a single order in a make-toorder manufacturing setting. The manufacturing system consists of several processing centers all subject to random failures and repairs. Because of a time window constraint on the delivery of the order, the latter has to be split among several processing centers to meet the constraint imposed on its delivery date. The assignment of lots to the processing centers is based on minimizing the operating cost associated with the entire order (i.e., its price). Two major cases are studied: the case of rushed order and the case of regular order. Each case has two options: Partial deliveries allowed and partial deliveries not allowed. Exact and heuristic algorithms are developed for each situation. Numerical results are used to draw conclusions and test the performance of the heuristics. Ó 2000 Elsevier Science B.V. All rights reserved. Keywords: Production planning; Scheduling; Lot sizing; Stochastic; Optimization 1. Introduction Short lead times and quick response to customer orders are important strategic considerations for a ®rm to survive in a time-based competition market place. The success of the Japanese manufacturing Just-In-Time (JIT) practices, which highlight the importance of short-lead times, has further increased the level of competition. In addition, in todayÕs global manufacturing, characterized by quick technology advances and availability of capital, ®rms are increasingly dependent on fast response times as an important source of sustainable competitive advantage. It is reported that the ®rm that can o€er and realize shorter lead-time due dates is subject to less pressure when competing on the basis of price (Blackburn, 1991). In this paper, we propose a normative model that addresses the customer preference with respect to price and lead-time due date. We study the problem of how a ®rm should determine the price and the lead-time due date to be quoted to an upcoming order, based upon the congestion level of the manufacturing shop ¯oor and the operating cost associated with the production of the order. This problem was motivated by an aluminumparts manufacturing plant. The latter runs seven 0377-2217/00/$ - see front matter Ó 2000 Elsevier Science B.V. All rights reserved. PII: S 0 3 7 7 - 2 2 1 7 ( 9 9 ) 0 0 2 9 4 - 5 356 M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370 automated assembly lines and manufacture about 1700 di€erent part types. The manufactured parts are supplied to automotive manufacturers, home appliance manufacturers, and other customers. Due to various degrees of automation, several lines can be used to process the same part. The lines have di€erent throughput rates and operating costs. Usually, high production rate means lower cost. A major setup is required for switching a line to a new part type (the major part of the setup is performed o€ line). In this environment operating costs are heavily a€ected by the allocation of jobs to assembly lines. Cost reduction and short leadtime are the primary competitive tools in this environment. A decision support system for production planning can be used by the marketing/ sales department to quote customers realistic leadtime due dates. If costs of new orders can be approximated in advance (by determining the optimal allocation that does not violate committed orders), the customer can be quoted a di€erent price for his requested shipment date. Rushing orders would increase the manufacturing costs, and hence these costs would be passed to the customer. On the other hand, if the customer accepts the manufacturerÕs lead-time due date, the quoted price could be signi®cantly lower. Many other similar examples exist. For instance, many manufacturing systems specialize in certain types of products to serve only a ®xed number of customers. This is the case of small ®rms that are owned by larger ones, such as in the automotive industry (i.e., component suppliers, such as brakepad manufacturers). A number of papers have focused on the leadtime due date setting problem. Early work in this research area consisted of studies where the objective is to minimize the average weighted due date quoted to customers while maintaining a certain service level (Eilon and Chowdhury, 1976; Weeks, 1979; Seidmann and Smith, 1981; Baker and Bertrand, 1981a,b; Bertrand, 1983; Baker, 1984). The service level is de®ned as either the maximum allowable average tardiness of jobs, or the average percentage of tardy jobs. The manufacturing system is usually assumed to be a single resource system. Recently, analytical models for due date setting were considered by Bookbinder and Noor (1985), Wein (1991) and Chand and Chhajed (1992). The major ®nding of these studies is that ®rms that assign customers lead-time due dates based upon shop ¯oor congestion information achieve better on time delivery. A more recent line of research consists of the work of Wein et al. (1990), Li and Lee (1994), Lederer and Li (1994) and Duenyas and Hopp (1995). These studies broadly address the e€ect of quoted price and leadtime due dates on customer demand. Most of the above literature deals with leadtime and pricing decisions at a strategic level and focuses on simple models (e.g., M/M/1 and M/G/1 systems) dealing with a single product. However, they serve in gaining insight into the nature of the pricing and due date setting problem. Unfortunately, these models cannot be used to make day to day operational decisions. Such decisions are crucial to the survival of ®rms operating in highly competitive markets. Including operational level details in the above studies would result in intractable models. Similarly, it is extremely dicult to include strategic level information into an operational decision model. In this paper, we address day to day operational decisions that a ®rm faces with respect to quoting lead-time due date and price to an order about to be placed. The primary objective of this research is to develop a model that includes as much detail as possible so that realistic lead-time due date and price can be achieved and quoted to the customer. The tools developed for decision making are very simple, yet powerful in terms of eciency and speed (e.g., in a real-time decision making environment). The rest of this paper is organized as follows. In Section 2, we present the mathematical model. In Section 3, we study the case of a rushed order. Section 4 discusses the case of regular order. In Section 5, we present numerical results. Section 6 concludes the paper. 2. Model formulation and basic results 2.1. Problem statement Consider a manufacturing system consisting of m processing centers. The centers can be thought M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370 of as manufacturing cells. The partition of the manufacturing system into centers is not necessarily physical (i.e., it may be a logical partition according to di€erent production processes). For a similar application, the reader is referred to Liu (1990). The centers are subject to random failures. We assume that the probability law of the failure process is known and follows a Poisson distribution (i.e., the time between failures is exponentially distributed). Each failure is followed by a constant restoration or repair time. The assumption on the breakdown distribution represents systems with many unreliable sources or components, each susceptible to breakdown (see Barlow and Proschan, 1965). Furthermore, the assumption that the restoration time is constant, approximately describes the repair process of modern manufacturing equipment that is frequently based on modular design. We assume that at the time a new orderP is being placed, there are already n ˆ mjˆ1 nj ‡ 1† lots scheduled for processing (with m lots currently being processed). Let nj be the number of lots queued at Center j. Let Lij i ˆ 1; 2; . . . ; nj † represent the ith lot waiting to be processed at Center j. Lots L1 ; L2 ; . . . ; Lm are the ones currently being processed at Centers 1; 2; . . . ; m, respectively. Each lot requires a setup time before its processing begins. The problem can then be stated as follows: Consider a make-to-order manufacturing system and assume that an order is about to be placed. The order could be from an outside customer or could be internal (e.g., a subassembly component). The order should be completed and delivered within a certain time window. As a result, management would like to determine how to schedule this order among the processing centers so as to minimize the total operating cost and/or how to assign a lead-time due date for this order that does not violate the speci®ed time window. To respond to the above statement, few preliminary results are needed. The following notation will be used throughout the rest of the paper. Notation kj sj Xj qij qj Rij rj sij Uj Uij Nj Nij Cij rij ˆ Pi kˆ1 skj hij ˆqj =r Pj ‡ ikˆ1 qkj =Rkj Q xj sj Sj ˆ sj ‡ rnj ;j Rj N xj † 357 failure rate of Center j repair time of Center j generic random variable (r.v.) of the sequence of up-times when Center j is processing a lot size of Lot Lij size of Lot Lj processing rate of units from Lot Lij processing rate of units from Lot Lj setup time of Lot Lij total time to process Lot Lj (r.v.) total time to process Lot Lij (r.v.) number of failures of Center j until Lot Lj has been completed (r.v.) number of failures of Center j until Lot Lij has been completed (r.v.) completion time of Lot Lij (r.v.) total setup time incurred before processing of Lot Lij begins total deterministic processing time including that of Lot Lij size of the order about to be placed portion of Q to be manufactured at Center j (decision variable) setup time associated with Lot xj at Center j total setup time before Lot xj begins processing processing rate of units from Lot xj number of failures of Center j until Lot xj has been completed (r.v.) 358 M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370 2.2. Preliminary results It is not dicult to see that the processing time of a particular lot at a particular center is the sum of the processing time without interruptions and the time spent in repairs. As a result, we have Uj ˆ qj =rj ‡ sj Nj ; 1† Uij ˆ qij =Rij ‡ sj Nij : 2† Proposition 1. Uj Uij † has a Poisson distribution at mass points unj ˆ qj =rj ‡ nsj unij ˆ qij =Rij ‡ nsj †, for n ˆ 0; 1; 2; . . . In other words, n PrfUj ˆ unj g ˆ kj qj =rj † eÿkj qj =rj =n!; and PrfUij ˆ unij g ˆ kj qij =Rij †n eÿkj qij =Rij =n! for n ˆ 0; 1; . . . For the purpose of clarity, all proofs are deferred to the Appendix A. Proposition 2. Cij has a Poisson distribution at mass points cnij ˆ rij ‡ hij ‡ nsj , for n ˆ 0; 1; 2; . . . In other words, n PrfCij ˆ cnij g ˆ kj hij † eÿkj hij =n! for n ˆ 0; 1; . . . Proposition 3. The expected inventory of finished items until Lot xj has been completed is given by
ÿ
ÿ 3† Ij xj ˆ x2j 1 ‡ kj sj =2Rj : Notice that the dimension of Ij xj † is in (unit) (time unit). 2.3. Mathematical formulation First, we have the following relationship: m X xj ˆ Q: 4† jˆ1 Using Proposition 2, the completion time of Lot xj , Cj xj †, has a Poisson distribution at mass points cnj ˆ Sj ‡ xj =Rj ‡ hnj ;j ‡ nsj In other words, n o Pr Cj xj † ˆ cnj ÿ ÿ

n ˆ kj xj =Rj ‡ hnj ;j eÿkj for n ˆ 0; 1; 2; . . . xj =Rj ‡hnj ;j † =n!: 5† For Lot xj to be scheduled at Center j, let Aj denote the setup cost, pj denote the production cost per unit, h denote the unit inventory carrying cost of ®nished products per time unit and b denote the unit backlog cost of ®nished products per time unit. We assume that the added value between the un®nished work and ®nished work is an order of magnitude higher. As a result, the inventory carrying cost of un®nished products is neglected. Let Tj denote the planned lead-time due date of Lot xj (Tj is a decision variable). The operating cost associated with Lot xj is then given by ÿ
fj xj ; Tj † ˆ Aj d xj † ‡ pj xj ‡ h 1 ‡ kj sj x2j =2Rj ÿ
‡ ‡ hxj E Tj ÿ Cj xj †
‡ ÿ ‡ bxj E Cj xj † ÿ Tj : 6† Here, c‡ ˆ maxfc; 0g for any real number c, and d xj † denotes the indicator function de®ned as follows: d x† ˆ 1 if x 6ˆ 0 and d x† ˆ 0 otherwise. The ®rst term in Eq. (6) represents the setup cost incurred if Center j were to be used. The second term represents the production cost at Center j. The third term represents the average in-process inventory cost of ®nished items at Center j, (i.e., hIj xj †). The fourth term represents the inventory cost associated with a lot completed before its planned lead-time due date. The last term represents the backlog penalty associated with a lot completed after its planned lead-time due date. It is not dicult to show that M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370 ÿ
‡ E Tj ÿ Cj xj † mj X ÿ
Tj ÿ Sj ÿ xj =Rj ÿ hnj ;j ÿ nsj ˆ nˆ0 n o  Pr Cj xj † ˆ cnj ; ÿ
‡ E C j xj † ÿ Tj
‡ ÿ ˆ E Tj ÿ Cj xj † ‡ Sj ‡ xj =Rj ‡ hnj ;j ÿ
‡ sj kj xj =Rj ‡ hnj ;j ÿ Tj : 7† 8† mj ˆ b Tj ÿ Sj ÿ xj =Rj ÿ hnj ;j †=sj c with bxc being the largest integer no greater than x. The objective function Eq. (6) assumes that the order can be partially delivered at planned leadtime due dates Tj . At this stage, we will adopt a general approach to formulate the problem. Later, we will discuss di€erent situations including the case of no partial deliveries. We also assume that shipment time is not signi®cant compared to completion time. Further, we assume that shipment costs are linear in the shipment size. This last assumption allows us to treat shipment costs implicitly rather than explicitly. Indeed, the per unit shipment cost can be added to the per unit production cost. The formal optimization model can be written as follows: P† Minimize f x; T † ˆ s.t. m X jˆ1 xj ˆ Q; m X jˆ1 fj xj ; Tj † 3. The case of a rushed order 10† j ˆ 1; . . . ; m; 11† TL ÿ Tj 6 0; j ˆ 1; . . . ; m; 12† j ˆ 1; . . . ; m: 13† 0 that Lot xj be completed and delivered no earlier than Time TL . Constraint set (13) represents the usual non-negativity constraints. Problem (P) is formulated in such a way that it can be used either as a tool for estimating or as a tool for negotiating the lead-time due date and price (i.e., operating cost plus a pro®t margin) of a certain order. In the ®rst case, by setting the value of TU to in®nity, one obtains the minimum operating cost lead-time(s) due date. This case happens when a customer is willing to wait for whatever time it takes to complete the order. In the second case, if a customer is not satis®ed with the initially proposed lead-time due date (i.e., at the lowest operating cost), an earlier lead-time due date can be assigned to the variable TU and another lead-time due date is determined. It is clear that the operating cost will increase. The incremental cost can be either partially or totally passed to the customer at the discretion of the ®rm. The negotiation process continues until an agreement is reached. The lower bound on the order completion time, TL , is added to make the model more general, or TL may denote the time until which the shop ¯oor is already committed and hence the order cannot start sooner. This situation happens when a customer speci®es a time window for her order lead-time due date to avoid having the order before it is needed (e.g., in a Just-In-Time context). 9† Tj ÿ TU 6 0; xj P 0; 359 0 Here, x ˆ x1 ; x2 ; . . . ; xm † and T ˆ T1 ; T2 ; . . . ; Tm † are two m-dimensional vectors. Constraint (11) makes sure that Lot xj be completed and delivered no later than Time TU . Constraint (12) makes sure This situation arises when a customer is in a hurry to receive her order and does not care much about the price to be quoted to her. Also, if the order is internal and is running behind schedule, it has to be rushed and ®nished as early as possible. Note that this situation does not describe expediting an order, since we do not allow bumping out previously scheduled orders. To capture this aspect, we have to split the order on as many centers as possible so that the smallest possible lead-time due date(s) is achieved. The idea is to order the centers (in the stochastic sense) in ascending order of their workload (i.e., according to their earliest availability epoch), then assign lots to the earliest available centers ®rst. 360 M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370 Before we provide a procedure for ®nding the shortest completion time(s) at the centers, we need to discuss what we mean by stochastic ordering. A common way to compare the magnitude of two random variables is by so-called stochastic ordering (see Ross, 1982). De®nition 1. We say that a random variable X is stochastically larger than a random variable Y, denoted X P st Y , if PrfX P ag P PrfY P ag, for all a. This is equivalent to E‰g X †Š P E‰g Y †Š, for all non-decreasing functions g. This is a very strong ordering, which can be best illustrated by its coupling property: X P st Y if and only if there exist two random variables X and Y  on a common probability space that have the same probability distributions as X and Y, respectively, and such that Pr fX  P Y  g ˆ 1. We now use the above results to derive rules for stochastically ordering the processing centers according to their availability time. Let Nj t† denote a Poisson random variable with mean kj t. De®nition 2. The availability time of Center j is given by the random variable Ej ˆ Sj ‡ hnj ;j ‡ sj Nj hnj ;j †: Proposition 4. Let Ej and Ek be the availability time at centers j and k, respectively. Then, ÿ
Ej P st Ek () Sj ÿ Sk ‡ hnj ;j 1 ‡ kj sj ÿ hnk ;k 1 ‡ kk sk † P 0: An immediate consequence of Proposition 4 is that we can stochastically order the centers in ascending order of their availability time. Now, to obtain the shortest completion time in the stochastic sense, we ®rst note that Proposition 4 applies to the completion time of lots xj and xk as follows: ÿ
Cj xj P st Ck xk †

ÿ ÿ () Sj ÿ Sk ‡ xj =Rj ‡ hnj ;j 1 ‡ sj kj ÿ xk =Rk ‡ hnk ;k † 1 ‡ sk kk † P 0: Using this last result, we note that if a center is selected and assigned a lot, then its completion time cannot exceed the completion time of another selected center. As a consequence, the centers must be assigned lots such that, they all ®nish (in the stochastic sense) processing at the same time. Algorithm 1, below, is based on this result. First, assign to the earliest available center, say Center i, a lot such that the completion time of Lot xi at Center i equals the availability time of the next center, say Center k. If the order quantity is not exhausted, then assign lots to Centers i and k, such that their completion time equals the next availability time. Continue in this fashion until all Q units of the order are assigned. Algorithm 1 (Rushed order). Initialization Step: Sort center indexes according to increasing values of Sj ‡ hnj ;j ‡ sj kj hnj ;j †, j ˆ 1; . . . ; m. For convenience, label the centers according to the above sorting criterion. That is, S1 ‡ hn1 ;1 1 ‡ s1 k1 † 6 S2 ‡ hn2 ;2 1 ‡ s2 k12 † 6


6 S2 ‡ hn2 ;2 1 ‡ s2 k2 †. For j ˆ 1; . . . ; m, let xj :ˆ 0 and set j :ˆ 1. Go to Main Step. Main Step: For i ˆ 1; 2; . . . ; j, set ÿ 
yi :ˆ Ri Sj‡1 ‡ hnj‡1 ;j‡1 1 ‡ sj‡1 kj‡1  ÿ Si ÿ hni ;i 1 ‡ si ki † = 1 ‡ si ki †: 14† Piˆj Set Q0 :ˆ Q ÿ iˆ1 yi . If Q0 > 0, set xi :ˆ yi , for i ˆ 1; 2; . . . ; j, and set j :ˆ j ‡ 1. If j ˆ m, go to Termination Step, otherwise, go to Main Step. If Piˆj Q0 6 0, set Q0 :ˆ Q ÿ iˆ1 xi and go to Termination Step. Termination Step: Solve the following system of linear equations: y1 ‡ y2 ‡


‡ yj ˆ Q0 y1 1 ‡ s1 k1 †=R1 ˆ y2 1 ‡ s2 k2 †=R2 .. . ÿ ÿ

yjÿ1 1 ‡ sjÿ1 kjÿ1 =Rjÿ1 ˆ yj 1 ‡ sj kj =Rj : 15† Set xi :ˆ xi ‡ yi for i ˆ 1; 2; . . . ; j. The set of equations (14) allows the assignment of lots to Centers 1 through j such that they all M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370 complete processing at the expected availability time of Center j ‡ 1. Linear system (15) allows dividing any remaining units from the order among the chosen centers, so that all the centers ®nish processing (in the stochastic sense) at the same time. In fact, (15) can be solved in closed form using the following formulae: y i ˆ Q 0 Ri = 1 ‡ k i s i † for i ˆ 1; . . . ; j: kˆj X kˆ1 Rk = 1 ‡ k k s k † At this stage one may calculate the expected completion time of Lots xj at the selected centers and may use these as the quoted delivery date. But a quoted delivery date based on expectations only, may not be accurate since it ignores the distribution of the completion times. Now, given the distribution of the completion time of Lots xj , one can derive the lead-time due date(s) of the entire order. This may be achieved by minimizing the weighted expected deviation from the planned lead-time due date(s). For Center j, this is given by ÿ
‡ ÿ
‡ fj Tj † ˆ hxj E Tj ÿ Cj xj † ‡ bxj E Cj xj † ÿ Tj : 361 Here mj ˆ b Tj ÿ Sj ÿ xj =Rj ÿ hnj ;j †=sj c. In other words, Tj is the value for which Expression (17) exceeds b= b ‡ h†, through mj , for the first time. Remark. The term b= b ‡ h† represents the probability that the actual completion time of a lot is less than the quoted lead-time due date. Therefore, it could be thought of as a measure of the service level that the manufacturer would like to achieve. The latter could be set according to a certain industry standard. Since the centers complete at the same time on average, we expect the Tj Õs to be equal. But, because the completion time at a center is discrete, there may be a slight di€erence in the Tj Õs. The latter are computed using (17). First, mj is calculated starting with mj ˆ 0, then mj ˆ 1, and so on until condition (17) is satis®ed. Then, Tj is calculated using Tj ˆ sj mj ‡ Sj ‡ xj =Rj ‡ hnj ;j : 18† The quoted delivery date could be calculated using the following: 16† fj Tj † denotes the weighted deviation from the planned lead-time, Tj , at Center j. Here, h and b can be thought of as penalties incurred for completing Lot xj before or after its planned lead-time due date, respectively. Notice that minimizing fj Tj † is equivalent to solving a Newsboy Problem where Tj is equivalent to the quantity to be ordered, Cj xj † is equivalent to the demand to be satis®ed, hxj is equivalent to the unit overage cost and bxj is equivalent to the unit shortage cost. The following proposition is a direct consequence of the Newsboy ProblemÕs results and therefore its proof is omitted. Proposition 5. fj Tj † is convex in Tj and attains its minimum at the value Tj where  mj n  o  X  Pr Cj xj † ˆ cnj Pr Cj xj † 6 Tj ˆ nˆ0 P b= h ‡ b†: 17† n o T  ˆ max Tj : j;xj >0 19† To illustrate the above algorithm, consider a simple example of a manufacturing system consisting of four processing centers. Table 1 gives the characteristics of the processing centers. The order size is Q ˆ 100 units, h ˆ $1/unit/time unit and b ˆ $10/unit/time unit. The expected availability time summarizes the data for the already scheduled orders (i.e., indicates the workload at a speci®c center). The result of running Algorithm 1 indicates that 23 units of the order should be scheduled for processing at Center 1, 48 units to be scheduled for processing at center 3, and 29 units to be scheduled for processing at Center 4. The lead-time due dates to be quoted are T1 ˆ 12:9 days, T3 ˆ 13:3 days, and T4 ˆ 12:8 days. Therefore, the earliest time the order can be delivered is after 13.3 days of its receipt. Note that this lead-time due date will be met with a probability of 91% (service level). 362 M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370 Table 1 Processing centersÕ data Processing centers Failure rate (per day) Restoration time (in days) Processing rate (units/day) Expected availability time (in days) 1 2 3 4 1 0.25 10 9 0.75 0.5 10 17 1 0.5 15 7 0.25 0.33 20 10 4. The case of a regular order 4.1. Exact solution approach In this section, we study the case of customers who are willing to wait for their order as long as necessary so that they are quoted the lowest price. The goal is to determine a lead-time due date(s) that minimizes the total operating cost of the entire order. This is achieved by solving Problem (P): To be able to solve Problem (P), ®rst ®x the Tj Õs and de®ne the function f  T † as P† s:t: Minimize g x; T † 6 0: f x; T † ˆ m X jˆ1 fj xj ; Tj † 20† 21† x and T are the vectors of lot sizes and lead-time due dates, and f and g denote the objective function (9) and constraints (10)±(13), respectively. Notice that Problem (P) can be easily transformed into a mixed 0±1 nonlinear optimization problem with a nonlinear objective function and linear constraints. Indeed, since we do not know which centers are to be used for the current order, the d xj †'s are 0±1 decision variables as well. In general, Problem (P) is very dicult to solve. If the Tj Õs are ®xed and we ignore the nonlinear terms of the objective function, then the problem reduces to the ®xed-charge problem (see Murty, 1968). By employing an extreme-points ranking solution procedure, the number of vertices is factorial in the number of constraints. This implies that a solution procedure may have to rank all possible vertices before identifying the optimal vertex. In Section 4.1, we present an exact solution approach using a dynamic programming formulation. Section 4.2 deals with heuristic algorithms. f  T † ˆ Minf f x; T †jg x; T † 6 0g; 22† so that f  T † is the minimum cost solution to (9)± (13) if vector T is ®xed. Proposition 5 indicates that f  T † is jointly convex in T (Because the Tj Õs are independent decision variables). Further, f  T † exists on the bounded set de®ned by constraints (11) and (12). Now let us focus on how to obtain the optimal solution f  T † given T. Because f x; T † is neither convex nor concave in the vector x, and especially because of the presence of the ®xed charges (i.e., the setup costs), we cannot use any of the conventional nonlinear programming tools. Instead, we use a Dynamic Programming (DP) approach to solve for x in f x; T †, given a ®xed vector T. Let /l q† represent the minimum objective function value when q units are split among Centers 1; 2; . . . ; l. Then the following DP solves Problem (P), for a given lead-time due date vector, T. Procedure 1: DP algorithm Recurrence relation: /l‡1 q† ˆ min f/l q ÿ xl‡1 † ‡ fl‡1 xl‡1 ; Tl‡1 †g; 0 6 xl‡1 6 q q 2 ‰0; QŠ; l 2 ‰0; m ÿ 1Š: Boundary conditions: /0 q† ˆ 0 if q ˆ 0 and /0 q† ˆ 1; otherwise: M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370 Optimal policy: Optimal lot sizes at each stage: x1 ; x2 ; . . . ; xm . Optimal objective function value: /m Q†. The state space of the DP is O mQ†. An iteration of the recurrence relation takes O Q† time. Hence, Problem (P) can be solved in O mQ2 † time. Once the DP has been solved, the lot sizes x1 ; x2 ; . . . ; xm are used in the expression of f  T †. The latter is then optimized with respect to the lead-time due date vector T (depending on whether partial deliveries are allowed or not). The optimal lead-time due date vector T, say T , is then plugged back into the expression of f  T † and the DP is solved again for the xj Õs, and so forth until either the lot sizes or the lead-time due date(s) converge. First, we study the case of allowed partial deliveries. 363 proposition characterizes the optimal value of T, given a vector x of lot sizes. Again, this is a straightforward extension of the Newsboy problem. Hence, its proof is omitted. Proposition 6. f  T † is convex in T and attains its minimum at T  satisfying m X ÿ jˆ1
ÿ
xj =Q Pr Cj xj † 6 T  P b= b ‡ h†: 23† ÿ
Here mj ˆ b T  ÿ Sj ÿ xj =Rj ÿ hnj ;j =sj c. In other words, T is the minimum value for which Expression (23) is satisfied. To solve for T in Eq. (23), we use the following procedure. Procedure 2: Computing T  4.1.1. The case of allowed partial deliveries In this case, since given xj ; fj xj ; Tj † is convex in Tj ; Tj is computed using Proposition 5. The algorithm to solve Problem (P) in this case is the following: Algorithm 2 (Regular order ± partial deliveries allowed). Initial Step: Choose a feasible vector of planned lead-time due dates T 0 . Let xk and T k be the vector of lot sizes and the vector of planned lead-time due dates at the kth iteration, respectively. Set k :ˆ 1, x0 :ˆ 0. Let e be a scalar. Go to Main Step. Initialization Step: Set mj :ˆ 0, for j ˆ 1; 2; . . . ; m. Main Step: Evaluate Expression (23) using the mj Õs set before. If Expression (23) is satis®ed, go to Termination Step. If not, Compute Tj ˆ sj mj ‡ 1† ‡ Sj ‡xj =Rj ‡ hnj ;j , for j ˆ 1; 2; . . . ; m. Set l :ˆ arg min Tj , and ml :ˆ ml ‡ 1. Go to 16j6N Main Step. Termination Step:  min sj mj ‡ Sj ‡ xj =Rj ‡ hnj ;j : T ˆ 1 6 j 6 N ; xj >0 Main Step: Solve for xk using Procedure 1 (i.e., the DP algorithm). Solve for T k as follows: Tjk ˆ sj mkj ‡ Sj ‡ xkj =Rj ‡ hnj ;j ; If Tjk > TU set Tjk :ˆ TU ; If Tjk < TL set Tjk :ˆ TL . This assures the feasibility of Tjk . mkj is calculated using (17). If kxk ÿ xkÿ1 k 6 e or kT k ÿ T kÿ1 k 6 e, go to Termination Step. Otherwise, set k :ˆ k ‡ 1 and go to Main Step. Initialization Step: Choose a feasible planned leadtime due date T 0 . Let xk and T k be the vector of lot sizes and the planned lead-time due date at the kth iteration, respectively. Set k :ˆ 1, x0 :ˆ 0. Let e be a scalar. Go to Main Step. 4.1.2. The case of no partial deliveries allowed In this case, the vector of planned lead-time due dates reduces to a scalar T. Algorithm 2 can still be used with slight modi®cations. The following Main Step: Solve for xk using Procedure 1 (i.e., the DP algorithm). Use Procedure 2 to compute T k . If T k > TU set T k :ˆ TU ; If T k < TL set T k :ˆ TL . If kxk ÿ xkÿ1 k 6 e or T k ÿ T kÿ1 † 6 e, go to Termination Step, otherwise set k :ˆ k ‡ 1 and go to Main Step. Termination Step: x :ˆ xk ; T  :ˆ T k . The minimum objective function value is f  T  †. Algorithm 3 (Regular order ± no partial deliveries allowed). 364 M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370 Termination Step: x :ˆ xk , T  :ˆ T k . Before we proceed any further, we note that Algorithms 2 and 3 are heavily dependent on the starting vector of planned lead-time due dates T 0 . A good starting solution will spare several iterations (especially that each iteration involves a DP algorithm and cost evaluation is costly because of the discrete nature of the distribution of the completion times). To develop a good startup procedure, we ®rst note that the bulk of the cost associated with the use of a particular center j is given by f~j xj † ˆ Aj d xj † ‡ pj xj ‡ h 1 ‡ kj sj †=2Rj †x2j : Notice that f~j
† is a quadratic function with a ®xed charge. Furthermore, f~j
† is strictly increasing in its argument. Now, consider the following optimization problem: ( m m X X xj ˆ Q; f~j xj † P0 † ˆ Minimize f~ x† ˆ jˆ1 xj P 0; jˆ1 ) j ˆ 1; . . . ; m : Problem (P0 ) can be solved using the above DP procedure with fj xj ; Tj † replaced by f~j xj †. The solution of problem (P0 ), say x0 , is then used to generate a starting vector of lead-time due date(s). To illustrate Algorithms 2 and 3, we use the same example as in Section 3. Table 2 provides additional data for the example. Applying Algorithm 2 to the above example indicates that the whole order (100 units) should be scheduled for processing at Center 4. The leadtime due date to be quoted is T4 ˆ 17 days. The operating cost of the regular order is $2844, while the operating cost of a rushed order is $4851. Here, we notice that for regular orders, the cheapest center(s) (in terms of production and setup cost) are the one(s) that are selected, while for rushed orders, the earliest available centers are the ones that are selected. Also, we notice that a rushed order uses more centers than a regular one, to take advantage of parallel processing. Applying Algorithm 3 gives exactly the same results since only one center is used (i.e., T ˆ T4 ). In Section 4.2, we develop a heuristic solution to the regular order case. 4.2. Heuristic solution approach The motivation for developing a heuristic solution to the case of regular order is based on the following main reasons. First, as we will see later, the heuristics require only information about the mean and variance of the completion time at a particular center. Indeed, in many practical situations, data about the type of distribution of the failure or repair processes is not available. However, statistics such as averages and standard deviations are usually readily available. Second, any other assumptions about the distribution of the failure or the repair processes will result in very complicated expressions of the completion times that cannot be expressed in closed form (i.e., mixed discrete and continuous distributions expressed as convoluted multiple integrals). Third, the proposed heuristics are faster than the algorithms we developed in the previous sections. Before we develop the heuristics, we need the following preliminary results. Let the expected value of the random variable Cj xj † equal to lj xj † ˆ Sj ‡ Kj hnj ;j ‡ xj =Rj †; where Kj ˆ 1 ‡ kj sj †. Then, we have Table 2 Order cost information Processing centers Setup cost ($) Production cost ($/unit) 1 2 3 4 800 20 500 16 1000 23 600 18 M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370

‡ ÿ ÿ E Cj xj † ÿ Tj ˆ E Cj xj † ÿ Tj ‡ lj xj † ÿ Tj =2;
‡ ÿ
ÿ E Tj ÿ Cj xj † ˆ E Cj xj † ÿ Tj ÿ lj xj † ‡ Tj =2: Substituting in the expression of fj xj ; Tj † and rearranging terms, we obtain fj xj ; Tj † ˆ Aj d xj † ‡ pj xj ‡ hKj x2j =2Rj ÿ
‡ b ÿ h†xj lj xj † ÿ Tj =2 ‡ b ‡ h†xj E Cj xj † ÿ Tj =2: Using Cauchy±Schwartz inequality, we have q ÿ
2 E Cj xj † ÿ Tj 6 E Cj xj † ÿ Tj q ˆ ECj2 xj † ÿ 2lj xj †Tj ‡ Tj2 q ÿ
2 ˆ lj xj † ‡ lj xj † ÿ Tj : Notice that the last term to the right of the inequality requires the knowledge of only the ®rst two moments of the distribution of the completion time at a particular center as opposed to the lefthand side of the inequality which requires the knowledge of the distribution of the completion times. Letting f~j xj ; Tj † ˆ Aj d xj † ‡ pj xj ‡ hKj x2j =2Rj 
ÿ ‡ b ‡ h†xj : lj xj † ÿ Tj  q ÿ
2 2; ‡ lj xj † ‡ lj xj † ÿ Tj we obtain fj xj ; Tj † 6 f~j xj ; Tj †, for j ˆ 1; 2; . . . ; m. P Therefore, f x; T † 6 f~ x; T † ˆ mjˆ1 f~j xj ; Tj †. This last inequality follows from the fact that all terms are positive. The main idea of the heuristic is to minimize f~ x; T † instead of f x; T †, and hope to obtain a good solution to the original problem. Property 1. For a fixed value of Tj , f~j xj ; Tj † is strictly increasing in xj . Tj ˆ lj xj † ‡ qhp pi. lj xj † b=h ÿ h=b 2: 365 24† The result follows immediately by taking the derivative with respect to Tj , setting it to zero, and solving for Tj . Convexity is due to the fact that the second derivative of f~j xj ; Tj † with respect to Tj is strictly positive. Property 3. For a fixed vector x, and a scalar T, f~ x; T † is strictly convex in T. The minimum value of f~ x; T † is attained for T satisfying the following condition: m X ÿ
ÿ 
q ÿ
2  xj =Q T ÿ lj xj † lj xj † ‡ T ÿ lj xj † = jˆ1 ˆ b ÿ h†= b ‡ h†: 25† Convexity follows from Property 2. The expression for T is derived by taking the derivative with respect to T, and setting it to zero. Now that we have the necessary tools to develop our heuristics, we ®rst start with the case of allowed partial deliveries. 4.2.1. Heuristic for the case of allowed partial deliveries In this case, the Tj Õs are given in closed form. Substituting Tj in f~j xj ; Tj † gives pq f~j xj † ˆ Aj d xj † ‡ pj xj ‡ bh lj xj †xj ‡ hKj x2j =2Rj : 26† To minimize f~ x† ˆ jˆ1 f~j xj †, we use Procedure 1 with f~j xj † as given in (26). Because of the constraints imposed on the Tj Õs, namely TL 6 Tj 6 TU , the DP procedure has to be modi®ed. First, let xLj and xU j be the lower bound and upper bound on xj , respectively, obtained by solving for xLj and xU j , respectively, in the following equations: Pm The proof is straightforward, therefore omitted. TL ˆ lj xLj † ‡ Property 2. For a fixed value of xj , f~j xj ; Tj † is strictly convex in Tj and attains its minimum at TU ˆ lj xU j †‡ qhp pi. lj xLj † b=h ÿ h=b 2: qhp pi. lj xU b=h ÿ h=b 2: j † 27† 28† 366 M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370 This can be accomplished using a classical numerical method such as bisection search. In addition, because we must have 0 < xLj < xU j < Q, then if Q < xLj , Center j cannot be used (since any quantity assigned to that center has to be greater than xLj to satisfy due date constraints). If xU j > Q ˆ Q. Using these arguments, Prothen, we let xU j cedure 2 is modi®ed as follows. tion Step, otherwise, set k :ˆ k ‡ 1 and go to Main Step. Termination Step: x :ˆ xk , T  :ˆ T k . 5. Numerical results 5.1. Sensitivity of rushed orders to service level Algorithm 4 (Heuristic ± partial deliveries allowed). Initialization Step: Compute xLj and xU j using (27) and (28), respectively. If xLj > Q, eliminate f~j :† from the list of f~j Õs. It is not feasible to use Center U L U j. If xU j > Q then, let xj ˆ Q. Round o€ xj and xj to the nearest integer. Go to Main Step. Main Step: Solve for the vector x using DP Procedure 1 with f~j :† rede®ned as fj xj † ˆ f~j xj † if  xLj 6 xj 6 xU j and fj xj † ˆ 1 otherwise. Let x be the optimal solution and go to Termination Step. Termination Step: Tj ˆ lj xj † ‡ qhp pi lj xj † b=h ÿ h=b =2: 4.2.2. Heuristic for the case of no partial deliveries allowed In this case, T must satisfy condition (25). The following algorithm gives the optimal values of the vector of lot sizes, x, and the planned lead-time due date, T. Because rushed orders are more sensitive to the service level, we study its impact on the quoted lead-time due date as well as the operating cost. We use the data given in Table 1. Fig. 1 shows the variation of the lead-time due date as a function of the service level. Notice that high service levels (90% and above) result in much longer lead-times than moderate service levels (60±80%). Fig. 2 shows the impact of service level on the operating cost (In fact, since the production, setup and inventory costs will be the same, the ®gure reports only the part of the cost that is a€ected by the choice of a service level). Again, we notice that very high service levels are very expensive compared to moderate service levels. 5.2. Performance of the heuristics for regular orders In this section, we experiment with randomly generated data to assess the performance of the two heuristics developed for the case of regular Algorithm 5 (Heuristic ± no partial deliveries allowed). Initialization Step: Let xk and T k be the vector of lot sizes and the planned lead-time due date at the kth iteration, respectively. A starting lot size vector x0 can be obtained by solving Problem (P0 ). Then, T 0 is obtained by solving (25) numerically. Set k :ˆ 1. Let e be a scalar. Go to Main Step. Main Step: Plug the value of T kÿ1 in all f~j Õs. Solve for xk using DP Procedure 1. Using the vector of lot sizes xk , compute T k using Condition (25). If T k > TU set T k :ˆ TU ; If T k < TL set T k :ˆ TL . If kxk ÿ xkÿ1 k 6 e or T k ÿ T kÿ1 † 6 e, go to Termina- Fig. 1. Quoted lead-time due date as a function of the service level. M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370 Fig. 2. Cost of service as a function of the service level. order. But ®rst, we present the data used in these experiments. The parameters used to generate the problem data sets are speci®ed in Table 3. These parameters have p been  drawn p from a uniform distribution U l ÿ 3r; l ‡ 3r†, where l represents the mean and r represents the standard deviation of the generated random numbers. In all Table 3 Experimental data Processing centers Mean time to failure 1=kj † Restoration time sj † Queued orders data Number of lots queued at Center j: nj Quantity to be processed at Center j: qij Processing speed at Center j: Rij Setup time at Center j: sij In-process orders Quantity to be processed at Center j: qj Processing speed at Center j: rj Order to be scheduled Setup cost at Center j: Aj Production cost at Center j: pj Holding cost: h Backlog cost: b Order size: Q Processing speed at Center j: Rj Setup time at Center j: sj 20 days 2 days 5 lots 15 units 10 units/day 2 days 75 units 10 units/day $500 $5/unit 10% of average (pj ) b ˆ 10 h 100 units 10 units/day 2 days 367 cases, the standard deviation is chosen to be 50% the value of the mean. Since, in this case, the uniform distribution is completely speci®ed by its mean, only the latter is shown in Table 3. Two criteria are used to evaluate the performance of the heuristics; namely the cost gap and the service gap. The cost gap de®ned as the relative di€erence between the cost of the heuristic solution and the cost of the optimal solution. The service gap de®ned as the relative di€erence between the service level achieved by the heuristic solution and the service level achieved by the optimal solution. The numbers shown in Table 4 are averages over 30 instances for a particular number of centers. Looking at the cost gaps in Table 4, we see that the two heuristics perform very well. The heuristic for allowed partial deliveries performs better. This could be explained by the fact that the heuristic for no partial deliveries allowed, tends to in¯ate the service level, which of course, results in higher costs. It is important to note that because of the discrete nature of the distribution of the completion time, the service level attained will always be slightly higher than the nominal service level b= h ‡ b† (i.e., overshooting of b= h ‡ b† in Propositions 5 and 6). Furthermore, because the Cauchy±Schwartz inequality is based on the service component of the original cost function, the heuristics always resulted in higher service levels. 6. Concluding remarks In this paper, we considered a make-to-order manufacturing system consisting of a set of unreliable processing centers. We were concerned with the scheduling of a single order on the di€erent centers. We considered two main cases. Rushed order and regular order. In the regular order case, we considered two di€erent delivery options: partial deliveries allowed and no partial deliveries allowed. In the case of rushed order, the lead-time due date to be quoted to the order is minimized. In the case of regular order, the expected operating cost associated with the order is minimized. For rushed order, an ecient algorithm was developed based on the idea of stochastic ordering. For regular order, two approaches were adopted. An 368 M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370 Table 4 Heuristics performance N Partial deliveries allowed No partial deliveries allowed % Cost gap % Service gap % Cost gap % Service gap 2 4 6 8 10 0.00 0.56 1.07 1.14 2.32 4.40 4.01 4.20 3.40 4.19 2.10 3.30 4.51 5.80 6.89 7.01 9.20 9.40 7.80 8.56 Average 1.01 4.04 4.52 8.39 exact approach consisting of a dynamic programming approach mixed with partial analytical results. A heuristic approach based on a very well known inequality. Numerical results indicate that the heuristics provide a very good approximation to the optimal solution. An interesting extension to this study is to test the heuristics with other types of distributions for the repair time at the centers. It should be noted though that a closed form expression of the completion time at a center would be extremely dicult. However, for purposes of comparison, numerical integration techniques are becoming easier to handle with the advance of computer technology. If only the mean and variance of the time between failures and time to repair are available, it is relatively easy to determine the mean and variance of the completion time at a particular center (since this is the only information needed for the development of the heuristics). In this case the heuristics provide a robust solutions for the worst case scenarios. Although, in this paper, we assumed that orders are scheduled First-Come First-Served (i.e., dealing with a single order at a time), there are manufacturing systems that do not operate in this fashion. A variant of this problem is to consider the case where an incoming order with higher priority (e.g., from a potential customer) is to be scheduled before other orders or lots that have been already scheduled. The question is which lots to delay, and by how much time, to accommodate the new order. What is the e€ect of rescheduling orders on their operating cost? Should an increase in their operating cost be passed to the new order? In case of a reduction of operating cost, should the savings be passed to a delayed order to compensate for the delay? All these are legitimate questions that can be answered once a model has been established and solved. It turns out that this problem is equivalent to rescheduling all existing orders. Which in turn adds another level of diculty, that of sequencing orders on a several processing centers using the operating cost as the optimization criterion for. Appendix A Proof of Proposition 1. The proof is straightforward and is a consequence of the fact that Nj and Nij follow a Poisson distribution with a Probability Mass Function (PMF)  ÿ
n Pr Nj ˆ n ˆ kj qj =rj eÿkj qj =rj =n! and  ÿ
n Pr Nij ˆ n ˆ kj qij =Rij eÿkj qij =Rij =n!; n ˆ 0; 1; . . .  Proof of Proposition 2. Notice that Cij ˆ Uj ‡ i X kˆ1 ‰skj ‡ Ukj Š: Applying (1) and (2), we have Cij ˆ rij ‡ hij ‡ sj ! i X Nj ‡ Nkj : kˆ1 Because the sum of independent Poisson r.v.Õs is a Pi Poisson r.v., it follows that Nj ‡ kˆ1 Nkj has a Poisson distribution with intensity kj hij (i.e., 369 M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370 Pi Nj ‡ kˆ1 Nkj represents the total number of failures during hij ). Hence, o ÿ n
n Pr Cij ˆ cnij ˆ kj hij eÿkj hij =n!; n ˆ 0; 1; . . . Ij x j † ˆ ‡ sj N xj † X iˆ1 ÿ
xj ÿ Vi : / q; Vi † ˆ q ÿ Vi 0 0 < Vi 6 q ; otherwise: Ij xj † ˆ x2j =2Rj ‡ sj E iˆ1 Ij xj † ˆ x2j =2Rj ‡ sj 1 X Ij xj † ˆ x2j =2Rj ‡ sj 1 Z X iˆ1 iˆ1 ÿ xj ÿ Vi
! ; ÿ
E/ xj ; Vi ; 1 0 ÿ
/ xj ; Vi d PrfVi 6 vg: Assuming that the integrals are absolutely convergent, we obtain Z xj 1 ÿ
X xj ÿ v d PrfVi 6 vg: Ij xj † ˆ x2j =2Rj ‡ sj 0 iˆ1 Noticing that iˆ1 d PrfVi 6 vg ˆ dN v† ˆ kj =Rj dv; we obtain
xj ÿ v dv: Proof of Proposition 4. We carry out the proof in two stages. First, we show that if Nj t† and Nk t†, t P 0, are two Poisson processes with intensity kj and kk , respectively, then Nj t† P st Nk t† () kj P kk : A:1† To prove the )† part of (A.1), we use the de®nition of stochastic ordering. Nj t† P st Nk t† () E‰Nj t†Š P E‰Nk t†Š () kj P kk : ) Nj t ‡ s† P st Nk t† for all s P 0: Taking the expected value, we have N xj † X 0 ÿ The result follows immediately after integrating the above expression.  Nj t† P st Nk t†  xj An immediate consequence is that Let 1 X ‡ sj kj =Rj Z  Proof of Proposition 3. The proof is based on the inprocess inventory of un®nished items or cumulative inventory of un®nished items Ij xj †. The latter is identical to the in-process inventory of ®nished items, since the rate of consumption of un®nished items is identical to rate of buildup of ®nished Pthe i items. Let Vi ˆ Rj kˆ1 Xk represent the amount of ®nished items right after the ith failure. Then, x2j =2Rj Ij xj † ˆ x2j =2Rj A:2† To prove the († part of (A.1), we use the coupling concept. Let Xk;1 ; Xk;2 ; . . . denote a sequence of inter arrival times that are i.i.d random variables having an exponential distribution with rate kk . Then, the Poisson process, generated by Xk;1 ; Xk;2 ; . . ., say N~k t†, has the same probability law as Nk t†. Now let Xj;1 ; Xj;2 ; . . . denote a sequence of inter arrival times that are i.i.d random variables having an exponential distribution with rate kk , and such that Xk;i P st Xj;i , i ˆ 1; 2; . . . Then, the Poisson process, generated by Xj;1 ; Xj;2 ; . . ., say N~j t†, has the same probability law as Nj t†. Now, because Xk;i P st Xj;i for all i, it follows that N~j t† P st N~k t† () Nj t† P st Nk t†: coupling The second part of the proof is straightforward, using (A.1) and (A.2). Noticing that sj , sk , Sj , Sk , hnj ;j , and hnk ;k are all positive variables, we have Nj hnj ;j †P st Nk hnk ;k †()kj hnj ;j Pkk hnk ;k ; sj Nj hnj ;j †P st sk Nk hnk ;k †()sj kj hnj ;j Psk kk hnk ;k ; Ej Pst Ek ()Sj ‡hnj ;j ‡sj kj hnj ;j PSk ‡hnk ;k ‡sk kk hnk ;k :  370 M. ElHafsi / European Journal of Operational Research 126 (2000) 355±370 References Baker, K.R., 1984. Sequencing rules and due date assignments in a job shop. Management Science 30 (9), 1093±1104. Baker, K.R., Bertrand, J.W.M., 1981a. An investigation of due date assignment rules with constrained tightness. Journal of Operations Management 1 (3), 109±120. Baker, K., Bertrand, J.W.M., 1981b. A comparison of due date selection rules. AIIE Transactions 13 (2), 123±131. Barlow, R.E., Proschan, F., 1965. Mathematical Theory and Reliability. Wiley, New York. Bertrand, J.W.M., 1983. The e€ect of workload dependent due dates on job shop performance. Management Science 29 (7), 799±816. Blackburn, J., 1991. Time Based Competition. Irwin, Homewood, IL. Bookbinder, J.H., Noor, A., 1985. Setting job shop due dates with service level constraints. Journal of Operational Research Society 36 (11), 1017±1026. Chand, S., Chhajed, D., 1992. A single model for determination of optimal due dates and sequence. Operations Research 40 (3), 596±602. Duenyas, I., Hopp, W.J., 1995. Quoting customer lead times. Management Science 41 (1), 43±57. Eilon, S., Chowdhury, I.G., 1976. Due dates in job shop scheduling. International Journal of Production Research 14, 223±237. Lederer, P., Li, L., 1994. Pricing, production, scheduling and delivery time competition. Operations Research 45 (3), 407± 420. Li, L., Lee, Y.S., 1994. Pricing and delivery time performance in a competitive environment. Management Science 40 (5), 633±646. Liu, J.J., 1990. Optimal dispatching in a periodic review cellular manufacturing system. Operations Research 38, 893±901. Murty, K.G., 1968. Solving the ®xed charge problem by ranking the extreme points. Operations Research 16, 268±279. Ross, S.M., 1982. Stochastic Processes. Wiley, New York. Seidmann, A., Smith, M.L., 1981. Due date assignment for production systems. Management Science 27 (5), 571±581. Weeks, J.K., 1979. A simulation study of predictable due dates. Management Science 25, 363±373. Wein, L., 1991. Due date setting and priority sequencing in a multiclass M/G/1 queue. Management Science 37 (7), 834±850. Wein, L., Whang, S., Lemire, L.J., 1990. Due Date Setting and Pricing in a Single Server Queue. Technical Report, Sloan School of Management, M.I.T., Cambridge, MA, September 1990.