Semiconductor Manufacturing Process: Layout Mathematical Modeling

Keywords: layout mathematics

Semiconductor Manufacturing Process: Layout Mathematical Modeling

1. Problem Context

A modern semiconductor fabrication facility (fab) involves:

Process Complexity

• 500–1000+ individual process steps per wafer
• Multiple product types with different process routes
• Strict process sequencing and timing requirements

Re-entrant Flow Characteristics

• Wafers revisit the same tool types (e.g., lithography) 30–80 times
• Creates complex dependencies between process stages
• Traditional flow-shop models are inadequate

Stochastic Elements

• Tool failures and unplanned maintenance
• Variable processing times
• Yield loss at various process steps
• Operator availability fluctuations

Economic Scale

• Leading-edge fab costs: $15–20+ billion
• Equipment costs: $50M–$150M per lithography tool
• High cost of WIP (work-in-process) inventory

2. Core Mathematical Formulations

2.1 Quadratic Assignment Problem (QAP)

The foundational model for facility layout optimization:

Subject to:

Variables:

Complexity Analysis:

• Problem Class: NP-hard
• Practical Limit: Exact solutions feasible for $n \leq 30$
• Large Instances: Require heuristic/metaheuristic approaches

2.2 Mixed-Integer Linear Programming (MILP) Extension

For realistic industrial constraints:

Capacity Constraint:

Space Constraint:

Adjacency Requirement (linearized):

Variables:

2.3 Network Flow Formulation

Wafer flow modeled as a multi-commodity network flow problem:

Flow Conservation Constraint:

Arc Capacity Constraint:

Variables:

3. Queuing Network Models 3.1 Fundamental Performance Metrics

Little's Law (fundamental relationship):

Equivalently:

Station Utilization:

Definitions:

• $L$ — Average number in system (WIP)
• $\lambda$ — Arrival rate (throughput)
• $W$ — Average time in system (cycle time)
• $\rho_k$ — Utilization of station $k$
• $v_k$ — Average number of visits to station $k$ per wafer
• $\mu_k$ — Service rate at station $k$
• $m_k$ — Number of parallel tools at station $k$

3.2 Cycle Time Approximation

Kingman's Formula (GI/G/1 approximation):

Extended GI/G/m Approximation:

Total Cycle Time:

Variables:

3.3 Re-entrant Flow Complexity

Characteristics of Re-entrant Systems:

• Variability Propagation: Variance accumulates through network
• Correlation Effects: Successive visits to same station are correlated
• Priority Inversions: Lots at different stages compete for same resources

Variability Propagation (Linking Equation):

Departure Variability:

Where:

• $p_{ij}$ — Routing probability from station $i$ to $j$
• $C_{d,k}^2$ — Squared CV of departures from station $k$

4. Stochastic Modeling

4.1 Random Variable Distributions

Log-normal PDF:

Weibull PDF (for reliability):

4.2 Markov Decision Process (MDP) Formulation

For sequential decision-making under uncertainty:

Bellman Equation:

Optimal Policy:

MDP Components:

5. Hierarchical Layout Structure

5.1 Bay Layout Architecture

Modern fabs use a hierarchical bay layout:

│─────────────────────────────────────────────────────────────│
│    Bay 1      │    Bay 2      │    Bay 3      │    Bay 4    │
│  (Lithography)│    (Etch)     │  (Deposition) │    (CMP)    │
├───────────────┴───────────────┴───────────────┴─────────────┤
│              INTERBAY AMHS (Overhead Hoist Transport)       │
├───────────────┬───────────────┬───────────────┬─────────────┤
│    Bay 5      │    Bay 6      │    Bay 7      │    Bay 8    │
│  (Implant)    │  (Metrology)  │   (Diffusion) │   (Clean)   │
│───────────────┴───────────────┴───────────────┴─────────────│

Two-Level Optimization:

1. Macro Level: Assign tool groups to bays

