SOGOBO_2012_v35n3_240.pdf648.9KB

1. Introduction

 This paper considers production planning in the context of hybrid flow shops. The flow shop has serial stages where each stage consists of identical parallel machines. Products can be processed at any one of the parallel machines at a stage in the hybrid flow shop. Also a product may have reentrant operations which require revisits of some stages several times. This may cause the congestion of work in process (WIP) or equipment idleness. In the real world, a configuration of the reentrant hybrid flow shop may be found in electronics industry such as printed circuit board (PCB), semiconductor wafer fabrication and thin film transistor and liquid crystal display (TFT-LCD) manufacturing [3, 12, 15]. In addition, TFT process in TFT-LCD manufacturing are quite similar to wafer fabrication in semiconductor manufacturing [10, 12, 17, 24]. The reentrant operations are required when glasses or wafers undergo multiple layer processes of photolithography in TFT or fabrication line. The progress of each layer has the steps to be consisted of photolithography, etching, thin filming, diffusion, and so on. The photolithography has usually the serial processes, which is coating, stripping, exposing, and developing [10].

 The reentrant hybrid flow shop planning has been researched mostly in environments of semiconductor wafer fabrication and TFT-LCD manufacturing. There are a number of studies of dispatching rules for operational control on wafer fabrication in the literature (see Sarin et al. [22], for detail survey). Spearman et al. [23] suggested the CONWIP method which is a controlling WIP policy to be simultaneously managed both WIP and throughput, and they compared to pull system in the hybrid flow shop environment. For reentrant hybrid flow shop problem in semiconductor wafer fabrication, Ehteshami et al. [4] studied controlling the WIP to reduce the cycle time, and Lee et al. [14] studied an input policy and WIP control policy considering dynamic cycle time. Lin and Lee [16] proposed a queueing network-based algorithm estimating a WIP level to achieve target throughput rate with a reasonable cycle. Rose [20, 21] proposed a simulation model to estimate of the cycle time distribution of semiconductor wafer factories. Robinson and Chance [19] suggested a methodology for wafer fab cycle time management using the actual manufacturing execution system (MES). The mean value analysis based an approximation method is investigated by Park et al. [18]. The approximation method is simple rule for estimating the mean cycle of each class of jobs, the mean queue length of buffer and the throughput of reentrant line with batch machine and multi-class jobs.

For bottleneck stage on reentrant hybrid flow shop, Kim et al. [8, 9] and Yea [25] suggested how to determine the target WIP level using the fab balanced in semiconductor wafer fabrication. Also they suggested the mixed integer programming model and the heuristic methods for shift scheduling to achieve the production target, which are stepper allocation to reduce the difference between actual WIP level and target WIP level. Lee et al. [13] suggested the dispatching rules to drive the target production and the target WIP for the input and bottleneck scheduling rules for production and cycle time reduction in semiconductor fabrication line. Lee and Kim [11] suggested the balance control policy for bottleneck scheduling and operation management in the fabrication line. There showed how to determine the proper WIP level, and measure the balance using the proper WIP level. There also proposed the optimization model applying the balance measurement for production and cycle time reduction. Lee and Lee [12] defined the managing point as bottleneck process step and suggested three mathematical models in TFT-LCD fabrication manufacturing. The models are the throughput driven push model, the balance driven push-pull model using the WIP controlling policy, and the target driven pull model using incapacitated production target projection applying the cycle time required. Kang and Lee [7] suggested the due date based optimization models for make-to-order semiconductor industry, that are the target control model, the movement control model and the WIP control model. Lee et al. [10] suggested the target balance (TB) optimization models using production target, due-date, and WIP in semiconductor fabrications. Also their models were tested on multi-stage with bottleneck processes in TFT-LCD fabrication. 

Gupta et al. [5] surveyed current researches for operational planning and control problem in semiconductor wafer produc-tion. There were various aspects that the productivity is related throughput, utilization, workload balance and so on, and the customer satisfaction is related cycle time, demand, due date and so on. However most of the existing literature has investigated a single objective function or multi-objective functions that are not directly pursued but implicitly for the hybrid flow shop planning problem. This paper tries to explicitly deal the bi-objective function that are, productivity and customer satisfaction. We propose heuristic methods based on mathematical model to maximize throughput for productivity and to minimize delayed customer demand for customer satisfaction. 

This paper is organized as follow : in section 2, we propose detailed problem description. Section 3 presents the procedure of the proposed heuristic methods. The comparison with TB model [10] for simulated data is shown in section 4. Section 5 concludes the paper with possible extension in the future. 

