應用顏色派翠網路與最小展開樹探討雙邊生產線平衡問題

Applying Colored Petri Net and Minimal Spanning Tree for Two-sided Assembly Line Balancing Problem

許佑萱(You-Xuan Xu)

指導教授 ： 魏乃捷

共同指導教授 ： 薄喬萍(Chiao-Pin Bao)

義守大學/管理學院/工業管理學系/碩士(2015年)

https://doi.org/10.6343/ISU.2015.00165

摘要

雙邊生產線平衡是屬於一NP-hard的組合優化問題，大多以演算法來求解，本研究發展一結合顏色派翠網路與最小展開樹來求解雙邊生產線平衡問題之型一問題，本研究的方法分成三個步驟，首先利用派翠網路的事件矩陣圖去計算任務指派的路徑，進而從上一步驟所得到可以指派的任務，利用顏色派翠網路之顏色的改變來判斷指派的條件是否滿足，最後再利用最小展開樹來協助任務的遴選，遴選的原則是以任務時間最短為優先指派，重複上述步驟直到所有任務皆指派到工作站為止。由於整個演算過程中會透過圖表的方式，因此可增加演算的透明度。文中最後會以過去文獻範例的比較，發現本研究可獲致一致性的結果甚至更佳。研究結果顯示顏色派翠網路及最小展開樹之演算法於雙邊生產線平衡問題之型一問題確實能求得工作位置最小化及平衡效率最大化。

關鍵字

雙邊生產線平衡問題 ； 顏色派翠網路 ； 最小展開樹

並列摘要

Two-sided assembly line balancing problem (TALBP) belongs to an optimum combination NP-hard problem and mostly, it is solved by various algorithms. Thus, this research proposes colored petri net (CPN) and minimal spanning tree to solve type I problem of TALBP. The proposed method is divided into 3 steps. The first step is to build a reachability tree chart to display the possible tasks order assignment. The second step adopts the color firing mechanism depending on where the colored conditions are satisfied. In order to select the suitable task to fire (assign), the final step applies minimal spanning tree in assisting efficiently task selection based on the least time prioritized rule. The above steps will be repeated until all the tasks are assigned. As the whole assignment is processed in graphical and paradigm manner, this will be helpful in reducing the complexity of calculation burden. The comparison results show that the proposed method is consistent or even favorable over the examples from literature. The results show that colored petri net and minimal spanning tree in two-sided assembly line balancing problem (Type – I) can obtaine minimized working position and maximized balance efficiency.

並列關鍵字

Two-sided Assembly Line Balancing Problem(TALBP) ； Colored Petri Net(CPN) ； Minimal Spanning Tree(MST)

參考文獻

葉丁鴻、顏伯蒼(2012)，利用數學規劃模式找出在有雙邊同時作業任務時的雙邊生產線平衡問題最佳解，創新研發學刊，8(2)，110-120。

藍俊雄、黃堯申、張耿睿、余玟慧(2011)，探討JIT生產與控制污染下雙邊生產線平衡之型三問題，環境與管理研究，12(1)，24-35。

陳涵櫻(2002)，以Coloured Petri Net為基礎的低壓工業配線電路分析，國立臺灣師範大學資訊教育學系未出版碩士論文。

Hu, X., Wu, E., Bao, J., & Jin, Y. (2010), A branch-and-bound algorithm to minimize the line length of a two-sided assembly line, European Journal of Operational Research, 206(3), pp.703-707.

Jensen, K., (1994), An introduction to the theoretical aspects of coloured petri nets, computer science, 803, pp.230-272.