Enhancing mathematical programming models to account for demand priorities increasing as a function of delivery date

Abstract

Linear and mixed integer programs are frequently used to allocate resources to support a prioritized statement of demands or needs. This paper describes how to enhance these mathematical programming formulations to reflect the dynamic relative importance of demands, namely the priorities of demands – relative to other objectives – increasing as a function of the time of demand fulfillment. We illustrate the modeling using data from a light-emitting diode manufacturer from Taiwan.

Keywords:

• resource allocation
• demand priorities
• customer request date
• delivery date
• mathematical programming

1. Introduction

Linear programming (LP) and mixed integer programming (MIP) have been used often in solving resource allocation problems in a wide range of manufacturing and service industries [11,13,17,18,31]. These include distribution [21], finance [5,29], government [4,7], health care [22], manufacturing [3], purchasing [6,25], and others industries. The resources to allocate vary across organizations but often involve the allocation of some combination of materials, people, money, and machine capacity to fulfill needs such as satisfying customer demand. These needs are often prioritized whether because of their anticipated profitability, the perceived importance of the client being satisfied, prior commitments, or other reasons. When resources limitations prevent the fulfillment of all demands on time, the demand priorities influence how the resources are allocated to best fulfill the most important needs.

The priority of needs can increase as a monotonically non-decreasing function of time to fulfillment. We refer to this as Dynamic Relative Importance. Consider for instance resource allocation decisions made for emergency medical care. A patient can lose some blood without significant threat to life; but if blood loss continues for too long, the result can be organ dysfunction or even death. We might frame this as the urgency of treating the bleeding patient increasing as a function of how long the patient has bled. A similar situation occurs with some diseases and medical conditions (e.g. Sepsis) which can have a mild impact if treated early enough, but lead to hospitalization or even death if not treated by a given point in time.

Imagine a resource-constrained allocation problem involving the planning of multiple projects. It may be desirable to complete a given project early (low priority), on time (moderate priority), and critical to complete the project by a third date (high priority), say, because of contractual or regulatory requirements. If each project is viewed as a demand, then we can model this situation as the demand priorities increasing as a step-function of changes in the expected delivery date (i.e. completion date) of the project.

Make-to-order production planning systems take as input a demand statement of customer orders and create a production plan to support delivery of these orders on time or as close to on time as possible given limited material inventories and work center capacities. Assume that late deliveries of customer orders result in backorders rather than lost sales. Typically, a customer order contains part number, quantity, due date, and priority. When it is not possible to satisfy all demand on time, scarce resources are allocated in favor of delivering on time those customer orders that have the most important priorities. In practice, the priority of satisfying a customer order can vary as a function of its delivery date [8,35]. For example, a customer may want to receive a product by 15 November but it may be important that the product be received no later than 15 December. In this case, satisfying the order by 15 November would be of moderate priority while satisfying the order by 15 December would be of high priority. A similar example would result from a supplier having made a previous commitment to deliver an order by 15 December and considering the customer’s current request to deliver the order by 15 November. In such a case, the supplier would try to fulfill the order by 15 November but would try very hard to fulfill the order by 15 December so as to honor its previous commitment. When allocating scarce resources to satisfy the mid-November deliveries, the customer orders of these examples should be considered as having moderate priority; when allocating resources to satisfy the mid-December (or later) deliveries, these customer orders should be treated as having high priority.

These above-mentioned examples illustrate that demand priorities can change as a function of delivery date in resource allocation problems as diverse as health care, project management, and make-to-order production planning.

Jo et al. [16] describe a queuing model for human dynamics where the task priority can change over time. Wang et al. [35] summarize the enhancements made to an LP model at IBM to accommodate an order’s changing priority when it is delivered later than the customer request date. Bhagwat and Sharma [2] consider on-time delivery to request date and on-time delivery to commit date explicitly as part of the performance metrics. Graves [12] and others assume a lost sales model where demand not fulfilled by its due date disappears; this can be considered as a special case where the priority of a demand drops instantly to zero importance if not satisfied on time.

LP and MIP models are used regularly for resource allocation in semiconductor manufacturing [9,10,14,15,19,20,26,28,30,35].

Sun et al. [32] compare policies for allocating semiconductor lots to customer demands under the assumption that each lot must be allocated to one customer. Liang [23] describes an interactive possibilistic LP method to facilitate decisions on multi-objective supply distribution with imprecise supply chain information. Tang and Yu [33] use mathematical programming to study various logistic issues in build-to-order and configure-to-order manufacturing faced by Taiwan’s PC makers. Lin et al. [24] propose a synchronized planning approach which models strategic and operational supply chain decision-makings in mathematical formulations. Azevedo and Sousa [1] address the problem of planning an incoming order to be produced using simulated annealing and provide preliminary computational results for semiconductor manufacturing.

