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

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

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

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