Provably Good Max–Min- m -Neighbor-TSP-Based Subfield Scheduling for Electron-Beam Photomask Fabrication

• Published in: IEEE transactions on very large scale integration (VLSI) systems 2018-02, Vol.26 (2), p.378-391
• Main Authors: Lin, Zhi-Wen, Fang, Shao-Yun, Chang, Yao-Wen, Rao, Wei-Cheng, Kuan, Chieh-Hsiung
• Format: Article
• Language: English
• Subjects: Algorithms; design; Distortion; electron beam lithography (EBL); Electron beams; Heating systems; Job shop scheduling; manufacturability; Scheduling algorithms; subfield scheduling; Throughput; Writing
• ISSN: 1063-8210; 1557-9999
• DOI: 10.1109/TVLSI.2017.2761850

Electron beam lithography (EBL) has been used for high-resolution photomask fabrication; its successive heating process in a certain region, however, may cause critical dimension (CD) distortion. As a result, subfield scheduling, which reorders a sequence of subfields in the writing process, is desirable to avoid the heating problem and thus CD distortion. To consider longer range heat dissipation, this paper models a subfield scheduling problem with blocked region consideration as a constrained max-min m -neighbor traveling salesman problem (called constrained m -nTSP). To solve the constrained m -nTSP which is NP-complete in general, we decompose a constrained m -nTSP into subproblems conforming to a special case with points on two parallel lines, solve each of them with a provably good linear-time approximation algorithm, and merge them into a complete scheduling solution. In particular, our algorithm can also minimize the distances between successive subfields to alleviate the throughput degradation of EBL writing due to moving a writing head, while minimizing the heating problem. Average reductions of 10% in the maximum temperature and 14% in the distances between successive subfields over the state-of-the-art work can be achieved.