Fab Scheduling: Mathematical Modeling

A comprehensive technical reference on mathematical optimization, queueing theory, and computational methods for semiconductor manufacturing process scheduling.

1. Problem Characteristics

Semiconductor fabrication (fab) scheduling is among the most complex scheduling problems in manufacturing. Key characteristics include:

• Reentrant Flow : Wafers visit the same workstations multiple times (e.g., photolithography visited 30+ times at different "layers")
• Scale :
• 400–800 processing steps per wafer
• Hundreds of machines across dozens of workstations
• Thousands of active lots representing hundreds of product types
• Cycle times of 4–8 weeks
• Sequence-Dependent Setup Times : Changeover time varies based on the product sequence
• Batch Processing : Some machines (diffusion furnaces, wet etch) process multiple lots simultaneously
• Machine Qualification : Not all machines can process all products—qualification restrictions apply
• Queue Time Constraints : Maximum time limits between certain operations due to contamination risk
• Rework : Defective wafers may require reprocessing
• Hot Lots : Emergency/priority lots requiring expedited processing

2. Mixed Integer Programming Formulations

2.1 Sets and Indices

2.2 Parameters

2.3 Decision Variables

2.4 Objective Function

Minimize Weighted Tardiness:

$$ \min \sum_{j \in J} w_j \cdot \max\left(0, \; C_{j,|O_j|} - d_j\right) $$

Alternative Objectives:

• Minimize makespan: $\displaystyle \min \max_{j \in J} C_{j,|O_j|}$
• Maximize throughput: $\displaystyle \max \sum_{j \in J} \mathbf{1}_{[C_j \leq T]}$
• Minimize average cycle time: $\displaystyle \min \frac{1}{|J|} \sum_{j \in J} \left(C_{j,|O_j|} - r_j\right)$

2.5 Constraints

Machine Assignment — Each operation assigned to exactly one qualified machine:

$$ \sum_{m \in M_{jo}} x_{jom} = 1 \quad \forall j \in J, \; \forall o \in O_j $$

Precedence — Operations within a job follow sequence:

$$ C_{j,o-1} + \sum_{m \in M_{jo}} p_{jom} \cdot x_{jom} \leq C_{jo} \quad \forall j \in J, \; \forall o \in O_j, \; o > 1 $$

Processing Time Relationship:

$$ C_{jo} = S_{jo} + \sum_{m \in M_{jo}} p_{jom} \cdot x_{jom} $$

Disjunctive Constraints — No overlap on machines (big-M formulation):

$$ C_{jo} + s_{jo,j'o'}^m + p_{j'o'm} \leq C_{j'o'} + M \cdot \left(1 - y_{jo,j'o'}^m\right) $$

$$ C_{j'o'} + s_{j'o',jo}^m + p_{jom} \leq C_{jo} + M \cdot y_{jo,j'o'}^m $$

Queue Time Constraints:

$$ S_{i,j+1} - C_{ij} \leq Q_{\max}^{(j)} \quad \text{for critical operation pairs} $$

2.6 Scalability Challenge

For a fab with:

• 100 machines
• 1,000 lots
• 500 operations per lot

The problem has approximately:

$$ \text{Binary variables} \approx 100 \times 1000 \times 500 = 5 \times 10^7 $$

This exceeds the capability of commercial MIP solvers, necessitating decomposition and heuristic methods.

3. Batching Subproblem

3.1 Additional Variables

3.2 Batching Constraints

Unique Batch Assignment:

$$ \sum_{b \in B} z_{job} = 1 \quad \forall j, o $$

Capacity Limit:

$$ \sum_{j,o} z_{job} \leq \text{cap}_m \quad \forall b \in B $$

Simultaneous Completion — All jobs in a batch complete together:

$$ C_{jo} = C_b \quad \text{if } z_{job} = 1 $$

Compatibility — Jobs in the same batch must have compatible recipes:

$$ z_{job} + z_{j'ob} \leq 1 \quad \text{if } \text{recipe}_j eq \text{recipe}_{j'} $$

3.3 Complexity

The batch scheduling subproblem is related to bin packing and is NP-hard .

4. Photolithography Scheduling

Photolithography (stepper/scanner tools) often forms the bottleneck workstation.

4.1 Characteristics

• Each product-layer combination requires a specific reticle
• Reticle changes take 10–30 minutes
• Setup time matrix: $s_{ij}$ = time to switch from product $i$ to product $j$

