Intelligent Preventive Maintenance
Scheduling in Semiconductor
Manufacturing Fabs
SRC/ISMT
FORCe: Factory Operations Research Center
Task NJ-877
Michael Fu, Director
Emmanuel Fernandez
Steven I. Marcus
Atlanta, GA, Oct. 21-22, 2003
1
SRC/ISMT Factory Operations Research Center
CONTENTS
1. Project Overview: Michael Fu
2. Summary of Completed Tasks: Emmanuel Fernandez
•
•
Interaction with Industry
Deliverables
•
•
•
•
•
•
•
Models, Algorithms, and Software Tools
Simulation Case Studies
Documentation submitted to SRC website
Other documentation
Software implementation: PMOST (Jose Ramirez)
Integration with fab schedulers: collaboration with ASU
Students trained
3. Summary of Doctoral and Master Theses: Students
4. Continuing and Future Research: Emmanuel Fernandez
5. Conclusions: Michael Fu
2
SRC/ISMT Factory Operations Research Center
Summary
Michael Fu
Robert H. Smith School of Business &
Institute for Systems Research
University of Maryland
1. Project Overview
3
SRC/ISMT Factory Operations Research Center
Research Plan (Proposed)
(1) Develop, test, and transfer software tools for optimal
PM planning and scheduling;
(2) Research and validate the models, methods and
algorithms for software development in (1);
(3) Facilitate the transfer of models, algorithms and tools
to 3rd party commercial software vendors.
4
SRC/ISMT Factory Operations Research Center
Executive Summary
•
Deliverables (reports) completed: January and July 2002;
SRC Pub P005269, P006317
•
Best Paper in Session, TECHCON 2003 (X.Yao presenter):
“Optimal preventive maintenance policies for unreliable production
systems with applications to semiconductor manufacturing”
•
Paper submitted for publication IEEE-Trans. Semiconductor Mfg:
–
•
5
“Incorporating Production Planning into Preventive Maintenance
Scheduling in Semiconductor Fabs”
INFORMS 2003 Annual Meeting: invited talks and an invited
session organized and chaired within Applied Probability Cluster.
SRC/ISMT Factory Operations Research Center
Executive Summary
•
software tool (PMOST):
–
–
6
Generic Scheduling Simulation Engine
Generic Implementation of PM Scheduling Algorithm
•
summer internships (AMD & Intel)
•
Ph.D. dissertations supported: He, Yao, Hu, Ramirez
MS dissertations supported: Crabtree, Jagannathan
•
commercialization feasibility discussions:
Adexa, Ibex Processes.
•
NIST internship via Swee Leong
SRC/ISMT Factory Operations Research Center
Industrial Liaisons
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
7
Matilda O'Connor,
Nipa Patel,
Ying Tat Leung,
Wayne F. Carriker,
Robin L. Hoskinson,
Ben-Rachel Igal,
Mani Janakiram,
Madhav Rangaswami,
Sidal Bilgin,
Russell Whaley,
Ramesh Rao,
Jan Verhagen,
Shekar Krishnaswamy,
K.J. Stanley,
Gurshaman S. Baweja,
Jason Wang,
James Yang,
Giant Kao,
Jacky Fan,
AMD
AMD (sign in SRC list)
IBM
Intel
Intel
Intel
Intel
Intel
LSI (sign in SRC list)
LSI (sign in SRC list)
National Semiconductor
Philips (sign in SRC list)
Motorola (sign in SRC list)
Motorola (sign in SRC list)
TI
TSMC (ISMT)
TSMC (ISMT)
TSMC (ISMT)
TSMC (ISMT)
SRC/ISMT Factory Operations Research Center
Research Personnel
Faculty:
– Michael Fu, Maryland
– Steve Marcus, Maryland
– Emmanuel Fernandez, Cincinnati
Students:
– Xiaodong Yao, Maryland (PhD final defense Nov.2003)
– Ying He, Maryland (PhD completed, summer 2002)
– Jiaqiao Hu, Maryland (3rd year PhD)
– Jason Crabtree, Cincinnati (MS completed, summer 2003)
– Jose Ramirez, Cincinnati (3rd year PhD)
– Sumita Jagannathan, Cincinnati (3rd year MS)
8
SRC/ISMT Factory Operations Research Center
Task Description
(Proposed)
Year 1 - Implementing the PM scheduling algorithm; developing,
distributing, and analyzing PM practice survey to drive PM
planning models and algorithms; literature review of research on
analytical and simulation-based models for PM planning with
production considerations.
Year 2 - Developing generic implementation platform for PM
scheduling algorithm to facilitate possible transfer
to 3rd party software provider; developing, testing, and
validating PM planning models and algorithms.
Year 3 – Implementing PM planning models and algorithms,
validating and testing; training workshop to facilitate transfer to
3rd party software vendor.
9
SRC/ISMT Factory Operations Research Center
Deliverables to Industry
(Proposed)
1. Survey of current PM practices in industry
(Report) (P:15-DEC-2001)
2. Models and algorithms to cover bottleneck
tool sets in a fab (Report) (P:31-MAR-2002)
3. Simulation engine implemented in commercially available
software, with case studies and benchmark data
(Report) (P:30-SEP-2002)
4. PM planning/scheduling software tools, with accompanying
simulation engine (Software, Report) (P:30-JUN-2003)
5. Installation and evaluation, workshop and consultation
(Report) (P:31-DEC-2003)
MORE DETAILS later in presentation
10
SRC/ISMT Factory Operations Research Center
Emmanuel Fernandez, Ph.D.
ECECS Department
University of Cincinnati
2. Summary of Completed Tasks
11
SRC/ISMT Factory Operations Research Center
Summary of Completed
Tasks
We summarize here the accomplishments in the project up to this
point:
•Interactions with industry
•Deliverables
•Models, Algorithms, and Software Tools
•Case Studies
•Documentation submitted to SRC website
•Other documentation
•Software Implementation: PMOST
•Integration with fab schedulers: collaboration with ASU
•Students trained
12
•(Doctoral and Master Theses)
SRC/ISMT Factory Operations Research Center
Interactions with Industry
13
SRC/ISMT Factory Operations Research Center
Interaction with Industry
• Interactions with industry have been fundamental in guiding our
research efforts:
• These facilitated the design, implementation, and proof of
concept of our algorithms, models and software tools.
• Interactions have taken place in the form of:
• Summer internships for our students from 2000 through 2002.
• Direct collaboration to exchange ideas and formulate problems and solutions,
e.g:
• Survey on best practices of PM scheduling;
• Visits to fabs to interview and obtain feedback from tool managers and
operators.
• Periodic teleconferences with MC liaisons.
•Co-authored publications derived from the research work.
14
SRC/ISMT Factory Operations Research Center
Interaction with Industry
•Summer Internships
During the project, a total of four summer internships were
completed at two member companies (2000 to 2002):
•X. Yao, 2000, AMD, Austin, TX: data collection and simulation of one case
study.
•X. Yao, J. Crabtree, 2001, AMD, Austin, TX: software implementation of
algorithms and models; built interfaces to integrate to fab systems.
•J. Crabtree, 2002, Intel, Chandler, AZ: data collection, software
implementation, and two simulation studies.
•J.A. Ramírez, 2002, AMD, Austin, TX: data collection and modeling for
wafer to calendar-based conversion of PM schedules, and two simulation
studies.
15
SRC/ISMT Factory Operations Research Center
Deliverables:
Models, Algorithms, and
Software Tools
16
SRC/ISMT Factory Operations Research Center
Deliverables
Models and Algorithms, and Software Tools
Here we summarize the Models and Algorithms produced by the
research team representing the theoretical/academic contributions
and basis for implementation in software tools:
-Hierarchical Model for Optimal PM Scheduling.
-MIP formulation of the PM scheduling problem.
-Conversion of wafer to calendar-based PM schedules.
- X. Yao Doctoral work.
17
SRC/ISMT Factory Operations Research Center
Deliverables
Models and Algorithms
Hierarchical Model for Optimal PM scheduling
Objective
Failure
Dynamics
Upper MDP
PM Policy
Demand
Pattern
Lower MIP
PM Schedule
WIP
Constraints
18
SRC/ISMT Factory Operations Research Center
Deliverables
Models and Algorithms - MIP Formulation
Objective:


