Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics

I. Lin Wang, Yi Chi Wang, Chih Wei Chen

研究成果: Article同行評審

34 引文 斯高帕斯(Scopus)

摘要

We investigate a difficult scheduling problem in a semiconductor manufacturing process that seeks to minimize the number of tardy jobs and makespan with sequence-dependent setup time, release time, due dates and tool constraints. We propose a mixed integer programming (MIP) formulation which treats tardy jobs as soft constraints so that our objective seeks the minimum weighted sum of makespan and heavily penalized tardy jobs. Although our polynomial-sized MIP formulation can correctly model this scheduling problem, it is so difficult that even a feasible solution can not be calculated efficiently for small-scale problems. We then propose a technique to estimate the upper bound for the number of jobs processed by a machine, and use it to effectively reduce the size of the MIP formulation. In order to handle real-world large-scale scheduling problems, we propose an efficient dispatching rule that assigns a job of the earliest due date to a machine with least recipe changeover (EDDLC) and try to re-optimize the solution by local search heuristics which involves interchange, translocation and transposition between assigned jobs. Our computational experiments indicate that EDDLC and our proposed reoptimization techniques are very efficient and effective. In particular, our method usually gives solutions very close to the exact optimum for smaller scheduling problems, and calculates good solutions for scheduling up to 200 jobs on 40 machines within 10 min.

原文English
頁(從 - 到)343-366
頁數24
期刊Flexible Services and Manufacturing Journal
25
發行號3
DOIs
出版狀態Published - 2013 9月

All Science Journal Classification (ASJC) codes

  • 管理科學與經營研究
  • 工業與製造工程

指紋

深入研究「Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics」主題。共同形成了獨特的指紋。

引用此