Hybrid decomposition heuristics for solving large-scale scheduling problems in semiconductor wafer fabrication

Most shop-floor scheduling policies used in practice rely on dispatching, making use of only local information at individual workcenters. However, in semiconductor manufacturing environments, we have access to real-time shop-floor status information for the entire facility. In these complex facilities, there would appear to be significant potential for improved schedules by considering global shop information and using optimization-based heuristics. To this end, we propose a rolling horizon (RH) heuristic that decomposes the shop into smaller subproblems that can be solved sequentially over time using a workcenter-based decomposition heuristic. We develop test instances for evaluating our heuristic using a simulation model of an industrial facility. The results demonstrate that the proposed heuristic yields better schedules than the dispatching rules in the vast majority of test instances with reasonable computational effort.