Title

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

Translated Titles

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

Authors

葉姵君

Key Words

啟發式演算法 ; 面板產業 ; 流程型工廠 ; 平行機台生產排程 ; Scheduling ; Flowshop ; TFT-LCD ; Heuristic Algorithm ; Parallel

PublicationName

中原大學工業與系統工程研究所學位論文

Volume or Term/Year and Month of Publication

2013年

Academic Degree Category

碩士

Advisor

蘇玲慧

Content Language

繁體中文

Chinese Abstract

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

English Abstract

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.

Topic Category 電機資訊學院 > 工業與系統工程研究所
工程學 > 工程學總論
Reference
  1. 【1】 Johnson, S. M., Optimal two and three stage production schedules with set-up time included, Naval Research Quarterly, pp.61-68. (1954)
    連結:
  2. 【2】 Palmer, D.S., Sequencing jobs through a multiple-stage process in the minimum total time – A Quick Method of Obtaining a Near Optimum, Operational Research Quarterly,16, pp.101-107. (1965)
    連結:
  3. 【3】 Ignall, E., and Schrage,L.E., Application of branch and bound technique to the some flow-shop problem, Operations Research,Vol.13, pp.400-412,1965. (1965)
    連結:
  4. 【4】 Campbell, H.G., Dudek, R.A. and Smith, M.L. A heuristic algorithm
    連結:
  5. for the n-job m-machine sequencing problem. Management Science, 16,
    連結:
  6. pp.630-637. (1970)
    連結:
  7. 【5】 Gupta, J.N.D., A Functional Heuristic Algorithm for the Flowshop Scheduling Problem, Operations Research Quarterly, 22, pp.39-47. (1971)
    連結:
  8. 【6】 Graves, S. C., A review of production scheduling, Operations Research, 29(4), pp.646-675. (1981)
    連結:
  9. 【7】 Nawaz, M., A heuristic algorithm for the M-Machine, N job flow-shop sequencing problem. Management Science, 11(1), 91-95. (1983)
    連結:
  10. 【12】 林正超,等效平行機台在機台限制且完工期限下總完工時間最小化排程問題,中原大學工業工程學系,碩士論文,2007.
    連結:
  11. 【13】 郭建男,基因演算法應用於面板產業cell製程後段之研究-以H公司為例,國立成功大學,碩士論文,2009.
    連結:
  12. 【14】 黃宇翔,TFT-LCD產業多能工技術員最適化指派問題之研究,國立成功
    連結:
  13. 【8】 陳建良,排程概述,機械工業雜誌,pp.122-133,1995.
  14. 【9】 游淑晴,黃光區關鍵層機台限制機台指派投料與派工法則探討,國立清華
  15. 大學工業工程與工程管理研究所,碩士論文,2003.
  16. 【10】 黃建中,多廠區規劃與排程-以TFT-LCD 產業為例,國立清華大學工業工程與工程管理學系,碩士論文,2003.
  17. 【11】 陳恩齊,多廠區之推式生產規劃與排程-以TFT-LCD 面板產業為例,
  18. 國立清華大學工業工程與工程管理學系,碩士論文,2004.
  19. 大學,碩士論文,2010.
  20. 【15】 莊惟翔、林晹桂,考慮有中斷點的學習效應下等速率平行機之排程問題,
  21. 科技整合管理研討會,逢甲大學工業工程與系統管理學系,2012.
  22. 【16】 曾心珮、林俊逸,工件大小不一致單一批次機器之排程問題,科技整合
  23. 管理研討會,長庚大學資訊管理學系,2012.