We use a modified version of the MIP model proposed in Wang [34] and related light-emitting diode (LED) data as a vehicle to demonstrate our method for adjusting an LP formulation to account for demands with priorities that can increase as a function of time to fulfillment. We assume that unsatisfied demand is backordered until resources permit the demand to be satisfied. In Section 2 of this paper, we present an overview of LED manufacturing and an LP model for solving the resource allocation problem for an LED manufacturing enterprise. In Section 3, we illustrate how to adjust a standard production planning LP formulation to accommodate customer order changing priorities as a function of their delivery dates. Section 4 provides numerical validation using real LED manufacturing data to show that our approach is superior to similar models which consider only a constant priority for each demand. We provide concluding remarks in Section 5.

2. Planning for LED manufacturing

2.1. LED manufacturing

LED is a semiconductor technology. Not surprisingly, its manufacturing resembles the process of other semiconductor manufacturing [26,27] very much. It takes two manufacturing stages to fabricate the core component of an LED, i.e. the semiconductor die (Figure 1): epiwafer fabrication and assembly. Most of the epiwafer fabrication takes place in manufacturing facilities called fabs and consists of repetitions of several manufacturing processes to create the desired contact patterns on the surface of the epiwafer, including deposition (distributing photoresist on the epiwafer’s surface), photolithography (reproducing contact patterns by allowing certain parts of the surface to interact with ultraviolet light), and etching (rinsing the surface with developer to expose the patterns). Most of the epiwafer fabrication takes a few weeks to complete and depending on the design, its unit manufacturing cost (i.e. per piece of epiwafer) can range from a few hundred to more than one thousand US dollars. Nearly finished epiwafers are transported to assembly plants for the next manufacturing stage in which six assembly processes are performed in sequence: grind (reducing epiwafer’s thickness), cut (laser-cutting epiwafers), probe (testing the performance of each individual die against certain criteria), automatic optical inspection or AOI, sort (categorizing each individual die), and personal inspection or PI. Laser cut completes the manufacturing process of epiwafers where each individual die is cut, inspected and categorized.

Figure 1. An LED. Source: Wikipedia.

The above processes are done by workstations with a specific epiwafer-size or die-size limitation except for the probe process (Table 1). For example, four and six-inch diameter epiwafers must go to different workstations for grind, cut, and sort processes, as these workstations can only process epiwafers with a specific size. Similarly, epiwafers must go to different workstations for AOI and PI, depending on the size of dies (large, medium, or small) fabricated on them. Probe is the only process without this type of limitation. Compared to the epiwafer fabrication stage, assembly takes a significantly shorter time (about a week or so) and lower cost.

Table 1. Factors influencing workstation selection for LED assembly processes.

Grind	Cut	Probe	AOI	Sort	PI
Epiwafer size	Epiwafer size	None	Die size	Epiwafer size	Die size

Virtually, every LED manufacturer is responsible for both epiwafer fabrication and assembly stages. This is quite unlike other semiconductor manufacturing where most manufacturers are dedicated to just one of the manufacturing stages. For example, TSMC is a well-known foundry dedicated to the wafer fabrication stage prior to assembly and ASE Group is a renowned company dedicated to providing semiconductor assembly and test services.

2.2. LED LP planning model

We present below an LP model formulated for solving the resource allocation problem in LED manufacturing. This model is modified from the MIP model proposed by Wang [34]. The model is formulated as a cost-minimization problem subject to a number of constraints reflecting the basic aspects of LED manufacturing, including manufacturing starts, material flows (within and between supply chain locations), workstation selections, capacity limitations, and demand fulfillment. Customer demand quantities are expressed in terms of “good” epiwafers, that is, all of their dies are functioning according to customer criteria. Epiwafer fabrication yield and operation yield of the selected assembly workstations represent the percentage of epiwafers entering the fabrication and assembly operations which complete the required work in good condition. The model includes routings in assembly plants. Any demand which is not fulfilled when due is backordered to the next period and fulfilled when supply is available. We assume zero lead time to ship from fabs to assembly plants and from assembly plants to demand centers. To facilitate model formulation, we form assembly lines with each consisting of some type of workstation for each of the six processes. The yield of an assembly line is simply the cumulative multiplied yield of workstations in the line. We adjust the MIP model so that it contains sufficient supply chain complexities to illustrate the effect of demand priorities increasing as a function of delivery date. For the purposes of our simplified model, it is not necessary to include the integrality restrictions of the Wang model [34].