l
l
l
max   bi  Vi (t ) - Ci  I i (t ) -  Ci  ai (t ) 
a (t )

t =1 i =1 
i =1
N
19
M
ri
SRC/ISMT Factory Operations Research Center
Deliverables
Models and Algorithms - MIP Formulation
Constraints:
nil
(i)
 ail (t ) = 1
t =1
for those PM tasks required to begin by
period nil
mil
(ii)
 ail (t ) = 0
t =1
for those PM tasks prohibited from
l
beginning before period mi
N
(iii)
20
 ail (t )  1
t =1
for all PM tasks in general
SRC/ISMT Factory Operations Research Center
Deliverables
Models and Algorithms - MIP Formulation
Constraints:
(iv) Vi (t ) = f ( a i (t ), b (t ))
i
"i , t
where a i (t ) is the set of PM decisions across all PM
tasks, and b i (t ) is a dummy variable holding the
value of a i (t ) from the previous period,
i.e. b i (t + 1) = a i (t )
21
SRC/ISMT Factory Operations Research Center
Deliverables
Models and Algorithms - MIP Formulation
Constraints:
(v)
I i (t + 1) = I i (t ) - X i (t ) + d i (t )
"i, t = 1,..., N - 1
where di(t) is amount of incoming wafers at tool i in
period t, and Xi(t) is the quantity of wafers processed
on tool i in period t.
(vi)
X i (t )  K i  Vi (t ) "i, t
where Ki is the wafer throughput coefficient for tool i.
22
SRC/ISMT Factory Operations Research Center
Deliverables
Models and Algorithms - MIP Formulation
Constraints:
(vii)
I i (t )  Li
"i, t
where Li is the maximum allowed inventory at tool i.
(viii)
rk (t ) = g (a i (t ), b i (t )) "k , t
where rk (t ) is the resource requirement variable for
resource k in period t.
23
SRC/ISMT Factory Operations Research Center
Deliverables
Models and Algorithms - MIP Formulation
Constraints:
(ix) rk (t )  Rk (t )
"k , t
where Rk(t) is the amount of resource k available in
period t.
k



(
)
0
(
)
0
(
)
0
(x) Vi t
, Ii t
, Xi t
, ri (t )  0
(xi) a il (t ) = 0 or 1
24
"k , i, t
"i, l , t
SRC/ISMT Factory Operations Research Center
Deliverables
Models and Algorithms
Conversion of Wafer to Calendar-based PM Schedules
PM window (W: warning, D: due, L: late)
Wl
ij
ij
ij
C t1
C t2
C t2
to
t1
t2
t3
C
ij

 C tij + rij   tij +   tij
k
k -1
=  ijk
ij
 C t k + rij   t k

Dl
...
ij
C t0
ij
t k +1
ij
ij
...
...
Ct
tW


if
ij
tk
ij

 
+   t k -1
ij
...
ij
Ct
D
(Wafer counts/period)
D +1
...
t D t D +1
tD
ij
ij
ij
tk
 Dl = Dl - C t
ij
ij
ij
ij
capacity at chamber
j , tool i .
k
rij : Throughput
rate in chamber
ij
C t : Cumulative
D
tD = tD + Dl 
ij
 t : Maximum
