以啟發式演算法求解最小化總完成時間之流程型工廠排程問題-以某TFT-LCD公司主生產排程為例

A Heuristic Algorithm for Makespan Minimization of a Flow Shop Scheduling Problem - A Study on Master Production Schedule in TFT-LCD Company

葉姵君(Pei-Ghun Yeh)

指導教授 ： 蘇玲慧

中原大學/電機資訊學院/工業與系統工程研究所/碩士(2013年)

https://doi.org/10.6840/cycu201300357

摘要

本研究主要在探討面板產業之主生產排程，主要生產型態屬於流程型工廠之平行機台生產排程問題，其目標為使機台閒置時間最小化及生產之最大完工時間最小化。本研究提出一啟發式演算法以快速求得一滿意的解，並作實驗分析Nawaz演算法與CDS演算法比較以驗證啟發式演算法的效益。
就實驗的結果以時間來看，所提出的新啟發式演算法相較於Nawaz演算法及CDS演算法相互比較，最小總完工時間與Nawaz演算法有相同效益皆為792秒，相對於CDS演算法的最小總完工時間810秒則勝了18秒。
然而以演算法的方法來進行比較，卻發現當利用Nawaz演算法求解最佳訂單排序時，卻因為求解的過程中因為遇到太多相同結果增加了迭代次數而必須搜尋更多的解，反觀利用新啟發式演算法時，若在使用Nawaz演算法遇到相同解時，改以CDS演算法求出最適合解接續求得最終結果，則可省略許多迭代次數增加所產生的求解時間，故本研究所提出的啟發式演算法是有效率的。

關鍵字

啟發式演算法 ； 面板產業 ； 流程型工廠 ； 平行機台生產排程

並列摘要

The main purpose of this thesis is to solve the flow shop scheduling problems in LCD manufacturing company. A heuristic algorithm is proposed to minimize both the idle time of machines and makespan. In order to evaluate the effectiveness of the heuristic, we compare it with Nawaz heuristic and CDS heuristic. Numerical experiments show that the heuristic provides a satisfactory result.
To compare each algorithm by minimum makespan, the result of experimentation shows that the new heuristic algorithm is the same as Nawaz algorithm (both 792sec), and is 18sec faster than CDS algorithm (810sec).
But in the progress by using Nawaz heuristic to calculate the best order scheduling, iterations increased because of the numerous equivalent results. On the contrary, new heuristic algorithm offers a more effective way by using CDS heuristic to replace Nawaz heuristic when the equivalent result appears, and earn the best result. In short, new heuristic algorithm is proved to be efficient by decreasing of iterations and minimum makespan.

並列關鍵字

Scheduling ； Flowshop ； TFT-LCD ； Heuristic Algorithm ； Parallel

參考文獻

【12】 林正超，等效平行機台在機台限制且完工期限下總完工時間最小化排程問題，中原大學工業工程學系，碩士論文，2007.

【13】 郭建男，基因演算法應用於面板產業cell製程後段之研究-以H公司為例，國立成功大學，碩士論文，2009.

【14】 黃宇翔，TFT-LCD產業多能工技術員最適化指派問題之研究，國立成功

【4】 Campbell, H.G., Dudek, R.A. and Smith, M.L. A heuristic algorithm

【1】 Johnson, S. M., Optimal two and three stage production schedules with set-up time included, Naval Research Quarterly, pp.61-68. (1954)