利用斐氏網為基礎的啟發式演算法求解雙邊生產線平衡型一問題

Solving Two-sided Assembly Line Balance Type-I Problem by Using of a Petri Net-based Heuristic Algorithm

彭定國(Ting-Kuo Peng) ； 項衛中(Wei-Jung Shiang)

《技術學刊》 30卷2期 (2015/06) Pp. 119-134

摘要

為了因應市場上產品多元化的需求，並使生產設備與空間的使用效率達到極大，製造廠商通常會採用雙邊生產線的佈置。雙邊生產線平衡問題是屬於NP-Hard，其複雜的數學模式，往往透過諸如基因演算法、模擬退火法以及禁忌搜尋法（tabusearch,TS）等相關的演算法來進行求解。本研究提出一個以斐氏網為基礎的演算法來求解雙邊生產線平衡的型一問題。將作業任務的先後關係轉換成斐氏網模型，透過斐氏網中的啟動與觸發原理來決定可指派的作業任務，在給定工作站週期時間下，依據斐氏網中標記可轉移的情形與最小化工作站閒置原則，從前而後將作業任務指派到工作站中。本演算法利用Excel VBA來撰寫，並以實際案例來驗證演算法的有效性，使用者可輸入不同的週期時間，依此找出適當的工作站數目。

關鍵字

雙邊生產線平衡 ； 斐氏網 ； 啟發式演算法

並列摘要

In order to meet market demand for product diversification, the production efficiency of equipment as well as space, many manufacturers usually adopt a two-sided assembly line layout, especially for assembling large-size products, like automobiles, buses, trucks, and other large vehicles. Since the two-sided assembly line balance problem (TALBP) is a NP-hard problem, many heuristic algorithms were developed to solve this problem, such as genetic algorithm, simulated annealing, and Tabu search. In this study, a Petri net-based heuristic algorithm was proposed to solve the type-I TALBP (TALBP-I). First, this algorithm generates the Petri net model based on precedence diagram, and then makes an order of firing sequence of transitions. By analyzing the token movement of the Petri net model, the set of tasks can be assigned to proper workstations to minimize workstation numbers. The algorithm was coded in Excel VBA to provide a user-friendly interface, and was tested with benchmarks to show the efficiency of this algorithm.

並列關鍵字

two-sided assembly line balancing problem ； Petri net ； heuristic algorithms