(Time period)
tL
 Dl
if  t k +   t k -1   t k
ij
ij
Ll
1
 r  rij
ij
j , tool i .
amount of wafers produced (estimated ), chamber
j , tool i .
Estimated due time (date)
k
ij
D l : Due amount
 t : Estimated
ij
of wafers for PM, chamber
incomming
WIP at chamber
k
 r : Throughput
ij
25
rate proportion
at chamber
j , tool i .
j , tool i , period t k .
j , tool i .
SRC/ISMT Factory Operations Research Center
Deliverables:
Simulation Case Studies
26
SRC/ISMT Factory Operations Research Center
Simulation Case
Studies
• Objectives
– Validate PM optimization through simulation
studies with real fab data
– Simulation studies conducted to compare
model-based optimized PM schedule and baseline or historical (“best in practice”) PM
schedules.
– Lay groundwork for integration of PM
optimization into production environment
27
SRC/ISMT Factory Operations Research Center
Simulation Case
Studies
•
Five case studies with real fab data. Calendar
and/or wafer based PM’s.
–
–
–
–
–
28
Case 1: Metal Deposition process (11 tools, 7days); Best
in Practice vs. Optimized Schedule
Case 2: Photolithography process (25 tools, 7 days); Best
in Practice vs. Optimized PM schedule
Case 3: Metal Deposition process (29 tools, 7 days);
Baseline vs. Optimized PM Schedule
Case 4: Photolithography process (12 tools, 7days);
Baseline vs. Optimized PM schedule
Case 5: Thin films process (28 tools, 21 days); Best in
Practice vs. Optimized PM schedule.
SRC/ISMT Factory Operations Research Center
Simulation Case
Studies
•
Results: Optimization made logical decisions and
showed good performance gains.
–
–
–
–
–
29
Case 1: up to 14% gain in throughput for one tool.
Case 2: Matched tool availability throughput for “Best-inPractice” schedule.
Case 3: about 1% average gain in tool availability for entire tool
group; 1.7% average gain in total throughput for entire tool
group.
Case 4: 1% average gain in tool availability for entire tool; 2.2%
average gain in total throughput for entire tool group.
Case 5: up to 6% gain in tool availability for one tool; 0.7%
average gain in tool availability for entire tool group; 1%
average gain in total throughput for entire tool group.
SRC/ISMT Factory Operations Research Center
Deliverables:
Documentation Submitted to
SRC Website
30
SRC/ISMT Factory Operations Research Center
Deliverables
Documentation submitted and currently available at SRC website
The following is the list of all the documentation produced by the research team and
available at the SRC website:
Annual review presentations
•Intelligent Preventive Maintenance Scheduling in Semiconductor Manufacturing Fabs; Crystal City, MD, December 13-14, 2001,
Pub P003262.
•Intelligent Preventive Maintenance Scheduling in Semiconductor Manufacturing Fabs; Tempe, AZ, April 9-10, 2002, Pub
P007441.
•Intelligent Preventive Maintenance Scheduling in Semiconductor Manufacturing Fabs; San Jose, CA, November 20-21, 2002,
Pub P005082.
Reports
•Survey of Current PM Practices in Industry, Conducted Via Web and Electronic Mail; E. Fernandez, M. Fu and S. Marcus; Univ. of
Maryland; 17-Jan-2002; 19pp.; Pub P003461.
Abstract: The researchers present the results of survey on the practices employed in the semiconductor manufacturing industry for scheduling Preventive
Maintenance (PM) tasks. The survey was distributed by the middle of October 2001, and responses were received until the middle of December 2001.
•Report on Models and Algorithms to Cover Major Bottleneck Tool Sets in a Semiconductor Manufacturing Fab; X. Yao, M. Fu,
S. Marcus and E. Fernandez; Univ. of Maryland; 29-Jul-2002; 4pp.; Pub P004304.
Abstract: The researchers have developed models and algorithms for optimal PM scheduling based on calendar information of time since last PM, and the time
window within which the next PM needs to fall. A computationally tractable mixed Integer/Linear Programming (IP/LP) model for short-term planning horizon,
e.g., 1-3 weeks, has been developed, tested and implemented to do the day-to-day actual scheduling of PM tasks across tools within a given family.
31
SRC/ISMT Factory Operations Research Center
Deliverables
Documentation submitted and currently available at SRC website
Reports
•Preventive Maintenance Optimal Scheduling Tool (PMOST): Ver. 1.0; J. Crabtree, J. Ramirez, E. Fernandez, X. Yao, M. Fu and S.
I. Marcus; Univ. of Maryland; 21-Jan-2003; 8pp.; Pub P005269.
Abstract: The Preventive Maintenance Optimal Scheduling Tool (PMOST) is a (programmed in C-language) software tool for optimal scheduling of Preventive
Maintenance tasks in Semiconductor Fabs.
•Preventive Maintenance Optimal Scheduling Tool (PMOST): Ver. 1.1; J. Crabtree, J. Ramirez, E. Fernandez, X. Yao, M. Fu and S.
I. Marcus; Univ. of Maryland; 10-Jul-2003; 10pp.; Pub P006317.
Abstract:The Preventive Maintenance Optimal Scheduling Tool (PMOST) is a (programmed in C-language) software tool for optimal scheduling of Preventive
Maintenance tasks in Semiconductor Fabs. PMOST v. 1.1 includes conversion of wafer-based to calendar-based PM schedules.
•Preventive Maintenance Scheduling Model and Generic Implementation, Mathematical Programming Modeling Languages
and Solvers; J. Crabtree, J. Ramirez, E. Fernandez; Univ. of Cincinnati; 29-Jul-2002; 6pp.; Pub P004306.
Abstract: This report present a survey on Mathematical Programming Modeling Languages (MDL) and Solvers that can be used in optimization of PM schedules.
Papers
•Optimization of Preventive Maintenance Scheduling for Semiconductor Manufacturing Systems: Models and Implementation;
X. Yao, M. Fu, S. Marcus and E. Fernandez-Gaucherand; Univ. of Maryland; 17-Dec-2001; 5pp.; Pub P003267.
Abstract: In this paper, the researchers present a two-layer hierarchical modeling framework for addressing the PM optimization problem for cluster tools, i.e., a
Markov Decision Process (MDP) model at the higher level, and a mixed Linear Programming (LP) model at the lower level. Production planning data such as WIP
levels are incorporated in these models. Paper presented at the 2001 IEEE International Conference on Control Applications, Mexico City, Mexico, 2001.
•Incorporating Production Planning into Preventive Maintenance Scheduling in Semiconductor Fabs; X. Yao, M. Fu, S. Marcus
and E. Fernandez-Gaucherand; Univ. of Maryland; 29-Jul-2002; 6pp.; Pub P004305.
Abstract: In this paper, a general mathematical model aiming at the optimization of preventive maintenance (PM) scheduling is proposed. The researchers
formulate the problem as a finite-horizon Markov decision process (MDP) that incorporates equipment dynamics and production system dynamics. Paper presented
at MASM 2002 Conference, Tempe, AZ, 2002.
32
SRC/ISMT Factory Operations Research Center
Deliverables
Documentation submitted and currently available at SRC website
Papers (cont.)
•Optimal Preventive Maintenance Policies for Unreliable Queueing/Production Systems with Applications to Semiconductor
Manufacturing; Xiaodong Yao, X. Xie, M. Fu, S. Marcus and E. Fernandez; Univ. of Maryland; 6-Jun-2003; 5pp.; Pub P006072.
Abstract: The reliability of equipment is critical to fab's operational performance, and Preventive Maintenance (PM) scheduling is a very challenging task in
semiconductor manufacturing. In this paper, the researchers will study optimal PM policies under the context of unreliable queueing systems. Presented at
TECHON 2003 (Awarded as "Best Paper in Session") , August 25-27, 2003, Dallas, TX.
•Optimal Importance Sampling in Securities Pricing; Y. Su and M. C. Fu; Univ. of Maryland; 21-Jun-2002; 29pp.; Pub P004145.
Abstract: To reduce variance in estimating security prices via Monte Carlo simulation, the researchers formulate a parametric minimization problem for the
optimal importance sampling measure, which is solved using infinitesimal perturbation analysis (IPA) and stochastic approximation (SA).
•Convergence of Simultaneous Perturbation Stochastic Approximation for Nondifferentiable Optimization; Y. He, M. C. Fu and
S. I. Marcus; Univ. of Maryland; 22-May-2003; 5pp.; Pub P005903.
Abstract: This paper considers Simultaneous Perturbation Stochastic Approximation (SPSA) for function minimization. The standard assumption for convergence
is that the function be three times differentiable, although weaker assumptions have been used for special cases. However, all previous work appears to at least
require differentiability. This paper relaxes the differentiability requirement and proves convergence using convex analysis.
Presentations
•Preventive Maintenance in Semiconductor Manufacturing Fabs; M. Fu; Univ. of Maryland; 15-May-2001; 41pp.; Pub P002234.
Abstract: FORCe Kick-off meeting presentation, Seatle, WA, April 26-27, 2001.
•Optimal Preventive Maintenance Policies for Unreliable Queueing/Production Systems with Applications to Semiconductor
Manufacturing Fabs; Xiaodong Yao, X. Xie, M. Fu, S. Marcus and E. Fernandez-Gaucherand; Univ. of Maryland; 8-Sep-2003; 13pp.;
Pub P006866.
Abstract: The reliability of equipment is critical to fab's operational performance, and Preventive Maintenance (PM) scheduling is a very challenging task in
semiconductor manufacturing. In this paper, the researchers will study optimal PM policies under the context of unreliable queueing systems. Presented at
TECHON 2003 (Awarded as "Best Paper in Session").
33
SRC/ISMT Factory Operations Research Center
Deliverables
Documentation submitted and currently available at SRC website
Other documentation
Software Description: Preventive Maintenance Optimal Scheduling Tool (PMOST); SMITLab University of Cincinnati; Univ. of
Maryland; 30-Jun-2003; 2pp.; Pub P006313.
Abstract: The Preventive Maintenance Optimal Scheduling Tool (PMOST) is a (C-language) software tool for optimal scheduling of Preventive Maintenance tasks
in Semiconductor Fabs. PMOST accepts a set of parameters related to the PM optimization process, e.g. planning horizon, number of resources for the PM tasks,
cost coefficient related to the PM tasks, etc.. PMOST obtains an optimal solution for that problem via the use of mathematical programming solvers for Linear
Programming/Mixed Integer Programming problems. The PMOST system was designed to work with different types of mathematical programming solvers, such
as IBM OSL and CPLEX. The system requires a set of data files, defined under specific (standard) formats, used in the optimization process.
Thesis-MS: Optimal Preventive Maintenance Scheduling in Semiconductor Fabs; J. Crabtree; Univ. of Cincinnati; 10-Oct-2003;
84pp.; Pub P007381.
Abstract: This thesis is spawned from the research project, "Preventive Maintenance in Semiconductor Fabs", sponsored by the Semiconductor Research
Corporation (SRC) and International SEMATECH. The project proposes a two-level hierarchical optimization structure that considers important factors such as the
work-in-progress (WIP) at a tool and the complex relationships between the chambers of a cluster tool. This thesis focuses on the lower level of the aforementioned
hierarchy that deals with PM scheduling. It expands on the work accomplished thus far in the project, specifically analyzing and fixing current issues with the PM
scheduling algorithm and creating a software implementation of the scheduling algorithm.
34
SRC/ISMT Factory Operations Research Center
Deliverables:
Other Documentation
35
SRC/ISMT Factory Operations Research Center
Deliverables
Other Documentation (not posted yet at SRC web site)
Papers
•Optimal Preventive Maintenance Scheduling in Semiconductor Manufacturing, X. Yao; E. Fernandez-Gaucherand; M.C. Fu; S.I.
Marcus; submitted for publication to IEEE Transactions on Semiconductor Manufacturing, 2003.
•An Algorithm to Convert Wafer to Calendar-Based Preventive Maintenance Schedules for Semiconductor Manufacturing
Systems, J.A. Ramírez-Hernández and E. Fernández-Gaucherand., to appear in Proceedings of the 42nd IEEE Conference on Decision and
Control, Maui, HI, December, 2003.
•Optimal PM Scheduling in Semiconductor Manufacturing Systems: Case Studies, Univ. Cincinnati, Univ. Maryland, AMD, Intel. In
preparation.
•Survey of Best Practices of PM Scheduling in Semiconductor Manufacturing Systems, J.A. Ramírez, J. Crabtree, E. Fernandez, X.
Yao , M. Fu and S.I. Marcus. In preparation.
•Optimal Joint Preventive Maintenance and Production Control Policies for Unreliable Production Systems, X. Yao, X. Xie, M. Fu,
and S. Marcus. In preparation.
Presentations
•Suppliers Teleconference Presentation: Commercialization, M. Fu, E. Fernandez, S.I. Marcus, J. Crabtree, J.A.
Ramírez, X. Yao, September 4th,, 2003, SEMATECH Webex teleconference system.
36
SRC/ISMT Factory Operations Research Center
Software Implementation:
PMOST
37
SRC/ISMT Factory Operations Research Center
Software Implementation:
PMOST
Software implementation of models and algorithms is an objective that has been
accomplished with the design and coding of the software Preventive Maintenance
Optimal Scheduling Tool (PMOST).
The following are the versions produced up to this point:
•PMOST ver. 1.0: first version of PMOST coded in C-language, running over MSWindows platforms (Windows 2000 and up). Include a basic text-mode user interface,
link with Optimization Library Solutions (OSL) solver from IBM, and generates
Mathematical Programming System (MPS) files describing the MIP problem.
•PMOST ver. 1.1: includes same characteristics of version 1.0 plus the conversion
algorithm for wafer-based to calendar-based PM schedules. An installer for MS-Windows
is included in this version.
•PMOST ver. 1.2: first Graphical User Interface (GUI) for PMOST, includes all
characteristics of verions 1.0 and 1.1. MS-Windows platform (Windows 2000 and up).
38
SRC/ISMT Factory Operations Research Center
Software Implementation:
PMOST
PMOST Block Diagram
pmost_ui.exe
main.c
START
User Interface
pmost.exe
read_data_file.c
read_fam_file.c
read_sch_file.c
read_wip_file.c
-Planning horizon
-Tools family
-Number of Technicians
utils.c
General functions used in
different parts of the system.
-Tool/PM data files: *.fam, *.data
-Conversion to calendar-time PMs data files
Read
Input Data
write_sch_file.c
-PM schedule: files *.sch
-Estimated WIP data files: files *.wip
ASAP
conv2cal (.exe, .c, .h)
-Debugging file: debug.txt
-Converted Schedule File: *.csch
Conversion to
calendar-time PMs
create_pm_vectors.c
write_set_val_files.c
write_mps_file.c
write_debug_file.c
Write
MPS file
-Output data: *.set, *.val files
-MPS file: *.mps
.mps file
main.c calls the
solver (OSL,
CPLEX, etc)
LP/MIP
SOLVER
solution file (text file)
parse_osl_solution.c
parse_cplexl_solution.c
write_solution_file.c
write_pm_order_file.c
39
Output: pm_order.txt
Parse
Solution
pm_solution.txt
SRC/ISMT Factory Operations Research Center
Software Implementation:
PMOST
PMOST 1.2 with GUI, Demo Movie
40
SRC/ISMT Factory Operations Research Center
Software Implementation:
PMOST
PMOST 1.1 with text-mode user interface, screen captions
•The input data used for this exercise was artificially created for illustration purposes only.
•The user executes the file pmost.exe and the following prompt will be shown:
41
SRC/ISMT Factory Operations Research Center
Software Implementation:
PMOST
PMOST 1.1 with text-mode user interface, screen captions
•After that, the user will define the “Start Date” and “End Date” in the format requested in the following
screenshot:
42
SRC/ISMT Factory Operations Research Center
Software Implementation:
PMOST
PMOST 1.1 with text-mode user interface, screen captions
•Finally, PMOST will ask for the number of technicians assigned to each period in the planning horizon
defined by the “Start Date” and the “End Date”, as follows:
43
SRC/ISMT Factory Operations Research Center
Software Implementation:
PMOST
PMOST 1.1 with text-mode user interface, screen captions
•PMOST will then produce the MPS file, and finally it will communicate this MPS to the solver selected. The
solver will compute the optimal solution that will be decoded by PMOST and written in the output_files directory.
The messages presented by PMOST are as follows:
44
SRC/ISMT Factory Operations Research Center
Software Implementation:
PMOST
PMOST 1.1 with text-mode user interface, screen captions
•For this example in particular, the pm_solution.txt file will looks as follows:
Tool Name
PM Name
CT01
7 DAY PM
CT02
14 DAY PM
CT03
28 DAY PM
CT04
56 DAY PM
CT04
PMCH1
CT05
PMCH4
CT06
PMCH5
CT07
PMCH2
CT08
PMCH3
CT09
KIT CH2
CT10
KIT CH3
CT02
7 DAY PM
CT04
14 DAY PM
CT01
28 DAY PM
CT05
56 DAY PM
CT01
PMCH1
CT10
PMCH4
CT04
PMCH5
CT06
PMCH2
CT05
PMCH3
CT03
KIT CH2
CT09
KIT CH3
45
Old Due Date
01/06/2002 07:00:00
01/05/2002 07:00:00
01/04/2002 07:00:00
01/03/2002 07:00:00
01/01/2002 07:00:00
01/02/2002 07:00:00
01/03/2002 07:00:00
01/04/2002 07:00:00
01/02/2002 07:00:00
01/05/2002 07:00:00
01/01/2002 07:00:00
01/02/2002 07:00:00
01/03/2002 07:00:00
01/04/2002 07:00:00
01/01/2002 07:00:00
01/05/2002 07:00:00
01/01/2002 07:00:00
01/02/2002 07:00:00
01/05/2002 07:00:00
01/03/2002 07:00:00
01/02/2002 07:00:00
01/01/2002 07:00:00
Optimal Due Date
01/05/2002 07:00:00
01/06/2002 07:00:00
01/02/2002 07:00:00
01/03/2002 07:00:00
01/03/2002 07:00:00
01/03/2002 07:00:00
01/06/2002 07:00:00
01/06/2002 07:00:00
01/04/2002 07:00:00
01/05/2002 07:00:00
01/01/2002 07:00:00
01/01/2002 07:00:00
01/03/2002 07:00:00
01/05/2002 07:00:00
01/03/2002 07:00:00
01/05/2002 07:00:00
01/01/2002 07:00:00
01/03/2002 07:00:00
01/06/2002 07:00:00
01/03/2002 07:00:00
01/02/2002 07:00:00
01/01/2002 07:00:00
SRC/ISMT Factory Operations Research Center
Software Implementation:
PMOST
PMOST 1.1 with text-mode user interface, screen captions
•Also, a pm_order.txt file can be generated for use it in AutoSched AP simulations as PM orders:
PMORDER
order1
order2
order3
order4
order5
order6
order7
order8
order9
order10
order11
order12
order13
order14
order15
order17
order18
order19
order20
order21
order22
46
STN
CT01
CT02
CT03
CT04
CT04
CT05
CT06
CT07
CT08
CT09
CT10
CT02
CT04
CT01
CT01
CT10
CT04
CT06
CT05
CT03
CT09
DUEDATE
01/05/2002 07:00:00
01/06/2002 07:00:00
01/02/2002 07:00:00
01/03/2002 07:00:00
01/03/2002 07:00:00
01/03/2002 07:00:00
01/06/2002 07:00:00
01/06/2002 07:00:00
01/04/2002 07:00:00
01/05/2002 07:00:00
01/01/2002 07:00:00
01/01/2002 07:00:00
01/03/2002 07:00:00
01/05/2002 07:00:00
01/05/2002 07:00:00
01/01/2002 07:00:00
01/03/2002 07:00:00
01/06/2002 07:00:00
01/03/2002 07:00:00
01/02/2002 07:00:00
01/01/2002 07:00:00
PTIME
8.000000
12.000000
55.000000
55.000000
48.000000
5.000000
5.000000
50.000000
50.000000
24.000000
24.000000
8.000000
12.000000
55.000000
48.000000
5.000000
5.000000
50.000000
50.000000
24.000000
24.000000
PTUNITS
hr
hr
hr
hr
hr
hr
hr
hr
hr
hr
hr
hr
hr
hr
hr
hr
hr
hr
hr
hr
hr
SRC/ISMT Factory Operations Research Center
Integration with Fab
Schedulers: Collaboration with
ASU
47
SRC/ISMT Factory Operations Research Center
Integration of Fab Schedulers:
Collaboration with ASU
•Collaboration is under way with the ASU Team with the objective of integrating
fab scheduling and optimal PM scheduling in semiconductor fabs.
– The goal is integrate both fab scheduling and preventive maintenance to evaluate long-term
performances in semiconductor manufacturing systems via simulation analysis.
– The research teams have identified the requirements for such integration as well as proposed a
work plan to complete the task.
– Currently, both teams are working to close the gap in the software implementation and start
experiments using simple models (e.g., minifab) for proof of concept.
– Integration involves communication between simulation software (customization of ASAP)
and the corresponding schedulers (jobs and PMs).
48
SRC/ISMT Factory Operations Research Center
Students Trained
49
SRC/ISMT Factory Operations Research Center
Students Trained
The following students have participated in the research tasks for this project,
and have received substantial training in different topics (e.g., ASAP training,
courses in stochastic modeling and decision, simulation analysis and modeling):
– Ph.D. Students:
•
•
•
•
Ying He, Maryland (Ph.D. completed, graduated on summer 2002)
Jiaqiao Hu, Maryland (3rd year Ph.D.)
José Ramírez, Cincinnati (3rd year Ph.D.)
Xiaodong Yao, Maryland (Ph.D., will graduate in December 2003)
– M.Sc. Students:
• Jason Crabtree, Cincinnati (M.Sc. completed, graduated September 2003)
• Sumita Jagannathan, Cincinnati (continuing M.Sc.)
50
SRC/ISMT Factory Operations Research Center
(Students)
3. Summary of Doctoral and
Master Theses
51
SRC/ISMT Factory Operations Research Center
Summary of Doctoral
and Master Theses
M.Sc. Thesis on Electrical & Computer Engineering & Computer Science
Title: Optimal Preventive Maintenance Scheduling in Semiconductor Fabs
Author: Jason Crabtree, SMITLab, University of Cincinnati.
Defense/submission date: August 4th 2003.
Abstract:
This thesis is spawned from the research project, "Preventive Maintenance in Semiconductor Fabs",
sponsored by the Semiconductor Research Corporation (SRC) and International SEMATECH. The
project proposes a two-level hierarchical optimization structure that considers important factors such as
the work-in-progress (WIP) at a tool and the complex relationships between the chambers of a cluster
tool. This thesis focuses on the lower level of the aforementioned hierarchy that deals with PM
scheduling. It expands on the work accomplished thus far in the project, specifically analyzing and
fixing current issues with the PM scheduling algorithm and creating a software implementation of the
scheduling algorithm. (See SRC Publication P007381)
52
SRC/ISMT Factory Operations Research Center
Summary of Doctoral
and Master Theses
Research Proposal
Ph.D. on Electrical & Computer Engineering & Computer Science
Title: Reinforcement Learning (Neuro-Dynamic Programming) Approach for
Production Control of Semiconductor Manufacturing Re-Entrant Lines
Author: José A. Ramírez, SMITLab, University of Cincinnati.
Defense/submission date: proposal to be defended in December 2003.
Description:
Semiconductor fabs are complex systems characterized by re-entrant lines in the manufacturing
process. The scheduling of jobs (control) in this type of systems is a challenging task. Finding optimal
scheduling policies, via analytical procedures, is a difficult problem. Generally, it is intractable given
the complexity and high dimensionality of such systems. We propose the use of a novel approach in
control of high-dimensional and complex systems: Reinforcement Learning (Neuro-Dynamic
Programming).
53
SRC/ISMT Factory Operations Research Center
Summary of Doctoral
and Master Theses
Research Proposal
Ph.D. on Electrical & Computer Engineering & Computer Science
Jose A. Ramírez – SMITLab – University of Cincinnati
Description (cont.):
•Reinforcement Learning (RL) (Neuro-Dynamic Programming (NDP)) has been successfully used to
find suboptimal (near to the optimal) policies in complex systems, where the curse of dimensionality is
presented as a serious constraint to apply Dynamic Programming approaches for optimization and
control. RL and NDP are new and very promissory approaches for a wide spectrum of applications.
•RL and NDP methods are based in learning from the interaction with the system of interest (e.g., learn
an (sub) optimal scheduling policy) or its corresponding model (simulation). From this interaction we
maximize the long-term returns (performance index) given the actions (control) applied to the system,
and derived from the learning process.
•Semiconductor manufacturing systems have the essential characteristics to apply these type of
approaches: simulation models are available, but analytical modeling is too complex in large scale
systems and stochastic events are present (e.g., tool failures, tool maintenance).
54
SRC/ISMT Factory Operations Research Center
Summary of Doctoral
and Master Theses
Xiaodong Yao,
Ph.D. Student, University of Maryland,
Optimal Joint Preventive Maintenance
and Production Control Policies for
Unreliable Production Systems
55
SRC/ISMT Factory Operations Research Center
Overview
1.
2.
3.
56
In literature
 preventive maintenance (PM) and production control have