Indices

Table

d	Customer demand record (which normally contains attributes such as customer ID, the requested product and its quantity, demand priority, and due date).
w	Epiwafer.
f	Fab location.
a	Assembly plant location.
s	Assembly workstation.
l	Assembly line consisting of a type of workstation to perform each of the six assembly processes.
h	Demand center.
t	Time period.

Each workstation performs a particular type of assembly process, such as grind. Note that each assembly line only processes a particular kind of epiwafer configuration, such as four-inch epiwafers on which small-size dies are fabricated, or six-inch epiwafers on which large-size dies are fabricated. We use to denote the situation where workstation s is contained in assembly line l.

Sets

Table

	The product which is requested by customer demand d.
	Fabs which can perform epiwafer fabrication (the first manufacturing stage) for w.
	Assembly lines which can provide the assembly operations for epiwafer w.
	Epiwafers which may be sent to workstation s for assembly processing.

Parameters

Most of the following parameters have a superscript to indicate the kind of supply chain location for which the parameter applies: an F superscript indicates that the location is a fab and an A superscript indicates that the location is an assembly plant.

Table

DEMQTYdt	Quantity of epiwafers requested by customer demand d in period t.
	Receipt quantities (i.e. projected WIP or purchase orders) of epiwafer w expected to be received at fab location f in period t in nearly finished condition (e.g. after the completion of stage-one manufacturing but before the stage-two assembly).
	Cycle time (a.k.a. lead time) for the epiwafer fabrication stage of epiwafer w at fab location f.
	Output of nearly finished epiwafer w per piece started at fab location f in period t.
	Capacity available for epiwafer fabrication at fab location f during period t.
	Capacity required per piece of epiwafer w at fab location f in period t.
	Cycle time for the processing of epiwafer w at assembly plant location a.
	Cumulative yield for processing one piece of epiwafer w from the first workstation in assembly line l which passes through workstation s to the workstation which immediately precedes workstation s in the same assembly line l at assembly plant a in period t.
	Output obtained for each piece of epiwafer w entering assembly line l at assembly plant a during period t (this is the cumulative yield of the six workstations in l processing one piece of epiwafer w to completion).
	Capacity of workstation s required to process each piece of epiwafer w at assembly plant a in period t.
	Capacity of workstation s available at assembly plant a during period t.

Decision variables

If a variable has an H in its superscript, it means that the variable is related to demand centers. If a variable has an arrow “→” in its superscript, it means that the variable is a transportation decision variable.

Table

	Production starts quantity for epiwafer w during period t at fab location f.
	Quantity of shipments of epiwafer w leaving fab location f during period t destined for assembly plant a.
	Quantity of epiwafers w which begin assembly operations at assembly plant a using assembly line l during period t.
	Inventory at the end of period t of nearly finished epiwafer w awaiting assembly operations at assembly plant a.
	Quantity of shipments of epiwafer w leaving assembly plant a during period t destined for demand center h.
	Inventory at the end of period t of finished epiwafer w at demand center h.
	Quantity of epiwafer shipments leaving demand center h during period t to satisfy customer demand d.
	Quantity of customer demand d which is backordered at the end of period t

Objective function coefficients

Table

	Manufacturing cost for stage-one manufacturing of one piece of epiwafer w incurred during period t at fab location f.
	Transportation cost per piece of epiwafer w leaving fab location f during period t destined for assembly plant a.
	Inventory holding cost per piece of nearly finished epiwafer w in period t awaiting assembly at assembly plant a.
	Cost of processing one piece of epiwafer w on workstation s at assembly plant a during period t.
	Transportation cost per piece of epiwafer w leaving assembly plant a during period t destined for demand center h.
	Inventory holding cost per piece of finished epiwafer w in period t at demand center h.
	Cost per piece backordered of epiwafer requested by customer demand d in period t.

Objective function(1)

Constraints(2) (3) (4) (5) (6) (7) (8) (9) (10)

