多產品U型組裝線平衡/投料問題的蟻軍優化求解法

Abstract

本研究針對多產品U型組裝線平衡/投料問題提出了蟻軍優化求解法，以一階段的求解方法同時處理作業配置和投料排序的問題，並詳細定義此種問題的數學模式。求解目標是在適當配置各工作站的組裝作業和投料順序之下得到：(1) 最小化生產週程時間及(2) 最小化絕對工作量偏差，並深入探討此兩種目標式的求解效果。本研究研擬兩種組裝模式的生產情形：(1) 組裝線的各組裝作業依照投料順序個別組裝不同的產品及(2) 相同工作站內的相鄰組裝作業共同組裝相同的產品。本研究提出蟻軍優化求解法，將蟻軍仿效為三種能力不同的部隊，評估三種不同的啟發式值以引導蟻兵建構作業配置解。每隻螞蟻必須先依照組裝作業的先後執行順序關係建置不違反限制的作業配置解以決定各工作站內須執行的組裝作業，再建置投料順序解以完成求解步驟。本研究使用擴大手法增加蟻軍的求解數，並使用優加劣減擇段系統費洛蒙更新方式，完成最佳解的搜尋過程。本研究開發一軟體系統實作提出的求解模式和啟發項，並對多個範例問題進行測試。數據驗證結果顯示，使用最小化絕對工作量偏差作為優化目標相較於使用最小化生產週程時間作為優化目標是無法提升組裝線的生產效能。另外，本研究所提出的蟻軍優化求解法相較於其他相關此問題的求解法可得到較好的結果。

The mathematical model of the mixed-model U-shaped assembly line balancing problem is first rigorously defined in this thesis. This research proposes an Ant Colony Optimization (ACO) method for the tasks of line balancing and model sequencing involved in the problem. The pitfall and fitness for the objective functions using the minimum cycle time (CT) and the absolute deviation of workloads (ADW) are discussed. Two operation scenarios are simulated for the assembly line to determine the cycle times of all of the subcycles: (1) each task assigned to a workstation is processing on an individual model instance, and (2) successive tasks assigned to a workstation are processing on the same model instance. An ant platoon consisting of three squads with different heuristic value evaluations is proposed to guide the solution construction for line balancing. The first task for an ant is to construct a sequence of assembly tasks subject to the precedence constraints and create workstation one after the other to host the tasks. The second task is to construct a model sequence. Our method uses a solution set augmentation technique to enlarge the number of solutions and then adopts the segment-based pheromone update strategy from the segment discriminated ant system (SDAS). A software prototype system is developed to implement the proposed method. Several numerical tests are conducted on benchmarks to evaluate the performance of the proposed method. Numerical results show that the ADW objective function, compared with the one with CT, is unable to maximize the line efficiency. In addition, the proposed ACO method significantly outperforms the existing solving algorithms in solving the discussed problems.