4.2 TSP-Like Formulation

Let $x_{ij} = 1$ if product $j$ immediately follows product $i$ in the schedule.

Objective — Minimize Total Setup Time:

$$ \min \sum_{i} \sum_{j} s_{ij} \cdot x_{ij} $$

Constraints:

$$ \sum_{j} x_{ij} = 1 \quad \forall i \quad \text{(exactly one successor)} $$

$$ \sum_{i} x_{ij} = 1 \quad \forall j \quad \text{(exactly one predecessor)} $$

Subtour Elimination (MTZ formulation):

$$ u_i - u_j + n \cdot x_{ij} \leq n - 1 \quad \forall i eq j $$

where $u_i$ is the position of product $i$ in the sequence.

5. Queueing Network Models

5.1 Open Queueing Network Approximation

Model each workstation $k$ as a queue:

Stability Condition:

$$ \rho_k < 1 \quad \forall k $$

5.2 Little's Law

$$ L = \lambda \cdot W $$

where:

• $L$ = average number in system (WIP)
• $\lambda$ = throughput
• $W$ = average time in system (cycle time)

Implication: $\text{Cycle Time} = \dfrac{\text{WIP}}{\text{Throughput}}$

5.3 Kingman's Formula (G/G/1 Approximation)

For a single-server queue with general arrival and service distributions:

$$ W_q \approx \frac{\rho}{1 - \rho} \cdot \frac{C_a^2 + C_s^2}{2} \cdot \frac{1}{\mu} $$

where:

• $C_a$ = coefficient of variation of inter-arrival times
• $C_s$ = coefficient of variation of service times
• $\rho$ = utilization
• $\mu$ = service rate

Key Insights:

• Waiting time explodes as $\rho \to 1$
• Variability multiplies waiting time (the $(C_a^2 + C_s^2)/2$ term)

5.4 Multi-Server Approximation (G/G/c)

For $c$ parallel servers (heavy traffic):

$$ W_q \approx \frac{\rho^{\sqrt{2(c+1)} - 1}}{c \cdot \mu \cdot (1 - \rho)} \cdot \frac{C_a^2 + C_s^2}{2} $$

5.5 Total Cycle Time

Summing over all $K$ workstations:

$$ CT = \sum_{k=1}^{K} \left( W_{q,k} + \frac{1}{\mu_k} \right) $$

5.6 Fluid Model Dynamics

Approximate WIP levels $w_k(t)$ as continuous:

$$ \frac{dw_k}{dt} = \lambda_k(t) - \mu_k(t) \cdot \mathbf{1}_{[w_k(t) > 0]} $$

5.7 Diffusion Approximation

In heavy traffic, WIP fluctuates around the fluid solution:

$$ W_k(t) \approx \bar{W}_k + \sigma_k \cdot B(t) $$

where $B(t)$ is standard Brownian motion.

6. Hierarchical Planning Framework

6.1 Lot Release Control (CONWIP)

Maintain constant WIP level $W^*$:

$$ \text{Release rate} = \text{min}\left(\text{Demand rate}, \; \frac{W^* - \text{Current WIP}}{\text{Target CT}}\right) $$

7. Dispatching Rules

7.1 Standard Rules

7.2 Composite Rule

$$ \text{Priority}_j = w_1 \cdot \text{slack}_j + w_2 \cdot p_j + w_3 \cdot Q_{\text{remaining}} + w_4 \cdot \mathbf{1}_{[\text{bottleneck}]} $$

where weights $w_1, w_2, w_3, w_4$ are tuned via simulation.

7.3 Critical Ratio

$$ CR_j = \frac{d_j - t}{\sum_{o' \geq o} p_{jo'}} $$

• $CR < 1$: Job is behind schedule (high priority)
• $CR = 1$: Job is on schedule
• $CR > 1$: Job is ahead of schedule

8. Decomposition Methods

8.1 Lagrangian Relaxation

Original Problem:

$$ \min \; f(x) \quad \text{s.t.} \quad g(x) \leq 0, \; h(x) = 0 $$

Relaxed Problem (dualize capacity constraints):

$$ L(\lambda) = \min_x \left\{ f(x) + \lambda^T g(x) \right\} $$

Subgradient Update:

$$ \lambda^{(k+1)} = \max\left(0, \; \lambda^{(k)} + \alpha_k \cdot g(x^{(k)})\right) $$

where $\alpha_k$ is the step size.

8.2 Benders Decomposition

Master Problem (integer variables):

