以瀰集演算法求解流線型製造單元排程

A Memetic Algorithm Approach to Scheduling Flowshop Manufacturing Cell

潘冠銘

指導教授 ： 巫木誠

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

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

摘要

瀰集演算法是一種廣泛被使用拿來求解複雜空間搜尋問題的巨集啟發式演算法。對於各種問題，過去的研究往往著重在對於演算法進化部分的改善，本研究不同於以往的思維去嘗試一種新的研究議題，採用新的染色體表達法來改變瀰集演算法的績效。
本研究對於求解具有固定序列的流線型製造單元排程問題利用瀰集演算法搭配兩種不同的染色體表達法去進行比較；這兩種瀰集演算法具有相同的演算流程，但具有不同的染色體表達方式，一個是過去研究所使用的，本研究稱之為舊染色體表達法(Sold)；另一個則是使用Wu et al. (2011)所發明的，本研究將其稱為新染色體表達法(Snew)。經由大量的數據分析後發現本研究所使用的瀰集演算法搭配新染色體表達法(Memetic-Snew)大部分都優於瀰集演算法搭配舊染色體表達法(Memetic-Sold)。此結果顯示一個新的重要研究方向，利用巨集啟發式演算法於不同空間求解問題時，新的染色體表達法可以改善空間求解問題的績效。

關鍵字

瀰集演算法 ； 染色體表達法 ； 排程

並列摘要

The memetic algorithm, 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 the search mechanism 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 the memetic algorithm? A flowshop manufacturing cell scheduling problem with permutation is used as the problem context, and two memetic algorithms 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 Memetic-Sold and Memetic-Snew accordingly. Extensive numerical experiments reveal that Memetic-Snew mostly outperforms Memetic-Sold. This finding highlights an important new research track—exploring new solution representation schemes while applying meta-heuristic algorithms to various space-search problems.

並列關鍵字

Memetic Algorithm ； solution representation ； Scheduling

參考文獻

戴邦豪，「應用混合式染色體表達法於具順序相依家族整備時間之流線型製造單元排程」，國立交通大學工業工程與管理學系碩士論文，2010。

Abdelmola, A.I., Taboun, S.M., and Merchawi, S., 1998. Productivity Optimization of Cellular Manufacturing Systems. Computers industrial engineering, 35 (3-4), 403–406.

Bouabda, R., Jarboui, B., Eddaly, M., and Rebaı, A., 2011. A branch and bound enhanced genetic algorithm for scheduling a flowline manufacturing cell with sequence dependent family setup times. Computers & Operations Research, 38, 387–393.

Chen, J.S., Pan, C.H., and Wu, C.K., 2008. Hybrid tabu search for re-entrant permutation flow-shop scheduling problem. Expert Systems with Applications, 34, 1924–1930.

Chiang, T.C., Cheng, H.C., and Fu, L.C., 2010. A memetic algorithm for minimizing total weighted tardiness on parallel batch machines with incompatible job families and dynamic job arrival. Computers & Operations Research, 37, 2257–2269.