• Flexciton

A review of the two-phase approach to photolithography production scheduling

Reviewing technology literature is a common practice when developing a new approach to solving an existing problem. James Adamson, a Senior Optimization Engineer at Flexciton, has recently reviewed several technical papers on photolithography scheduling, one of which he found particularly interesting.

The reticle challenge

Photolithography is the cutting edge of semiconductor manufacturing and as a result, requires the most complex and expensive equipment to run and maintain. Reticles (also known as photomasks), must be prepared and loaded into litho tools before the wafers can process. These fragile masks are extremely expensive (in the region of $100k or more [Weber 2006]), making them a scarce resource.

Wafers require specific reticles for their individual process step. Therefore fab operators need to ensure that the correct reticles are at the correct tools on time in order to keep production KPIs such as wafer throughput and cycle time optimal. While reticles can be moved between tools, this takes time and considering how fragile these masks are, the movement needs to be minimised as much as possible. If wafer scheduling wasn’t already difficult enough, we now have to wrestle with reticle scheduling too.

The approach review

The paper “A Practical Two-Phase Approach to Scheduling of Photolithography Production” by Andy Ham and Myesonig Cho was published in 2015. The authors present an approach that is based on the observation that most semiconductor manufacturing companies are still using real-time dispatching (RTD) systems to make last-second dispatching decisions in the fab. RTD has the advantage of being familiar and relatively understandable whilst also being fast computationally. In contrast, some optimisation-based approaches, particularly for photolithography, can struggle to scale up to industrial-scale problems. The authors' approach exploit the idea that an exact schedule for the next several hours is not necessarily needed and that RTD will ultimately be responsible for the final dispatch decision.

They propose a two-stage approach that integrates a simple heuristic (designed to mimic a fab’s RTD system) with mixed-integer programming (MIP):

  1. Stage 1 - Upper-stage (Assignment): MIP is used to guide the high-level lot-to-machine and reticle-to-machine assignments. Explicit timing of lots and reticles is ignored.

  2. Stage 2 - Lower-stage (Sequencing & Timing): The finer-detailed sequencing (and therefore timing) of lots according to those assignments is provided by the heuristic.

The two stages are then tied together in an iterative fashion. A set number of lots are scheduled in each iteration of the two stages. The algorithm then repeats from Stage 1 with new additional lots and keeps iterating until all lots are scheduled.

Stage 1

A MIP approach is proposed to solve the assignment problem in the first stage. Two primary decision variables are used:

  • A variable that allocates a reticle to a machine

  • A variable that allocates a reticle to a lot on a machine

The model does not account for the explicit timing of lots on their allocated machines. Therefore it cannot prescribe a sequence of lots or reticles on the machines. It just indicates that they will be scheduled on this machine at some point. The model requires that all lots are assigned to a machine and a reticle. Finally, the model measures the completion time of each machine as a function of the processing time of all lots allocated to the machine, rather than explicitly deciding the order of each lot on the machine.

Multiple objectives are used to achieve the trade-off between reticle movements, cycle times, and machine load balancing:

  1. Minimise completion time; the end of the last lot’s process

  2. Minimise the difference between the earliest and latest machine completion times. This aims to achieve load balancing across machines

  3. Minimise total machine underachievement, where underachievement is the gap between the total processing time on a machine and the average total processing time over all machines.

Stage 2

Sequencing decisions are handled by an RTD system, where the manufacturer’s custom business rules can be applied; however, the lot-reticle-machine assignment decisions are fixed. This reduces the scope of the decision-making that RTD must make. The authors highlight the benefit of explainability with this two-stage approach. When questioning assignment decisions, the assignment model should be explored, whereas when questioning sequencing decisions, RTD should be investigated.

This practical approach was shown to solve reasonable problem sizes (500 lots, up to 800 reticles, 30 machines) in 2-4 minutes. They managed to reduce cycle times by 3%, on average, and, particularly interestingly, reticle movements by up to 40% when compared to standalone RTD.

Flexciton’s View

Although the model does have some shortcomings, as outlined above, the practicality of the approach makes it a strong candidate for production-size scheduling as very few studies have been able to effectively handle industrial problem sizes for photolithography tools. The reduction in reticle movements achieved, in particular, cannot be ignored.

However, with the notion of time largely ignored in the assignment model, the approach outlined is certainly simplistic.

There are a number of factors not considered in the model, including:

  • The effect of batching decisions on processing times of the lots. For example, if 5 lots could be assigned to machine A as a single batch, and 5 different lots were assigned to machine B in five unique batches, then the assignment model would consider these cases as having equal total processing times (which is unlikely to be true).

  • The sequencing (and therefore timing) of reticles on machines.

  • The batching of reticles into “pods”; a container of reticles for easy and safe transportation around the fab and within lithography machines such that they can’t always be separated

  • How high priority wafers are handled in relation to lot-reticle-machine assignments

  • Accounting for periods of downtime or machine unavailability, which would contradict with the aim of achieving machine load balancing.

Flexciton’s Way

At Flexciton, we schedule a variety of photolithography tools as part of our optimisation engine. Our hybrid optimization-based solution strategy is therefore capable of handling all the intricacies of a wafer fab simultaneously, such as the issues described in the previous section;

  • modelling photolithography tools that require pods,

  • priority lots,

  • batching tools with variable processing times based on the batch, and

  • machine unavailability.

Not only do we model these complexities, but we also succeed in achieving high-quality schedules in little computation time.

The user is given the option of controlling various relative priorities of the lots, in addition to deciding the relative importance of KPIs such as reticle movements vs lots’ cycle time. The flexibility of an optimisation approach that considers all of the advanced photolithography constraints combined with a self-tuning model that has limited tuning parameters is what makes our engine highly attractive as a semiconductor scheduler.


1) Weber, C.M; Berglund, C.N.; Gabella, P. (13 November 2006). "Mask Cost and Profitability in Photomask Manufacturing: An Empirical Analysis". IEEE Transactions on Semiconductor Manufacturing. 19 (4). doi:10.1109/TSM.2006.883577;