• Objective: Minimize interbay transport
• Constraints: Bay capacity, cleanroom class requirements

2. Micro Level: Arrange tools within each bay

• Objective: Minimize within-bay movement
• Constraints: Tool footprint, utility access

5.2 Distance Metrics

Rectilinear (Manhattan) Distance:

Euclidean Distance:

Actual AMHS Path Distance:

Where $(x_k, y_k)$ and $(x_l, y_l)$ are coordinates of locations $k$ and $l$.

6. Objective Functions

6.1 Multi-Objective Formulation

6.2 Individual Objective Functions

Material Handling Cost:

Cycle Time:

Work-in-Process:

Throughput (bottleneck-constrained):

Variables:

6.3 Weighted-Sum Scalarization

Where:

• $w_i$ — Weight for objective $i$ (with $\sum_i w_i = 1$)
• $f_i^{\min}, f_i^{\max}$ — Normalization bounds for objective $i$

7. Constraint Categories

7.1 Constraint Summary Table

7.2 Detailed Constraint Formulations

Non-Overlapping Constraint (for unequal areas):

With:

Cleanroom Zone Assignment:

Where $\mathcal{Z}_c$ is the set of locations with cleanroom class $c$.

8. Solution Methods

8.1 Exact Methods

Applicable for small instances ($n \leq 30$):

• Branch and Bound:
• Uses Gilmore-Lawler bound for pruning
• Lower bound: $\text{LB} = \sum_{i} \min_k \{ \text{flow}_i \cdot \text{dist}_k \}$

• Dynamic Programming:
• For special structures (e.g., single-row layout)
• Complexity: $O(n^2 \cdot 2^n)$ for general case

• Cutting Plane Methods:
• Linearize QAP using reformulation-linearization technique (RLT)

8.2 Construction Heuristics

CRAFT (Computerized Relative Allocation of Facilities Technique):

│─────────────────────────────────────────────────────────────│
│ Algorithm CRAFT:                                            │
│ 1. Start with initial layout                                │
│ 2. Evaluate all pairwise exchanges                          │
│ 3. Select exchange with maximum cost reduction              │
│ 4. If improvement found, goto step 2                        │
│ 5. Return final layout                                      │
│─────────────────────────────────────────────────────────────│

CORELAP (Computerized Relationship Layout Planning):

│────────────────────────────────────────────────────────────│
│ Algorithm CORELAP:                                         │
│ 1. Calculate Total Closeness Rating (TCR) for each dept    │
│ 2. Place department with highest TCR at center             │
│ 3. For remaining departments:                              │
│    a. Calculate placement score for candidate locations    │
│    b. Place dept at location maximizing adjacency          │
│ 4. Return layout                                           │
│────────────────────────────────────────────────────────────│

ALDEP (Automated Layout Design Program):

│─────────────────────────────────────────────────────────────│
│ Algorithm ALDEP:                                            │
│ 1. Randomly select first department                         │
│ 2. Scan relationship matrix for high-rated pairs            │
│ 3. Place related departments in sequence                    │
│ 4. Repeat until all departments placed                      │
│ 5. Evaluate layout; repeat for multiple random starts       │
│─────────────────────────────────────────────────────────────│

8.3 Metaheuristics

Genetic Algorithm (GA):

│────────────────────────────────────────────────────────────│
│ Algorithm GA_for_Layout:                                   │
│   Initialize population P of size N (random permutations)  │
│   Evaluate fitness f(x) for all x in P                     │
│                                                            │
│   While not converged:                                     │
│     Selection:                                             │
│       Parents = TournamentSelect(P, k=3)                   │
│     Crossover (PMX or OX for permutations):                │
│       Offspring = PMX_Crossover(Parents, p_c=0.8)          │
│     Mutation (swap or insertion):                          │
│       Offspring = SwapMutation(Offspring, p_m=0.1)         │
│     Evaluation:                                            │
│       Evaluate fitness for Offspring                       │
│     Replacement:                                           │
│       P = ElitistReplacement(P, Offspring)                 │
│                                                            │
│   Return best solution in P                                │
│────────────────────────────────────────────────────────────│