been treated independently.
Recent work
 Boukas and Liu (2001) (continuous flow model)
 Iravani and Duenyas (2002) (propose and analyze a heuristic
policy of “double-threshold” policy)
 Sloan and Shanthikumar (2002, 2000) (integrated production
dispatching and maintenance scheduling in semiconductor
manufacturing)
Our objective
 characterization of optimal joint policies for unreliable
production systems with either
 time-dependent failures
 operation-dependent failures
SRC/ISMT Factory Operations Research Center
Systems with time-dependent
failures
u  [0,P]
d, constant demand
• The machine experiences time-dependent failures: Machine deteriorates
over calendar time, and can fail while idle. (e.g., calendar-based PMs)
• flexible production rate, u  [0,P], P is the maximal production rate
• inventory consumed by a constant demand d, and backlog allowed
• Upon machine failures, repair has to be initiated with cost cr, and time
for repair r is a r.v.
• Before machine failures, PM can be applied with cost cp, and time for
PM p is a r.v. as well.
• inventory holding cost g(·), piecewise linear function of inventory level
• Objective: find PM / production policy to minimize discounted cost
57
SRC/ISMT Factory Operations Research Center
Markov-Decision Process
Formulation
Consider the discrete-time model:
 state st , it , nt  where st = inventory level