The objective function (1) minimizes total supply chain costs, including production starts, interplant shipments, inventory holding, and customer demand’s backorders. These costs are calculated in a straightforward manner except the production costs which must account for assembly processes requiring epiwafers to be processed on specific workstations (depending on epiwafer size or die size) and yield losses occur with different rates at workstations along different assembly lines. Constraint (2) indicates that all scheduled receipts of in-process epiwafers will be shipped to assembly plants immediately after their first manufacturing stage has completed. Constraint (3) is similar to constraint (2) but includes additional quantities for interplant shipments, which are the result of new fab starts accounting for cycle times and yields. Constraint (4) represents restrictions on fab capacity which limits fab start quantities in each planning period. Constraint (5) of the LP model represents the inventory of nearly finished epiwafers balanced at an assembly plant through periods in the planning horizon, ensuring that the inventory at the end of one period is the inventory at the end of the previous period plus shipments arriving from fabs and minus the quantities which begin assembly processing. Upon arriving at an assembly plant, epiwafers can either enter one or more assembly lines in to immediately begin their second manufacturing stage, or become inventory waiting to enter assembly lines. Epiwafers can enter an assembly line only when every workstation in that assembly line has available capacity – constraint (6) represents this governance of workstation capacity at each assembly plant. Constraint (7) ensures that finished epiwafers (i.e. end products) are transferred from assembly plants to demand centers while accounting for both cycle times and yields. Constraint (8) is an inventory balance equation for each demand center, ensuring that the inventory at the end of one period is the inventory at the end of the previous period plus shipments arriving from assembly plants and minus shipments made to customers. Constraint (9) is a backorder conservation equation to ensure that any unsatisfied demand is backordered to the next period. Constraint (10) requires that all decision variables be non-negative.

3. Enhancing mathematical programming models to account for changing priorities

Using the LP model presented in Section 2.2 as a vehicle (we will refer to that model simply as the “original” LP model hereafter), we present a generic procedure for enhancing an existing mathematical programming model, so that the enhanced model can account for demand priorities increasing as a function of delivery date. As will be seen shortly, this procedure is highly adaptable that it should also work in those situations with moderate modifications.

Assume that there are actually two types of demands considered by the LP model – demands which are specified with a single delivery period/priority combination (type-1) and demands which are specified with N (N  >  1) delivery period/priority combinations (type-2). Using N  =  3 as an example, suppose the priority of a type-2 demand with a quantity of 10 K epiwafers is 5 (low priority) if the demand is supplied by its preferred delivery date of 15 October; but if the demand is not delivered by 15 November, its priority would rise in importance to 3 (medium priority); and if the demand is still not delivered by 15 December, its priority would rise again to 1 (high priority). Consistent with this example, we assume that the priorities are monotonically non-decreasing in importance as a function of increasingly later delivery dates. In such a situation, firms usually consider only a single priority associated with each demand to reduce decision complexity. Thus, they would normally pick the first period/priority combination and ignore the subsequent change(s) in priority. We make this assumption primarily for notational convenience in explaining our method. The general approach of our method would still work – with modifications – if this assumption were violated.

The procedure to enhance the original LP model consists of five steps. In essence, these steps transform the problem from its original “multiple period/priority combinations per customer demand” representation to a traditional “single period/priority combination per customer demand” representation. The transformation is achieved by replicating every type-2 demand (each specified with multiple delivery period/priority combinations) and associating each replicated demand with just one of that type-2 demand’s delivery period/priority combinations. So doing allows the LP solver algorithm to be able to evaluate all the delivery periods and their associated priorities of a type-2 demand and determine the best timing to fulfill it. Using the example in the previous paragraph, the procedure transforms the type-2 demand of 10 K pieces of epiwafers with priorities specified on 15 October, 15 November, and 15 December into three demands each asking for 10 K pieces where one has a due date of 15 October and priority 5, another a due date of 15 November and priority 3, and the third 10 K piece demand a due date of 15 December and priority 1 (Table 2). Observe that the first of the post-transformation demands (15 Oct/5) already existed in the original model due to our assumption of the business using only the first period/priority combination and ignoring the other two changing priorities. Thus, only two of those post-transformation demands resulting from changing priorities are new (15 Nov/3 and 15 Dec/1). Consequently, we refer to those new transformed demands (15 Nov/3 and 15 Dec/1) as replicated, the 15 Oct/5 demand as the original truncated type-2 demand, and all three demands (replicated + original truncated type-2) as the transformed demand.

Table 2. Transforming the problem from its original “multiple period/priority combinations per customer demand” representation to a traditional “single period/priority combination per customer demand” representation.

	Before transformation	After transformation
Demand qty.	10 K	10 K	10 K	10 K
Delivery period/priority	15 Oct/5	15 Oct/5	15 Nov/3	15 Dec/1
	15 Nov/3
	15 Dec/1

