Solving the Mask Data Preparation Scheduling Problem Using Meta-Heuristics

Abstract

Mask data preparation (MDP) is a part of the mask data process for fabricating semiconductors, and its importance has commonly been neglected. This paper proposes an integer linear programming model and two meta-heuristics, a genetic algorithm (GA) and simulated annealing (SA), for solving the MDP scheduling problem (MDPSP). The proposed meta-heuristics are empirically evaluated using 768 simulation instances of MDPSP based on the characteristics of a real technology company and compared with the most commonly used first-come, first-served method. The experimental results reveal that the proposed GA and SA algorithms can critically improve the manufacturing schedule for semiconductor factories.

Keywords

• Scheduling
• integer linear programming
• mask data preparation
• meta-heuristics
• genetic algorithm
• simulated annealing