Transcript Loading Balance in Foundry Fab

Scheduling for Dedicated Machine
Constraint Using Integer
Programming
Huy Nguyen Anh Pham, Arthur Shr, and Peter P. Chen
Louisiana State University, Baton Rouge, LA, U.S.A.
Alan Liu
National Chung Cheng University, Chia-Yi, Taiwan
Outline

Dedicated Machine Constraint in Semiconductor
Manufacturing

Related Work

Integer Programming Approach

Experiments

Conclusion
Outline

Dedicated Machine Constraint in Semiconductor
Manufacturing

Related Work

Integer Programming Approach

Experiments

Conclusion
Dedicated Machine Constraint in
Semiconductor Manufacturing

The operations of
semiconductor
manufacturing repeatedly
make an IC product layer
by layer.

The dedicated machine
constraint is in the
photolithography process
area
Photolithography Process

The most important process for the yield of IC
– “Blue Print” for each photo layer
– Alignment of layers

Photo machines could be used in different layers.

Different process time for photo each layer
Dedicated Photolithography
Machine Constraint
Dedicated Machine Constraint :
No constraint :
Wafer lots
Busy
idle
Machine X
Machine Y
Machine Z
Photolithography Stages
Machine A
Machine B
Machine C
Other Stages

With this constraint, the wafer lots dedicated to machine X need to wait
for machine X, even if there is no wafer lot waiting for machine Y.

Without this constraint, the wafer lots can be scheduled to A, B, or C.
Issues and Current Solutions
– Photo machines might become load unbalanced if
the wafers are dispatched randomly to the photo
machines at the first photo layer.
– Some photo machines will be “lost” for a while and
the others will be “run” with heavy load
– Switch from the highly congested machines to the
idle machines.
– Rely on experienced engineers to manually
handle alignment problems of the wafer lots
Outline

Dedicated Machine Constraint in Semiconductor
Manufacturing

Related Work

Integer Programming Approach

Experiments

Conclusion
Related Work

Kimms (1996) proposed a mixed-integer programming model for
optimally scheduling machines.

(Miwa, 2005) proposed a load balance allocation function between
machines and used this function for a dynamic programming method to
schedule them.
=> Their problems without dedicated machine constraint.

(Shr 2008a; 2008b) proposed a heuristic Load Balancing scheduling
method.
=> The approaches did not attempt to optimize the cost for the overall
productivity with the dedicated machine constraint.
Outline

Dedicated Machine Constraint in Semiconductor
Manufacturing

Related Work

Integer Programming Approach

Experiments

Conclusion
Modeling the Dedicated Machine
Constraint-RSEM

A Resource Schedule and Execution Matrix (RSEM):
Steps
j
1
2
3
4
5
6
7
8
9
Wafer lots i
W1
R3
W2
W3
W4
W5
R3
R3
R2
R4
R1
R3
R2
R2
R2
R4
R1
R1
10
Modeling the Dedicated Machine
Constraint-Breakdown (BD) Matrix

A Breakdown Matrix:
Steps
j
1
2
..
Machines k
R1
100
..
R2
467
..
R3
838
..
R4
100
..
Formulation of the Problem

Variables:
(1)
Xi,j,k is a binary variable.

The penalty cost for switching:
mi,j,k
ri, j seconds, if stepWi,j is assigned to machine k ,

si, j seconds, if stepWi,j is assigned to another machine.
ri , j  si,j
(2)
Formulation of the Problem – Cont’d

The production cost for wafer i at step j assigned to machine k:
(3)

Minimize the production cost of the assignments:
minimize
 X
i
j
i , j ,k
 Ci , j ,k 
k

Minimize the queue time for wafer lots waiting at machines



minimize    X i , j ,k 
j
k  i

The objective function:
minimize
f   X i , j ,k  Ci , j ,k 
i
j
k
(4)
2


    X i , j ,k 
j
k  i

(5)
2
(6)
Formulation of the Problem – Cont’d

Constraints:
– Wafer i at step Wi,j is assigned to exactly one machine:
(7)
– Assume that each wafer lot Wi has Pi photo steps. The
dedicated machine constraint for wafer i at step Wi, j :
for either k = 1, 2, …, or Q.
(8)
Formulation of the Problem – Cont’d
– Because of requirements for a canonical form of an IP
formulation, by using the Big M method Equation (8) is
transformed into:
  X i , j ,1  M  Yi ,1  M ,
 j
  X i , j , 2  M  Yi , 2  M ,
 j

..........


 X i , j ,Q  M  Yi ,Q  M ,
 j
 Yi ,k  1,
k
for Yi ,1 ,..., Yi ,Q  {0,1}, i
 1,.., N , j  1,.., M , k  1,.., Q.
(9)
Formulation of the Problem – Cont’d
Since the Big M method

The Integer Formulation:




minimize f    X i , j ,k  Ci , j ,k    Yi ,k      X i , j ,k 
i  j k
k

 j k  i
2
Subject to :
  X i , j ,1  M  Yi ,1  M ,
 j
  X i , j , 2  M  Yi , 2  M ,
 j

..........


 X i , j ,Q  M  Yi ,Q  M ,
 j
 X i, j ,k  1,  Yi,k  1,
k
k
for X i , j ,k , Yi ,1 ,..., Yi ,Q  {0,1}, i  1,.., N , j  1,.., M , k  1,.., Q.
(10)
Outline

Dedicated Machine Constraint in Semiconductor
Manufacturing

Related Work

Integer Programming Approach

Experiments

Conclusion
Experiments

100, 200, and 300 wafer lots with 10 steps are used.

The number of machines is set equal to 3.

BD[j, k] is randomly given in the range [0, 1000].

Each experiment uses 30 examples
Experiments – Cont’d
Experiment of 100 wafer lots, 10 steps and 3 machines.
Execution time in seconds
80
70
60
50
40
30
20
10
0
134
132
130
128
126
124
122
1 2 3 4 5 6 7 8 9 101112131415161718192021222324252627
Examples
• The average execution time: 127 seconds for each example.
• The average percentage cost saved: approximately 41.1%.
Execution time
Percentage
Percentage of the cost saved in seconds
Experiments – Cont’d
Experiment of 200 wafer lots, 10 steps and 3 machines.
Execution time in seconds
1230
1220
1210
1200
1190
1180
1170
1160
1150
1140
70
Percentage
60
50
40
30
20
10
0
1 2 3 4 5 6 7 8 9 101112131415161718192021222324252627
Examples
• The average execution time: 1,186.6 seconds for each example.
• The average percentage cost saved: approximately 37.9%.
Execution time
Percentage of the cost saved in seconds
Experiments – Cont’d
Experiment of 300 wafer lots, 10 steps and 3 machines.
Percentage
50
3000
40
2900
2800
30
2700
20
2600
10
2500
0
2400
1
2
3
4
5
6
7
8
9
10
11
12
Examples
• The average execution time: 2,781 seconds for each example.
• The average percentage cost saved: approximately 26.5%.
Execution time
Execution time in seconds
Percentage of the cost saved in seconds
Outline

Dedicated Machine Constraint in Semiconductor
Manufacturing

Related Work

Integer Programming Approach

Experiments

Conclusion
Conclusion

Provide an Integer Programming (IP) approach to
model the dedicated machine constraint

Future work
– Improving the performance of IP for on-line scheduling
problems
– Improving the technique to model the constraint
Thank You