2. Problem Description

 This paper considers the multi-stages reentrant hybrid flow shop problem. The flow shop has serial stages, where each stage consists of identical parallel machines. Each product can visit several stages following the given product route in the hybrid flow shop. Moreover, products can revisit the some stages several times, this is a reentrant operation. We consider the stages as bottleneck processes that must be managed. Thus, this paper is focused on the operational planning for processing steps of the bottleneck stages as managing points among entire processing steps [3, 12]. It is assumed that the processing or staying on non-bottleneck stages bet-ween bottleneck stages takes one period time. Also the machines at each stage are assumed to be aggregated and processing times are given.

 To describe the problem formally, a linear programming (LP) model with bi-objective is presented. Note that our model is a modified formulation of Kang and Lee [7], Lee et al. [10] and Lee and Lee [12] where they proposed the hybrid flow shop with bottleneck processes. Consider the following notations:

i             index for products, i = 1, …, n
j             index for operations of bottleneck stages in entire process
l             index for bottleneck stages, l = 1, …, L
t,t'          index for planning time periods, t,t' = 1, …, T
D_i,t         demand quantity of product i during time t
N_i           number of operations in bottleneck stages required for product i,  i = 1, …, n
p_i,j          processing time of operation j of product i, i = 1, …, n and  j = 1, …, N_i 
S_i,j           stage required for operation j of product i,  i = 1, …, n and  j = 1, …, N_i 
WT_l,t       total working time at stage  during time
IWIP_i.j    initial WIP amount waiting to process operation j of product i
INPUT_i  raw material amount of product

Decision variables
X_i,j,l,t      production amount of operation  of product  to be processed at stage  during time
WIP_i,j,t   WIP amount waiting to process operation  of product  during time
V_i,t         delayed customer demand of product  during time
Q_i,t         throughput of product  during time  

Objective functions
 

 Subject to

 The bi-objective function is composed of simultaneously minimizing the sum of delayed customer demand in (1) and maximizing the sum of throughput in (2), where the throughput is specified in constraint (10), and the delayed customer demand is specified in constraint (11). At the end of each time period, the WIP balance equations are shown (3) through (6). Constraint (7) shows that the production amount cannot exceed the residing WIP on the first time period. Constraint (8) shows that the production amount can not exceed the residing WIP from second time period. Constraint (9) shows that the total working time of stage with aggregation machine is restricted by the available working time. Constraints (10) and (11) are the constraint of the throughput and the delayed customer demand, respec-tively. The throughput is the output at the last operation of each product. The delayed customer demand is the difference between cumulative sum of the throughput and demand values from the first time period to the current time period. Constraint (12) is the non-negativity restrictions of the variables.

 Multi-objectives problems are commonly related to the Pareto optimal solution. The Pareto optimal solution is defined as follows; a solution x* is Pareto optimal if no objec-tive function can be improved by degrading at least one other objective functions [1]. As shown in <Figure 1>, a feasible solution x₂ is dominated by a feasible solution x₁ for bi-objective functions f₁ and f₂ . But the x₁  is non-dominated by other feasible solutions for anyone, and then the x₁ is Pareto optimal solution. In general, it is difficult to find all possible the Pareto optimal solutions for multi-objectives problems, this paper focuses on the method using the goal programming which is efficient and fast algorithm for multi- objectives problem.

<Figure 1> Example of Bi-Objective Problem

3. Solution Approach

In this section, we propose preemptive goal programming [2, 6] based algorithms. In preemptive goal programming, we define priority of objective function. In the first step, we optimize the problem based on the first objective. In the second step, we consider the second objective function such that the first optimal objective function value is not violated. The procedure continues until we consider all the objective functions. In this paper, we propose two heuristics. In heuristic (1), the first priority objective is the delayed customer demand and the second priority objective is the throughput. For the heuristic (2), we consider the throughput as the first priority objective and the delayed customer demand as the second priority objective. 

 Let Z^de  and Z^th  be the objective function of the delayed customer demand and the throughput, respectively. Also let z^de  and z^th  be the objective value of the delayed customer demand and the throughput, respectively. Then, structure of heuristic (1) is as following:

 Heuristic (1)
  Phase I. Optimize to minimize Z^de  in LP as following:

  PhaseⅡ. Add constraint (13) for z^de  and optimize to maxi-mize Z^th  in LP as following:

 where constraint (13) shows that the delayed customer demand is restricted to z^de  in phase I of heuristic (1).