2 : if machine in PM

it = 1 : if machine in working state

0 : if machine in repair
nt = time periods since the last change of machine state i
 PM : to do PM
 control ut = 
, while machine in working state, i.e., it = 1.


u

0
,
P
:
to
produce

 conditiona l probabilit ies :
f n = Pr it +1 = 0 it = 1, nt = n ,
pn = Pr it +1 = 1 it = 2, nt = n ,
rn = Pr it +1 = 1 it = 0, nt = n .
58
SRC/ISMT Factory Operations Research Center
Bellman Equations
The optimal cost functions satisfy:
 when machine in repair :
J s,0, n  = g s  + b  rn  J s - d ,1,0  + b  1 - rn   J s - d ,0, n + 1,
 when machine in PM :
J s,2, n  = g s  + b  pn  J s - d ,1,0  + b  1 - pn   J s - d ,2, n + 1,
 when machine in working state :

J s,1, n  = min Q
where Q
PM
PM
s,1, n ;

min Q s,1, n  ,
u
u = 0 ,, P
s,1, n  = c p + J s,2,0,
Q s,1, n  = g s  + b  f n  cr + J s + u - d ,0,0 
u
+ b  1 - f n   J s + u - d ,1, n + 1.
59
SRC/ISMT Factory Operations Research Center
Characterization of
optimal policy
Theorem 1: J(s,0,n), J(s,1,n), J(s,2,n) are decreasing function in s, for s  0.
Remark: This implies that when there is backlog, if choose not to do PM,
then optimal production rate is at least as large as demand rate.
Theorem 2: J(s,1,n) is an increasing function in n, if the following conditions
are satisfied:
(1) the machine has IFR;
(2) cr  cp;
(3) times for repair and PM are stochastically equivalent
or machine failure rate is constant.
Corollary: For fixed inventory level, the optimal joint policy has
control-limit form w.r.t. machine age.
Theorem 3: There exists s* such that "s > s*, *(s,1,n) = 0 or PM, for all n.
Remark: This is an intuitive observation, such that at high inventory level,
it’s not optimal to produce.
60
SRC/ISMT Factory Operations Research Center
Numerical Study
Example:
the machine lifetime ~ Weibull (4,5),
time for PM ~ U(0,3),
time for CM ~ U(0,6),
d = 1, P =3, cp = 50, cr = 2 * cp,
c+ = 1, c- = 10,
b = 0.95.
Fig. 1: the optimal policy
Fig. 2: The relative difference of cost
function under the joint optimal policy
and independently optimized policy.
diff = (Jind – J*)/J*  100%.
61
Fig. 2
SRC/ISMT Factory Operations Research Center
Operation-Dependent
Failures
u {0,1}
1, with prob. q
•
•
•
•
Operation-dependent failures: Machine deteriorates only when it is
producing, and can’t fail while idle.
(e.g., wafer-count-based or operation-history based PMs)
Random demand: unit demand in each period with prob. q
Machine can produce at rate either 0 or 1, u  {0,1}
Upon machine failures, repair has to be initiated with cost cr, and time
for repair r is a r.v.
•
Before machine failures, PM can be applied with cost cp, and time for
PM p is a r.v. as well.
•
•
62
inventory holding cost g(·), piecewise linear function of inventory level
Objective: find PM / production policy to minimize discounted cost
SRC/ISMT Factory Operations Research Center
Bellman Equations
The optimal cost functions satisfy:
 when machine in repair :
