應用和弦演算法求解兩階段混合式流程型工廠綁機問題

Scheduling Two-stage Hybrid Flowshops with Dedicated Machines by Harmony Search Algorithm

胡志育(Chi-yu Hu)

指導教授 ： 應國卿

國立臺北科技大學/管理學院/工業工程與管理研究所/碩士(2011年)

摘要

在現實環境中兩階段混合式流程型工廠是一種常見的生產型態，而綁機限制正是為近年來半導體製造廠裡生產流程日漸精密之下所產生的現象。在排程學術研究中，相關文獻十分稀少，故引發本研究探討此問題的動機。本研究主要在探討兩階段混合式流程型工廠綁機排程問題，其目標函數為最小化總完工時間，並提出一新型修正的和弦演算法(Revised Harmony Search)，以c語言來求解此問題，研究結果證實，本研究所提出之修正和弦演算法較現存之四種啟發式演算法為佳。因此，本研究所提出的RHS能迅速且穩定求得較佳的解。

關鍵字

綁機 ； 兩階段混合式流程型工廠 ； 和弦演算法

並列摘要

In real world, the two-stage hybrid flowshops scheduling problems are commonly encountered, and the dedicated machines constraint is a phenomenon which resulted from the delicate manufacturing process of semiconductor manufacturing industry. This research concerning the dedicated machines feature has been rarely investigated in the scheduling literature. So, this research focuses on this problem to discuss. So, the two-stage hybrid flowshops scheduling is quite an important issue. In this research, the author mainly probes the problem of two-stage hybrid flowshops with dedicated machines (TSHFDM), and the objective function of this research is to minimize the total completion time. This research compares with Yang’s benchmark test problems, using a revised harmony search (RHS) to find the solutions by C code. The computational results showed that the RHS outperformed the other four heuristics (GR, GS, H1, H2). Hence, the proposed RHS can provide a fast and stable, and better solution on the TSHFDM problem.

並列關鍵字

Dedicated Machines ； Two-stage Hybrid Flowshops ； Harmony Search

參考文獻

[1] R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, "Optimization and approximation in deterministic sequencing and scheduling: a survey," Annals of Discrete Mathematics, vol. 5, 1979, pp. 287-326.

[3] Richard Linn and Wei Zhang, "Hybrid flow shop scheduling: A survey," Computers & Industrial Engineering, vol. 37, 1999, pp. 57-61.

[4] J. N. D. Gupta and E. A. Tunc, "Schedules for a two-stage hybrid flowshop with parallel machines at the second stage," International Journal of Production Research, vol. 29, 1991, pp. 1489–1502.

[5] J. N. D. Gupta and E.A. Tunc, "Scheduling a two-stage hybrid flowshop with separable setup and removal times," European Journal of Operational Research, vol. 77, 1994, pp. 415–428.

[6] J. N. D. Gupta, A.M.A. Hariri and C.N. Potts, "Scheduling a two-stage hybrid flow shop with parallel machines at the first stage," Annals of Operations Research, vol. 69, 1997, pp. 171–191.