雙機流線型批次排程問題

A STUDY ON A TWO-MACHINES FLOWSHOP BATCH SCHEDULING PROBLEM WITH NON-IDENTICAL JOB SIZES

蔡仁皓(Jen-Hao Tsai)

國立虎尾科技大學/管理學院/工業工程與管理研究所/碩士(2007年)

摘要

半導體業在國內發展的相當迅速，而在預燒製程(burn-in)的過程中，常常會以批次處理機台(batch processing machine)來進行。本研究主要在探討雙機流線型(flow shop)批次排程問題並建構兩個混合整數規劃模式，並使用基因演算法(genetic algorithms，GA)及模擬退火法(simulated annealing，SA)來求解批次排程問題。其中工作的處理時間與大小(size)皆為已知，且工作有不相同的大小(size)，並以數個工作形成批次的方式在處理機台上加工，每個批次的大小不能超過機台本身所能處理的最大容量。批次的處理時間是以在同一批次之中所含工作之最長的處理時間定義為此批次的處理時間。本研究所建構的兩個混合整數規劃模式，分別是當兩機之間的暫存區容量(buffer capacity)為無限制與零的模式。目標是在如何將工作分配至批次內與安排批次到機台的工作順序，使得完工時間達到最小化(Minimum Makespan)目標。最後，將基因演算法、模擬退火法與電腦套裝軟體LINGO8.0版三者加以比較，由結果顯示，在小規模問題時，三者的求解能力差不多，但當問題規模變大時，基因演算法不管在求解品質或者計算時間上，皆優於模擬退火法與LINGO許多。

並列摘要

The domestic semiconductor industry expands rapidly, batch processing machines are commonly used in burn-in operations. This paper proposes two mixed integer formulation models to schedule batches of jobs on two machines in a flow shop. Then, GA and SA are applied to the batch scheduling problem. A set of jobs with known processing times and sizes has to be grouped, to form batches, in order to be processed on the batch processing machines. Each machine can process a batch as long as the total size of a batch is less than the machine capacity. The processing time of a batch is the longest processing time of all the jobs in that batch. Mixed integer formulation models are proposed when the buffer capacity is unlimited or zero. This research aims at minimizing the makespan for a batch processing machine. Random instances were used to test the effectiveness of the proposed approach. The results obtained from GA were compared with a SA approach and Lingo. The results indicate that the GA was able to arrive at better makespan with shorter run times.

參考文獻

13. 魏文鍇, 2003, 利用啟發式演算法求解工單式生產系統排程中時窗限制與釋放時間限制問題, 國立成功大學碩士論文 。

10. 湯璟聖, 2003, 動態彈性平行機群排程的討論, 中原大學碩士學位論文。

12. 錢明淦,1998, 遺傳演算法應用於具有多種資源組態及資源限制專案計畫排程問題之研究, 元智大學碩士論文。

1. 王惠梅, 2004, 動態批次機台排程問題之探討, 元智大學博士論文。

14. 韓駿逸, 2001, 基因演算法解算交貨時區限制零工型排程問題之效果分析, 元智大學碩士論文 。