To accomplish the transformation, we keep track of the fulfillment and backorder status of the replicated demands (e.g. the latter two single period/priority demands under “after transformation” in Table 2) through planning periods. We use the LED model example to demonstrate how this can be done. Specifically, the procedure will introduce new decision variables and constraints to govern replicated demands so that their fulfillment and backorders mimic the original type-2 demands. The new decision variables require additional backorder penalties to be added to the objective function. However, the procedure retains the original model as is. That is, there is no need to change the existing model, except that we add decision variables and constraints to model the changing demand priorities. As will be seen shortly, all the required changes occur at the end of the LED supply chain where demands are being fulfilled, and it will only take a moderate amount of effort to implement this procedure.

We use the following new indices and sets to describe the procedure.

Indices

Table

δ	Type-2 demand record.
ri(δ)	The transformed demand record created from type-2 demand δ for the period/priority combination

Sets

Table

	All type-1 demands
	All type-2 demands
	New (single period/priority) demands to be planned by the enhanced LP model, created by replicating the demands in

3.1. Decision variables

Two new variables are defined for enhancing the original LP model. Let be the quantity of epiwafer shipments leaving demand center h during period t to satisfy customer demand r_i(δ). Observe that is an alternative notation for the shipping variable in the original LP model, , where d is the original truncated type-2 demand r₁(δ). Also, observe that for all i ≥ 2, is not a “real” shipment but only treated as a shipment for modeling purposes. After the model has been solved, these “dummy” shipments should be discarded and not be reported to users of the model; the shipments reported to users will be those resulting from the original customer shipping variables, . Furthermore, let be the quantity of backorders at the end of period t for transformed customer demand r_i(δ). Similar to , observe that is an alternative notation for the backorder variable in the original LP model, , where d is the original truncated type-2 demand r₁(δ).

3.2. Objective function coefficients

Let be the additional backorder penalty per piece of epiwafer for the i^th (i ≥ 2) delivery period/priority combination of type-2 demand δ in period t. For example, is the additional penalty which will incur for every piece of epiwafer backordered during the time region in which the second priority of δ is in effect.

3.3. Procedure for enhancing the original LP model to accommodate changing demand priorities

• Step 1: Replicate every demand in to create

Suppose demand has N(δ) delivery period/priority combinations such that priority is a non-decreasing function of the delivery period. Create a new demand record r_i(δ) by assigning the quantity of δ and its period/priority combination to , for all 2 ≤ i ≤ N(δ). Place these new demands in .

• Step 2: Add replicated demands to the enhanced LP model.

In addition to those demands already considered by the original LP model, that is, demands in and those r₁(δ) demands (), the enhanced LP model must also consider demands in .

• Step 3: Add backorder constraints for changing demand priorities.

We introduce additional decision variables ( and ), constraints, and backorder penalties (using ) to account for the consideration of multiple period/priority combinations of demands in . Constraint (9) of Section 2.2 governs the backorder level of unsatisfied demands in the original LP model; therefore, a similar backorder tracking constraint must be added for the replicated demands in . This results in constraint (9-1) to be added to the original LP model.(9-1)

• Step 4: Add shipping constraints for changing demand priorities.

We introduce another group of constraints to the original LP model to further govern the fulfillment of the demands in .(11)

Constraints (9-1) and (11) are the only extra constraints which the original LP model of Section 2.2 would need to solve the problem. To see why, first of all, observe the following mathematical relationship which applies to any transformed demand r_i(δ).(12)

Equation (12(12) ) is obtained via the non-negativity constraint (10) applied to and by recursively substituting the backorder variable which appears on the right-hand side of the equality sign of constraint (9-1) with the calculation of its backorder quantity when placed into the left-hand side of the equality sign of constraint (9-1). That is,

Equation (12(12) ) ensures that , that is, on a cumulative basis, the total shipping quantity cannot be more than the total demand quantity . In other words, constraints (9) and (10) of the original LP model and the new backorder constraint (9-1) prevent any shipments occurring which are earlier than demanded. Equation (12(12) ) is not added explicitly to the model; rather, we use Equation (12(12) ) only to illustrate how the other constraints prevent shipments from occurring earlier than demanded.