$$ \min \; c^T x + \theta \quad \text{s.t.} \quad Ax \geq b, \; \theta \geq \text{cuts} $$

Subproblem (continuous variables, fixed $\bar{x}$):

$$ \min \; d^T y \quad \text{s.t.} \quad Wy \geq r - T\bar{x} $$

Benders Cut (from dual solution $\pi$):

$$ \theta \geq \pi^T (r - Tx) $$

8.3 Column Generation

Master Problem:

$$ \min \sum_{s \in S'} c_s \lambda_s \quad \text{s.t.} \quad \sum_{s \in S'} a_s \lambda_s = b $$

Pricing Subproblem:

$$ \min \; c_s - \pi^T a_s \quad \text{over feasible columns } s $$

Add column $s$ to $S'$ if reduced cost < 0.

9. Stochastic and Robust Optimization

9.1 Two-Stage Stochastic Program

$$ \min_{x} \; c^T x + \mathbb{E}_{\xi}\left[Q(x, \xi)\right] $$

where:

• $x$ = first-stage decisions (before uncertainty)
• $Q(x, \xi)$ = optimal recourse cost under scenario $\xi$

Scenario Approximation:

$$ \min_{x} \; c^T x + \frac{1}{N} \sum_{n=1}^{N} Q(x, \xi_n) $$

9.2 Robust Optimization

Uncertainty Set:

$$ \mathcal{U} = \left\{ p : |p - \bar{p}| \leq \Gamma \cdot \hat{p} \right\} $$

Robust Formulation:

$$ \min_x \max_{\xi \in \mathcal{U}} f(x, \xi) $$

Tractable Reformulation (for polyhedral uncertainty):

$$ \min_x \; c^T x + \Gamma \cdot \|d\|_1 \quad \text{s.t.} \quad Ax \geq b + Du $$

10. Machine Learning Approaches

10.1 Reinforcement Learning for Dispatching

MDP Formulation:

Q-Learning Update:

$$ Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \right] $$

Deep Q-Network (DQN):

$$ \mathcal{L}(\theta) = \mathbb{E}\left[ \left( r + \gamma \max_{a'} Q(s', a'; \theta^-) - Q(s, a; \theta) \right)^2 \right] $$

10.2 Graph Neural Networks

Represent fab as graph $G = (V, E)$:

• Nodes : Machines, buffers, lots
• Edges : Material flow, machine-buffer connections

Message Passing:

$$ h_v^{(l+1)} = \sigma \left( W^{(l)} \cdot \text{AGGREGATE}\left( \{ h_u^{(l)} : u \in \mathcal{N}(v) \} \right) \right) $$

11. Performance Metrics

11.1 Key Performance Indicators

11.2 Cycle Time Components

$$ CT = \underbrace{\sum_o p_o}_{\text{Raw Process Time}} + \underbrace{\sum_o W_{q,o}}_{\text{Queue Time}} + \underbrace{\sum_o s_o}_{\text{Setup Time}} + \underbrace{T_{\text{wait}}}_{\text{Batch Wait}} $$

11.3 X-Factor

$$ X = \frac{\text{Actual Cycle Time}}{\text{Raw Process Time}} $$

• Typical fab: $X \in [2, 4]$
• World-class: $X < 2$

11.4 Multi-Objective Pareto Analysis

ε-Constraint Method:

$$ \min f_1(x) \quad \text{s.t.} \quad f_2(x) \leq \epsilon_2, \; f_3(x) \leq \epsilon_3, \ldots $$

Vary $\epsilon$ to trace the Pareto frontier.

12. Computational Complexity

12.1 Complexity Results

12.2 Approximation Guarantees

For single-machine weighted completion time:

$$ \text{WSPT rule achieves} \quad \frac{OPT}{ALG} \geq \frac{1}{2} $$

For parallel machines (LPT rule, makespan):

$$ \frac{ALG}{OPT} \leq \frac{4}{3} - \frac{1}{3m} $$

Principles:

1. Variability is the enemy — Reducing $C_a$ and $C_s$ shrinks cycle time more than adding capacity

2. Bottleneck management dominates — Optimize the constraining resource; non-bottleneck optimization often has zero effect

3. WIP control matters — Lower WIP (via CONWIP or caps) reduces cycle time even if utilization drops slightly

4. Hierarchical decomposition is essential — No single model spans strategic to real-time decisions

5. Validation requires simulation — Analytical models provide insight; DES captures full complexity