J s,0, n  = g s  + b q  rn  J s - 1,1,0  + q1 - rn J s - 1,0, n + 1
+ b (1 - q )rn  J s,1,0  + 1 - q 1 - rn J s,0, n + 1,
 when machine in PM :
J s,2, n  = g s  + b q  p n  J s - 1,1,0  + q 1 - p n J s - 1,2, n + 1
+ b (1 - q ) p n  J s,1,0  + 1 - q 1 - p n J s,2, n + 1,
 when machine in working state :

J s,1, n  = min Q
where Q
Q
PM
0
PM
s,1, n ; Q 0 s,1, n ; Q1 s,1, n ,
s,1, n  = c p + J s,2,0,
s,1, n  = g s  + b  q  J ( s - 1,1, n) + (1 - q) J ( s,1, n),
Q ( s,1, n) = g ( s ) + b q  f n cr + J s,0,0  + q1 - f n J s,1, n + 1
1
+ b (1 - q ) f n cr + J s + 1,0,0  + 1 - q 1 - f n J s + 1,1, n + 1
63
SRC/ISMT Factory Operations Research Center
Characterization of
optimal policy
Theorem 4: J(s,1,n) is an increasing function in n, if the following
conditions are satisfied:
(1) the machine has IFR;
(2) cr  cp;
(3) r st. p.
Corollary: For fixed inventory level, the optimal joint policy has
control-limit form w.r.t. machine age.
Theorem 5: There exists s* such that "s > s*, *(s,1,n) = 0, for all n.
64
SRC/ISMT Factory Operations Research Center
Numerical Example
Example:
the machine lifetime ~ Weibull (4,5),
time for PM ~ U(0,3),
time for CM ~ U(0,6),
q = 0.8, cp = 50, cr = 2 * cp,
c+ = 1, c- = 10,
b = 0.95.
Fig. 3: the optimal policy
65
SRC/ISMT Factory Operations Research Center
Conclusions
The big picture:
Hierarchical Framework for PM planning and scheduling.
High Level:
 objective: to derive optimal PM policies
 methodology: Markov-decision processes