Structure of heuristic (2) is as following:
 Heuristic (2)
  Phase I. Optimize to maximize Z^th  in LP as following:
 

 PhaseⅡ. Add constraint (14) for z^th  and optimize to mini-mize Z^de  in LP as following:

where constraint (14) shows that the throughput is restricted to z^th  in phase I of heuristic (2).
 

4. Experiments

This section describes the experiments that have been conducted to compare the results of the proposed algorithm and Lee et al. [10]’s TB models. The TB models use the incapacitated production target (IPT) which is the production target on each layer to be estimated using the product due date information, not considering the machine capacity. The TB-D model tries to minimize the difference between cumulative sum of the WIP and IPT from the last layer to current layer. The TB-R model tries to minimize the maximum value of TB, which is calculated from the cumulative sum of the WIP from the last layer to current layer divided by the cumulative sum of IPT from the last layer to current layer. 

 The solutions were found using CPLEX 11.0 with Microsoft visual C++ 2005 language. The tests are performed on a personal computer with Intel(R) Core(TM)2 Duo CPU E8500 @ 3.16GHz 3.17GHz and DDR2 3.25G RAM. In this experiment, we set test problems based on the problems of Lee et al. [10] as collected from the historical database. The TFT-LCD fabrication line consist of a number of serial stages, however, the bottleneck stages is assumed to be the deposition, the photo and the PR strips stages in every stages, where machine of each stage are aggregated machine.

 The TFT-LCD manufacturing is assumed that there is daily demand to produce 1500 glasses per day on average for a month, but test problems are formed a total of 60 periods for 10 days, each day is consisted of 6 periods, i.e. a planning decision time period is 4 hours. The number of product is 5 products, and the number of layer for each product is randomly generated in the range of discrete uniform distribution DU[3,5]. Each bottleneck stage has 5 deposition machines, 10 steppers as photo machines and 5 PR strip machines, where their manufacturing cycle times are randomly generated in the range of continuous uniform distribution U[5.64,10.36] hours. The processing time on aggregated machine to process each step depending on the layers for deposition and PR strip stages is randomly generated in the range of U[0.30,0.48] minutes. And the processing time on aggregated machine for photo stage is U[0.15,0.24] minutes.

<Table 1> The Result of the Delayed Customer Demand and the Throughput for Problems

 The period demand of a product is calculated from the daily demand divided by 6. It is assumed that input volume is the average period demand. The working time in each period is set 220 minutes for each machine with the exception of 20 minutes for equipment loss time, which are setup, inspection, maintenance, machine breakdown, etc. Initial WIP for each period is assumed using average target WIP divided 6. The average target WIP is calculated by modi-fying the method in Kim et al. [8] and Yea [25] as following:

{average target WIP}
  = (({average daily demand}/2)/4)×{cycle time}  (16) 

 We consider three different types of initial WIP: 1.0 times, 1.5 times and 2.0 times of average target WIP. Also, we consider three variations of daily demand: In the type 1, the daily demand for each product is 300. In the type 2, the daily demand is generated in the range of DU[240,360] for each product with 20% variation. In the type 3, the daily demand for each product is generated in the range of DU[120,480] with 60% variation.

For each case of the initial WIP and demand, 20 random problems are generated and tested. <Table 1> shows the result of average period values of the delayed customer demand (Z^de ) and the throughput (Z^th ) for problems, where TB-D and TB-R are the model of Lee et al. [10]’s TB models. It seems that the performance of heuristic (1) and heuristic (2) are different according to first priority objective. For the delayed customer demand, heuristic (1) is better than heuristic (2). For the throughput, heuristic (2) is better than heuristic (1). Also, the result of heuristic (1) and heuristic (2) are significantly better than TB models for every problem on the delayed customer demand. Also the result of heuristic (1), heuristic (2) and TB-R model are slightly better than TB-D model for the every problem on the throughput. In conclusion, the proposed algorithms are more effective in terms of customer satisfaction in addition to productivity. 

<Table 2> shows the computation time of algorithms for problems. It seems that the proposed algorithms are needed a slightly less computational time than the TB models. 

<Table 2> The Average Computational Time for Problems(sec.)

5. Conclusion

 The performance of reentrant hybrid flow shop is closely considered several objectives related to productivity and customer satisfaction in real world situations. We propose preemptive goal programming based algorithms. The proposed algorithms perform better than existing TB models managing WIP based on due date in terms of the throughput and the delayed customer demand.

 This research can be extended to multi-objective function problems for real world scenarios.