Simulated Annealing (SA):

│────────────────────────────────────────────────────────────│
│ Algorithm SA_for_Layout:                                   │
│   x = initial_solution()                                   │
│   T = T_initial                                            │
│                                                            │
│   While T > T_final:                                       │
│     For i = 1 to iterations_per_temp:                      │
│       x' = neighbor(x)  (e.g., swap two departments)       │
│       Δf = f(x') - f(x)                                    │
│                                                            │
│       If Δf < 0:                                           │
│         x = x'                                             │
│       Else If random() < exp(-Δf / T):                     │
│         x = x'                                             │
│                                                            │
│     T = α × T  (Cooling, α ≈ 0.95)                         │
│                                                            │
│   Return x                                                 │
│────────────────────────────────────────────────────────────│

Cooling Schedule:

8.4 Simulation-Optimization Framework

│─────────────│     │──────────────────│     │─────────────────│
│   Layout    │────▶│  Discrete-Event  │────▶│   Performance   │
│  Solution   │     │   Simulation     │     │    Metrics      │
│─────────────│     │──────────────────│     │────────┬────────│
      ▲                                              │
      │                                              │
      │         │──────────────────│                 │
      │─────────│   Optimization   │◀────────────────│
                │    Algorithm     │
                │──────────────────│

Surrogate-Assisted Optimization:

Where $\hat{f}$ is a surrogate model (e.g., Gaussian Process, Neural Network) trained on simulation evaluations.

9. Advanced Topics

9.1 Digital Twin Integration

Real-Time Layout Performance:

Where:

• $\mathbf{s}(t)$ — System state at time $t$
• $\boldsymbol{\theta}(t)$ — Real-time parameter estimates

Applications:

• Real-time cycle time prediction
• Predictive maintenance scheduling
• Dynamic dispatching optimization

9.2 Machine Learning Hybridization

Graph Neural Network (GNN) for Layout:

Reinforcement Learning for Dispatching:

Surrogate Model (Neural Network):

9.3 Robust Optimization

Min-Max Formulation:

Uncertainty Set (Polyhedral):

Chance-Constrained Formulation:

Where:

• $\boldsymbol{\xi}$ — Uncertain parameters (demand, yield, tool availability)
• $\mathcal{U}$ — Uncertainty set
• $\Gamma$ — Budget of uncertainty
• $\epsilon$ — Acceptable violation probability

9.4 Multi-Objective Optimization

Pareto Optimality:

Solution $\mathbf{x}^*$ is Pareto optimal if there exists no $\mathbf{x}$ such that:

NSGA-II Crowding Distance:

10. Key Insights

10.1 Fundamental Observations

1. Multi-Scale Nature:

• Nanometer-scale process physics
• Meter-scale equipment layout
• Kilometer-scale supply chain

2. Re-entrant Flow Complexity:

• Traditional queuing theory requires significant adaptation
• Correlation effects are significant
• Scheduling and layout are tightly coupled

3. Simulation Necessity:

• Analytical models sacrifice too much fidelity
• High-fidelity simulation essential for validation
• Surrogate models bridge the gap

4. Layout-Scheduling Interaction:

• Optimal layout depends on dispatch policy
• Optimal dispatch depends on layout
• Joint optimization is active research area

5. Industry Trends Impact Modeling:

• EUV lithography changes bottleneck structure
• 3D integration (chiplets, stacking) changes flow patterns
• High-mix low-volume increases variability

10.2 Practical Recommendations

• Start with QAP formulation for initial layout
• Use queuing models for performance estimation
• Validate with discrete-event simulation
• Apply metaheuristics for large-scale instances
• Consider multi-objective formulation for trade-off analysis
• Integrate digital twin for real-time optimization

Symbol Reference

Source: ChipFoundryServices — Search this topic — Ask CFSGPT