Low Level:
 objective: to obtain optimal PM schedules
 methodology: Mathematical programming
66
SRC/ISMT Factory Operations Research Center
4. Continuing and Future
Research
67
SRC/ISMT Factory Operations Research Center
Continuing and Future
Research
Finishing and submission of papers for publication
•Optimal PM Scheduling in Semiconductor Manufacturing Systems: Case Studies, J.
A. Ramírez, J. Crabtree, E. Fernandez, M. Fu, X. Yao, S.I. Marcus, Advanced Micro
Devices, Corp., Intel, Corp., in preparation.
•Survey of Best Practices of PM Scheduling in Semiconductor Manufacturing
Industry, J.A. Ramírez, J. Crabtree, E. Fernandez, X. Yao , M. Fu and S.I. Marcus, to be
submitted for publication.
•Optimal Joint Preventive Maintenance and Production Control Policies for
Unreliable Production Systems, X. Yao, X. Xie, M. Fu, and S. Marcus, in preparation.
•Conversion of Wafer-Based PM Schedules into Calendar-Based for Optimal PM
Scheduling in Semiconductor Manufacturing, J.A. Ramírez, E. Fernandez, in
preparation.
68
SRC/ISMT Factory Operations Research Center
Continuing and Future
Research
Commercialization
Continue working with suppliers…
Collaboration with other research groups
•Continue task for integration of job and PM scheduling algorithms in a pilot study with
ASU Team.
•Analysis of simulations from integration of fab and PM scheduling algorithms.
• Other
•Xiaodong Yao, Ph.D. Dissertation defense and submission.
•No cost extension through August 2004.
69
SRC/ISMT Factory Operations Research Center
5. Conclusions
70
SRC/ISMT Factory Operations Research Center
Conclusions
71
SRC/ISMT Factory Operations Research Center
Descargar

PM Optimization for Cluster Tools