以模擬退火法求解流線型製造單元排程

A Simulated Annealing Approach To Scheduling Flowshop Manufacturing Cell

曾偉杰

指導教授 ： 巫木誠

國立交通大學/管理學院/工業工程與管理系所/碩士(2011年)

https://doi.org/10.6842/NCTU.2011.00213

摘要

模擬退火法是一種啟發式巨集演算法，目前已經被廣泛地運用在求解許多複雜的空間搜尋問題。在之前的研究，專注在如何應用或是提升模擬退火法本身演算法的精進。除了以前的研究議題之外，本研究進行了一個新的議題，一個新的染色體表達法機制應用在模擬退火法是否也能夠提升績效？
流線式製造單元排程問題是一種排成問題，而本論文以此問題為基準來探討兩種不同的染色體表達法應用在模擬退火法上的比較。這兩種方法在流程上是相同的，不同的是在染色體的表達方式上(稱為Sold 和 Snew)。Sold是以前的研究所發展出來的方法，而Snew是由巫木誠(2011)所發展出來的方法，因此這兩種演算法分別稱為SA-Sold和SA-Snew。
大量的實驗數據顯示出這兩種演算法在小和中的整備時間(SSU/MSU)情境下，有相同的解品質，然而在大的整備時間(LSU)下，SA-Snew相較於SA-Sold有更佳的解品質。這一項研究凸顯了一個重要的研究議題，新的染色體表達法運用在啟發式巨集演算法去求解問題，會有不同的結果。

關鍵字

模擬退火法 ； 表達法 ； 排程

並列摘要

Simulated Annealing (SA), a type of meta-heuristic algorithms, has been widely used in solving complex space-search problems. Most prior research focused on how to apply or enhance SA to various problems. Aside from the traditional track, this research examines a new research issue—Can the adoption of a new solution representation scheme improve the performance of SA? A scheduling problem called Flowshop Manufacturing Cell is used as the problem context, and two SAs are compared. The two algorithms, essentially the same in algorithmic flow, are distinct in using two different solution representation schemes (respectively called Sold and Snew). Noticeably, Sold was developed by prior studies and Snew is by Wu et al. (2011); the two algorithms are named SA-Sold and SA-Snew accordingly. Extensive numerical experiments reveal that the two algorithms performs equally well in small and medium setup time (SSU/MSU) scenarios. Yet, SA-Snew outperforms SA-Sold at large setup time (LSU) scenarios. This finding highlights an important new research track—exploring new solution representation schemes while applying meta-heuristic algorithms to various space-search problems.

並列關鍵字

Simulated Annealing ； solution representation ； scheduling

參考文獻

呂佳玟，應用基因演算法與家族式派工於傳輸整合步進機在小批量情境下之排程問題，國立交通大學，碩士論文，2009。

Cheng, J., Kise, H., and Matsumoto, H., 1997. A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem. European Journal of Operational Research, 96, 578-590.

Cheng,T.C.E. and Wang G., 1998. Batching and scheduling to minimize the makespan in the two-machine flowshop. IIE Transactions, 30, 447-453.

Franca, P.M., Gupta, J.N.D., Mendes, A.S., Moscato, P., and Veltink, K.J., 2005. Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups. Computers & Industrial Engineering 48, 491-506.

Hendizadeh, S.H., Hamidreza, F., Mansouri, S.A., Gupta, J.N.D., and ElMekkawy, T.Y., 2008. Meta-heuristics for scheduling a flowline manufacturing cell with sequence dependent family setup times. Int. J. Production Economics 111, 593-605.