Photolithography is a process used by semi-conductor manufacturers to transfer the geometric pattern of a computer chip on a wafer. This is done by putting UV light through a photomask on a light-sensitive layer on top of the wafer. If certain parts of the wafer do not need to be exposed, blades are moved in to block the UV light. Moving the blades is a time consuming process. Since it often influences the total processing time of a wafer in the lithography machine, minimizing the distance will reduce processing time.

We formulate this problem as an adjusted form of the traveling salesman problem; the scenario a priori TSP problem. In the a priori TSP problem, we are given a list of subsets of the vertices, called scenarios, along with a probability for each scenario. Given a tour on all vertices, the resulting tour for a given scenario is obtained by restricting the solution to the vertices of the scenario. The goal is to find a tour on all vertices that minimizes the expected length of the resulting restricted tour.

We show some complexity and approximation results for the problem. We will also look at the computational results from a real-life setting.