Research Article
Mathematical Modeling of the IC Final Testing Order Selection Problem
Department of Business Administration, Ching Yun University, No. 229, Chien Hsin Road, Jung-Li 320, Taiwan, R.O.C.
Semiconductor manufacturing process consists of four major process stages: wafer fabrication, wafer probe, IC package and IC final test. The semiconductor manufacturing process is as shown in Fig. 1. Based on the appearance of products, the first two stages, which process on wafers, are referred to as front-end and the last two stages, which process on ICs, are referred to as back-end. Both wafer probe and IC final test are testing activities on products and the differences between the two are that the product appearances and the testing objectives are different. For wafer probing, the testing target is the dies on a wafer and the defective dies are inked so that they will not be further assembled and the manufacturing cost can be reduced as a result. On the other hand, IC final testing is to ensure the functionality of IC after the assembly process. Packaged ICs may be defective due to an improper assembly process, for example, an uneven lead frame that makes wire bonding incorrectly connects it with the die. In addition, final IC products may be used in a variety of environments and IC final test is to ensure that these ICs can meet the predetermined functions and criteria (such as high temperature) so that the required quality of final IC products can be met.
Fig. 1: | Semiconductor manufacturing process (Chung et al., 2007) |
When a tester machine is available, an operator needs to verify the setting of the tester. The procedure of the setup is as follows:
• | Obtain the appropriate handler, hi-fix, change kit according the device type and package type of the IC product and bring them to the tester |
• | Connect the handler, hi-fix and change kit to the tester |
• | Bring the handler to the required temperature |
• | Download the required software |
In the IC final testing factory that we investigated in this study, they will receive many orders from different customers (i.e., the IC packaging factories). The information of each candidate order includes its device type, package type, lot size, unit testing time and the required test environment of the order. When processing two consecutive orders, a sequence dependent setup time may be incurred due to the different of their setup requirement. If the testing condition is the same one when testing two different orders consecutively on a tester, the operator only needs to download the required program and set the testing environment. However, if the testing condition is different, the operator needs to obtain the required hi-fix and change kit and connect it with the tester first and then the required program needs to be downloaded and the testing environment set. In fact, different orders usually require different testing criteria. Such a production characteristic leads to a production scheduling problem with sequence dependent setup time. That is, with a different processing sequence of orders, the required setup time may be different. An example is as shown in Table 1.
Additionally, the unit profit of each order may not equal since the depreciation of the required tooling (i.e., handler, hi-fix and change kit) and the hourly rate of the tester machine. The tester machines, used in the shop floor to perform testing operations in the IC final testing factory, are the most expensive machine and usually have a highest utilization rate. The production planning mechanism is executed every month to select orders from candidate orders. According to the fundamental concept of the Theory of Constraints (TOC) (Goldratt and Cox, 1992), the performance of a system is determined by the bottleneck resource in that system. Therefore, the aim of the production planning mechanism is deciding which orders should be accepted for maximizing the received profits.
From the open literature review, the authors found that most works on IC final testing factories are related to shop floor production management. Uzsoy et al. (1991) applied the decomposition method to divide the production system of a semiconductor test facility into a number of workstations and developed an algorithm to solve the scheduling problem in each workstation for minimizing number of tardy jobs.
Table 1: | An example of sequence dependent setup |
Ovacik and Uzsoy (1992, 1994, 1996) extending the study of Uzsoy et al. (1991), proposed shifting bottleneck algorithm, rolling horizon algorithms and decomposition method to solve such a problem, respectively. Perry and Uzsoy (1993) combined a decomposition method for the static problem with a discrete event driven rescheduling approach to minimize maximum lateness in the testing shop floor. Yoo and Martin-Vega (1997) applied a decomposition method incorporated with shifting bottleneck algorithm for minimizing the number of tardy jobs in semiconductor test facility. Pearn et al. (2002a, b) considered a parallel machine version of the scheduling problem of Uzsoy et al. (1991). They proposed a Mixed Integer Linear Programming (MILP) formulation and a modified saving algorithm to solve the problem, respectively. Lin et al. (2004) developed a Drum-Buffer-Rope (DBR) based dispatching rule to schedule the shop floor for minimizing the setup time and maximizing the committed volume performance. Lin et al. (2005) developed a Parameterized Dispatching Rule (PDR) using the response surface method for optimizing the desirability function that is the combination of priority of products, on-time delivery performance, processing time, setup time, waiting time and machine flexibility. Song et al. (2007) considered a similar problem that stated in Pearn et al. (2002a, b) and proposed an Ant Colony Optimization (ACO) method to minimize the machine conversion time, i.e., machine setup time. To the best knowledge of authors, there is no research that focuses on the profit maximization in the IC final test factory. Therefore, this study tackles an IC Final Test Order Selection Problem (ICFTOSP) under a single bottleneck resource environment. With the consideration of limited capacity of testers, price and delivery of orders and sequence dependence setup time, a Mixed Integer Linear Programming (MILP) model is proposed to achieve the objective of increasing a firm`s profit. A demonstrative is also given to illustrate the usability of the proposed model. In the last section, some concluding remarks are made.
NOTATIONS
Parameters
i | : | Index of candidate order, i = 0, 1, 2, ..., I, where 0 is a dummy order to represent the initial status of bottleneck resource (tester) at the beginning of the planning horizon |
ni | : | Lot size of order i |
pi | : | Unit processing time of order i |
pfi | : | Unit profit of order i |
sii | : | Setup time for changing setup from processing order i to order i` |
Q | : | A very large positive number |
C | : | Available capacity of bottleneck resource in planning horizon |
Decision variables
ti | : | Starting time of order i to be processed in planning horizon |
xi | : | If order i is selected to process in planning horizon, then xi = 1; otherwise, xi = 0 |
yi i` | : | Relative precedence variable of order i and order i`. If order i is processed before order i`, then yii` = 1; otherwise, yii` = 0 |
Zii` | : | Direct precedence variable of order i and order i`. If order I is processed directly before order i`, then zii` = 1; otherwise, zii` = 0 |
A MIXED INTEGER LINEAR PROGRAMMING FORMULATION
In an IC final testing factory, tester is the bottleneck resource and the objective function of the ICFTOSP is to maximize the system profit. In implementing the final testing task, the characteristic of sequence dependent setup time is present. The MILP model for the ICFTOSP can be represented by Eq. 1-15.
Objective function: The objective function tends to maximize the profit received in the planning horizon. It is the sum of the profit of the selected orders from the candidate orders.
(1) |
Machine capacity constraints: Constraint (2) ensures that the selected orders to process in planning horizon must not violate the available capacity of bottleneck resource. The total load in the planning horizon is calculated as the summing up the sum of the processing time of the selected orders and the sum of the setup time between orders.
(2) |
Processing precedence constraints: Constraints (3) and (4) ensure that the sequence between two orders must be hold (yii` = 1 or yi` i = 1) when order i (xii` = 1) and order i` are selected (xi` = xi` = 1) to process in planning horizon. Constraint (5), (6) and (7) describe the relationship between relative precedence variable yii` and decision variable xi. If both of order i and i` are not selected in planning horizon (xi = xi` = 0), then yii` and yi`i must be zero, respectively (constraint (5) is satisfied). If one of order i or i` is selected in planning horizon (xi = 1 or xi` = 1), then both of precedence variables yii` and yi`i must be zero, respectively (the value of yii` and yi`i is restricted to be zero by either constraint (6) or (7)). Constraint (8) describes the relationship between relative precedence variable and direct precedence variable. Order i could precede order i` directly (zii` = 1) only when precedence variable yii` = 1 and order i could not precede order i` directly (zii` = 0) only when precedence variable yii` = 0. Constraint (9) ensures that when n orders are selected to process in planning horizon, there must be (n-1) direct precedence variables with value of 1. Constraint (10) states the initial status at the beginning of the planning horizon. We note that the initial status is the required test environment of the latest process order in prior planning horizon.
(3) |
(4) |
(5) |
(6) |
(7) |
(8) |
(9) |
(10) |
Starting and finishing process time constraints: Constraint (11) ensures the starting time of order i must be zero (ti = 0) if order i is not selected (xi = 0). Constraint (12) ensures the starting time of order i` (ti`) to be processed must be greater than the finishing time of order i (ti + ni pi + sii`) if order i is scheduled prior to order i` (yii` = 1). Constraint (13) ensures that the starting time of order i` equals to the finishing time of order i (ti + ni pi + sii` = ti`) if order i and i` are the two consecutive orders (yii` = 1 and zii` = 1). Constraint (14) ensures that the finishing time of order i can not surplus the length of the planning horizon.
(11) |
(12) |
(13) |
(14) |
Decision variables
(15) |
(16) |
(17) |
(18) |
For an order selection problem with I orders, the MILP model contains I variables of xi, I variables of ti, I(I-1) variables of yii`, I(I-1) variables of zii`. In addition, there are a total of I(I-1) equations in constraint (2), I(I-1)/2 equations in constraint (3), (4), (5), (6) and (7) respectively, I(I-1) equations in constraint (8) and (9) respectively and I equations in constraint (10) and I equations in constraint (11) and I(I-1)/2 equations in constraint (12) and (13), respectively and I equations in constraint (14). Thus, the total number of variables is 2I2 and the total number of equations is (15/2)I2 - (9/2)I.
A simple example is presented in this section to explain the solving process and the application of the proposed model. Consider a production environment with one tester machine in bottleneck workstation. In the beginning of planning horizon, there have 15 candidate orders waiting for testing and the information of test type, processing time (min), lot size (die) and profit of each candidate order as shown in Table 2. The capacity limit of bottleneck resource is 120 min. When processing two consecutive orders, there may have setup time for preparing the testing environment in machine and the required setup time between different test types are shown in Table 3.
Table 2: | The required test type, process time, lot size and profit for the 15 candidate orders |
*Is an index to represent the required testing environment condition |
Table 3: | Setup time required for switching one test type to another in example |
Table 4 shows the feasible solution and solving time under different node limits. When the node limit is set to 1,000, a relatively good solution can be obtained in 2.7810 sec and the total profit is 267. Table 5 is the feasible solution under the node limit set as 1000.
Table 4: | Objective value and required solving time under different number of nodes limits |
Table 5: | MILP solution under the node limit set as 1000 |
The objective value and the required solving time, Node limit, integer feasible: Objective = 267, Solution time = 2.7810 sec, Iterations = 24,557, Nodes = 1,000. All other variable are zero |
The selected orders are No. 1, 2, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14 and 15 (x01 = x02 = x04 = x05 = x06 = x07 = x08 = x10 = x11 = x12 = x13 = x14 = x15 = 1) and processing sequences is No. 8, 7, 6, 10, 11, 12, 15, 13, 14, 2, 1, 5 and 4 (z0008 = z0807 = z0706 = z0610 = z1011 = z1112 = z1215 = z1513 = z1314 = z1402 = z0201 = z0105 = z0504 = 1) and the total profit is 267 and the total computational time for solving the example is 2.7810 sec.
After the depression of the semiconductor industry in 2000 to 2003, IC packaging and IC final testing companies, the back end of the semiconductor supply chain, have changed their capacity expansion strategy from follower strategy to lag strategy, in compared with wafer fabrication. Compared with the frond-end practitioners in the supply chain of semiconductor manufacturing, the capacity level of IC final testing companies is relatively lower than that of wafer fabrication and an appropriate selection of candidate orders for final testing is essential.
The IC final test order selection problem has the characteristics of different lot size, process time, order profit, sequence dependent setup time and limited capacity. Based on these, this research proposes a MILP model to solve the order selection problem. This study introduces a real-world example to describe the ICFTOSP and uses ILOG OPL 3.5 to construct the model. The results can be a reference for IC final testing companies for order selection.
To increase the applicability of this MILP, a best estimate search strategy incorporating a branch based on pseudo reduced costs rule was adopted to increase the solution efficiency and the numerical result showed that an acceptable solution can be obtained in a reasonable computational time.
The authors would like to thank the National Science Council, Taiwan, R.O.C., for support under contract No. NSC 96-2416-H-231-001-MY2.