Constraint (11) governs customer shipments further to ensure that any replicated demand r_i(δ) (i ≥ 2) created by step 2 cannot receive cumulative shipments which are more than the cumulative shipments delivered to fulfill the original truncated type-2 demand r₁(δ) (. In the enhanced model, only demand r₁(δ) will receive (real) shipments with finished epiwafers supplied via interplant shipments (constraint (8)). Consequently, we want shipments made to satisfy equally applicable to shipments made to fulfill every replicated demand r_i(δ), i ≥ 2, and constraint (11) ensures that.

When shipments being delivered to meet customer demand are placed under the above governance, constraints (9) and (9-1) will be able to keep track of any type-2 demand quantity backordered at the new priorities for the regions in time when those priorities become in effect. Take the type-2 demand of Table 2 for example. Denoting that type-2 demand as , there would be three single delivery period/priority demands transformed from after step 1: r₁(δ), r₂(δ), and r₃(δ), with r₁(δ) being the original truncated type-2 demand considered by the original LP model. Together, these transformed demands’ due dates would divide the original LP model’s planning horizon into regions in which a different combination of backorder variables is in effect (Table 3). For example, is the backorder variable in the original LP model which keeps track of the demand quantity backordered for at priority 5 (due to demand r₁(δ)) in the time region which begins on 15 October and continues through the rest of the planning horizon; and is a new backorder variable which keeps track of the quantity backordered for δ at priority 3 (due to demand r₂(δ)) in the time region which begins on 15 November and continues through the rest of the planning horizon. So if the first (real) shipment delivered to fulfill δ is delayed until, say, 20 November, will be 10 K starting on 15 October and both and will be 10 K starting on 15 November. Consequently,will be the daily backorder penalty incurred from 15 October to 14 November inclusive, and will be the daily backorder penalty incurred from 15 November to 19 November inclusive.

Table 3. Backorder time regions and applicable penalties for the example of Table 2.

Original type-2 demand	δ with three delivery period/priority combinations: 15 Oct/5, 15 Nov/3, and 15 Dec/1
Transformed demands	r1(δ) due 15 Oct/5, r2(δ) due 15 Nov/3, and r3(δ) due 15 Dec/1
Backorder time region	First day to 14 Oct	15 Oct to 14 Nov	15 Nov to 14 Dec	15 Dec to last day
Effective backorder variables	None		,	, ,
Total backorder penalty	0

Finally, we modify the objective function (1) of the original LP model to account for additional backorder penalties incurred as a result of changing demand priorities.

• Step 5: Add additional backorder penalties to the objective function.

The original objective function (1) considered all relevant costs and penalties based on our assumption that only the first delivery period/priority combination is considered. We need to incorporate the additional backorder penalties that account for the demand priorities increasing over time. The objective function for the enhanced model only differs from the original objective function (1) by adding to it the additional backorder penalties as follows.(1′)

Therefore, the enhanced LP model would consist of Equations (1′(9-1) ), (2(2) ) through (10), (9-1), and (11) with Equation (1′(9-1) ) serving as the model’s objective function and the rest of the equations serving as the model’s constraints.

In practice, demand priorities are often associated with backorder penalties such that the more important the priority, the heavier the associated backorder penalty. This means for , is smaller than , for all 2 ≤ i ≤ N(δ). With such relationships, we suggest using the following equation to create for all replicated demands r_i(δ),2 ≤ i ≤ N(δ):(13)

The above equation requires that the total of plus all additional backorder penalties be equal to . This ensures that once a shipment is delayed to the time at which the demand priority takes effect, the enhanced model will apply the backorder penalty, thus behaving very much like the original model in making crucial resource allocation decisions (assuming that the original model would somehow use the priority as the type-2 demand’s priority when the delivery date is within the time region where the priority applies).

Continuing the above example of Table 2 where the first shipment is delayed until 20 November, we set to be equal to so that the total daily backorder penalty incurred starting 15 November (the date on which the second priority starts taking effect) would match the original backorder penalty for the second priority. Similarly, we use Equation (13(13) ) to set as follows.

The above would result in the total daily backorder penalty incurred starting 15 December (the date on which the third priority starts taking effect) would match the original backorder penalty for the third priority.

4. Numerical validation

The proposed method is validated using data modified from the production data of a major manufacturer of LED epiwafers in Taiwan. The modification was done to extract a representative subset of data and adjusted to prevent leakage of confidential information, while retaining the salient characteristics necessary to validate our method. The manufacturer did not have all of the objective function data (e.g. backorder penalties), so we created some of this data arbitrarily. The modified supply chain consists of two four-inch epiwafer fabs and one six-inch epiwafer fab, one assembly plant, and one demand center, making six epiwafers with various characteristics (Table 4) to meet customer demand. The assembly plant houses appropriate workstations for processing these epiwafers (as reviewed in Section 2.1, most assembly workstations have a specific epiwafer-size or die-size processing limitation). Among the six epiwafers, W2 is the most expensive and W1 is the least expensive product to manufacture, respectively. The cost for making the same product can vary slightly depending upon the different workstations used for the cut and probe processes. As illustrated in Table 5, there are four assembly lines for processing four-inch epiwafers on which medium-size dies are manufactured. These assembly lines differ in which cut station (LBR-4 or SD-4) and which probe station (MCD or MW) are used to perform the corresponding process. For example, if MCD is used to process W6, the unit processing cost is $32.50 (USD); on the other hand, the unit processing cost is $39.00 if MW is used.

Table 4. Product characteristics influencing workstation selection for assembly processes.

Epiwafer	W1	W2	W3	W4	W5	W6
Epiwafer diameter (inches)	4	6	6	4	4	4
Die size	medium	large	large	medium	large	medium
Unit production cost (USD)	200 ~ 208	1000 ~ 1012	788 ~ 798	390 ~ 401	675 ~ 694	513 ~ 528

Table 5. Assembly lines and their six workstations for processing four-inch epiwafers on which medium-size dies are fabricated.

Assembly line	Grind	Cut	Probe	AOI	Sort	PI
1	G-4	LBR-4	MCD	AOI-M	S-4	PI-M
2	G-4	LBR-4	MW	AOI-M	S-4	PI-M
3	G-4	SD-4	MCD	AOI-M	S-4	PI-M
4	G-4	SD-4	MW	AOI-M	S-4	PI-M

There are a total of 12 monthly periods which constitute a one-year planning horizon. Every demand has two period/priority combinations (that is, all of the demands are type-2). The first combination contains the demand’s request period which is when the customer wishes to receive the requested product. The second (later) combination contains the demand’s commit period which is when the product needs to be delivered to the waiting customer as committed by the LED firm. Therefore, satisfying demands by their commit periods is more important than satisfying them by their request periods. The difference between the request period and the commit period ranges from one to four periods, and Table 6 shows the percentage of demands having each difference. For instance, 39.4% of the demands have a commit period which is one period after the request period.

Table 6. Percentage frequency of demands for each difference between the request and the commit periods.

Difference in delivery periods	1	2	3	4
Percentage	39.4%	24.6%	18.3%	17.7%

The experiments were conducted in an environment in which the monthly capacity for probe and PI is roughly 80% of what is actually needed (on a monthly average basis). Therefore, probe and PI are the bottleneck processes, meaning that the workstations for these two processes are scarce resources and how they are allocated dictates the performance of the supply chain. All of the late deliveries of demands are backordered rather than lost. The (unit) backorder cost for deliveries missing the commit period is set to be twice the unit price of the demand’s requesting product. For example, if a type-2 demand δ is asking for 100 pieces of epiwafer W1 at a unit price of $250, then using Equation (13(13) ), the demand’s would equal $500. On the other hand, the backorder cost for deliveries missing the request period of δ (i.e. ) varies.

The model was implemented using IBM^® ILOG^® OPL 6.0 and solved using CPLEX^® 9.0. All of the computer runs were done on a personal computer equipped with an Intel^® Xeon^® CPU (3.60 GHz) and 4 GB of RAM. Figure 2 shows the total backorder quantity (that is, backorders for all requested epiwafers) through the planning horizon obtained using the previous method (Section 2.2) and the proposed method (Section 3). The blue-circled line and the red-squared line of Figure 2(a) represent the optimal backorders against the commit period resulting from using the previous method (that is, ) with only the first (request) or the second (commit) period/priority combination as the sole period/priority combination of the model, respectively. We refer to the previous method as driving to either the request period (blue circles) or the commit period (red squares). The green-triangled line of Figure 2(a) shows the backorders against the commit period in the optimal solution resulting from using the proposed method (that is, Analogously, we refer to the proposed method as driving to both the commit period and the request period since the proposed method considers the periods and priorities of both combinations. As anticipated and illustrated in Figure 2(a), because the proposed method drives to both periods, it results in fewer backorders against the committed demand than the previous method which drives only to the request period (thus completely ignoring the commit periods), and more backorders against the committed demand than the previous method which drives only to the commit period (thus completely ignoring the request periods).

Figure 2. (a) Backorders against committed demand, (b) Backorders against requested demand (the ratio of to is 2 to 1)

Conversely, in Figure 2(b) which shows backorders against the requested demand, the proposed method results in fewer backorders () than the previous method which drives only to the commit period, and more backorders than the previous method which drives only to the request period. If management cares only about the performance versus the commit or the request period, then using the previous method with only a single period/priority combination would be fine. However, if management cares about the performance vs. both delivery periods, then the proposed method may yield a preferable result. Essentially, the results of the proposed method represent a trade-off between meeting the request period and the commit period. This trade-off can be controlled through the ratio of the backorder cost per period of not satisfying the demand by its request period () to the additional backorder cost per period of not satisfying the same demand by its commit period (). In the case of the data used to create Figure 2(a) and (b), this ratio is 2 to 1. As an example, if backorders against the request period () are penalized with a cost per period () of 100, then the backorders against the commit period () would be penalized at an additional cost per period () of 50.

Figures 3(a) and (b) illustrate the impact of changing the ratio to 1 to 19, heavily emphasizing performance against the commit period for the proposed method. In this scenario, the unit backorder cost for deliveries missing the request period is significantly smaller than the unit production cost of the demand’s requesting product, making these backorder costs inappropriate to be used by the previous method when it drives to the request period. Consequently, the backorder costs for deliveries missing the commit period were used by the previous method to drive to the request period or the commit period. The results in Figure 3(a) indicate that the performance of the proposed method (green triangles) is nearly as good against the commit period as the previous method when driving to the commit period (red squares). In fact, the two curves overlap so much as to be nearly indistinguishable. At the same time, Figure 3(b) indicates that the proposed method results in significantly fewer backorders against the request period (for the early time periods) than the previous method when driving to the commit period. We might summarize this as the proposed method performing better than the previous method (red squares) when meeting the commit periods are paramount and meeting the request periods is less important but still significant.

Figure 3. (a) Backorders against committed demand, (b) Backorders against requested demand (the ratio of to is 1 to 19)

Figures 4(a) and (b) illustrate the impact of changing the ratio to 19 to 1, heavily emphasizing performance against the request period for the proposed method. The results in Figure 4(b) indicate that the performance of the proposed method (green triangles) is nearly as good against the request period as the previous method when driving to the request period (blue circles). Again, the two curves overlap so much as to be nearly indistinguishable. At the same time, Figure 4(a) indicates that the proposed method results in fewer backorders against the committed demand than the previous method when driving to the request period for nearly the entire planning horizon. Once again, the proposed method outperformed the previous method in this scenario.

Figure 4. (a) Backorders against committed demand, (b) Backorders against requested demand (the ratio of to is 19 to 1)

5. Conclusions

This paper describes how to modify mathematical programming formulations to reflect the dynamic relative importance of demands, namely the priorities of demands – relative to other objectives – increasing as a function of the dates on which the demands are satisfied. The proposed solution is straightforward to implement and applies in a wide variety of industries where mathematical programming models are used in resource allocation decisions and where demand priorities can increase as a function of delivery date. Application areas include health care (e.g. treatment becomes more essential as time passes), project management (e.g. some target dates are more important than others), and manufacturing/distribution (various scenarios). Off-the-shelf commercial solvers, such as CPLEX and Gurobi Optimizer, will handle the LP and MIP formulation modifications without difficulty when demand priorities change for a moderate number of discrete time periods. When demand priorities change continuously or for many discrete time periods, solver algorithms may need to be extended to exploit the problem structure (and parallelization opportunities) to solve the resulting large-scale problems fast enough. When mathematical programming formulations are non-linear or stochastic, additional research may be necessary to obtain good and timely solutions. Another opportunity for further research is the exploration of applications in areas such as finance and consumer services. Finally, we assume that demand priorities are monotonically non-decreasing functions of delivery date; further research would be needed to model situations where demand priorities decrease over time.

Notes on contributors

R. John Milne received his BS and MEng degrees in operations research from Cornell University and his PhD in decision sciences and engineering systems from Rensselaer Polytechnic Institute. His 26-year career at IBM focused on the application of operations research to decision problems in supply chain management. This work was recognized by the Institute for Operations Research and the Management Sciences with the Franz Edelman Finalist Award for Achievement in Operations Research and the Management Sciences and the Daniel H. Wagner Prize for Excellence in Operations Research Practice. Presently, he is the Neil ′64 and Karen Bonke Assistant Professor in Engineering Management at Clarkson University. His research focuses on the application of operations research to supply chain management problems. He teaches courses in operations research, operations and supply chain management, and advises engineering and management students on their senior capstone design projects. He is the inventor or co-inventor of over 40 US patents.

Chi-Tai Wang received his PhD degree in industrial & operations engineering from University of Michigan at Ann Arbor. Prior to having a career in academia, he worked at IBM for 9 years developing supply chain management systems to support decision-makings in the company’s semiconductor manufacturing business unit. Currently, he is an assistant professor at Institute of Industrial Management, National Central University in Taiwan. He teaches graduate-level courses in operations research, large scale optimization, and supply chain management computer systems. He has been pursuing research in technology and supply chain management of high-tech manufacturing industries.

Acknowledgment

This study was supported in part by the National Science Council of Taiwan under Grant NSC 102 - 2410 - H - 008 - 058.