Resource Allocation Embedded Assembly Line Balancing Problem and Ant Colony Optimization Methods

本研究介紹含作業員選配的組裝線平衡問題，即在給定固定的工作站數下，一階段處理作業配置和分站以及作業員挑選和分配的任務。有別於傳統組裝線平衡問題，本研究的目標除了縮短組裝線的生產週期時間，同時降低作業員選配所引發的人事成本，並利用蟻拓優化演算法求解並詳細定義此問題的數學模型。本研究的單一目標優化模型參考兩個要項並使用當量因子，分別為生產週期時間和人事成本。在建構解的過程中，利用本研究所提出的動態更新開站時間和動態更新啟發值以完成最佳解的搜尋過程。本論文提出兩種建構解的方法，分別為RAF ACO求解法和LBF ACO求解法。RAF ACO求解法即為先建構作業員挑選和配置解，再建構組裝作業的配置和分站解；相反地，LBF ACO 求解法先解決組裝線平衡問題再處理資源分配問題。因此，每隻螞蟻都必須完成兩個任務並根據不同的方法而先後依序指派組裝作業到各個工作站和依序選配作業員到各個工作站。本研究提供機率計算的啟發值、生產週期時間的預測、動態更新開站時間和啟發值的設計並有不同的模式可選擇。本研究開發一軟體系統，RAELBP Solver，實作提出的求解方法和各項設計的模式進行範例測試並予以驗證。因應數據分析的需求，本研究針對所提出的問題實作一範例產生器，藉由組裝線平衡的標竿問題使得範例更加完整並能自動產生作業員範例。透過開發的範例產生器建立三個不同等級的範例問題並予以分析。每個範例問題需經過不同的求解模型測試，並按照不同目標式的選擇，即生產週期時間或人事成本做為數據分析的分類依據。數據驗證結果顯示所提出的求解方法皆能處理本研究問題且可以提供一組非臣服解供使用者作為選擇的參考。整體而言，LBF ACO 求解法相較於RAF ACO 求解法所得到的結果能涵蓋柏拉圖前緣面積較廣。This research introduces a resource allocation embedded assembly line balancing problem. The problem involves operations of task sequencing and grouping and operations of operator selection and assignment, for a given number of workstations. The goal of the problem is to minimize the cycle time of assembly line and the labor cost incurred from the operator assignments. The mathematical model is rigorously defined and ACO techniques for solving the problem are presented. A single objective optimization mode is adopted to accommodate the two primary evaluation terms, cycle time and labor cost, using weighting factors. For the solution construction, we propose a dynamic cycle time threshold and a dynamic heuristic value to guide the solution search toward the optima. This paper proposes two solution construction methods: the RAF ACO method deals with operations of operator selection and assignment first and then operations of assembly task sequencing and grouping; and conversely, the LBF ACO method deals with line balance related operations first, then the resource allocation related operations. Therefore, within these methods an ant is committed with two missions in different orders: (1) sequentially assign a list of assembly tasks to each workstation and (2) sequentially select and assign an operator to each workstation. Several operational options related to the evaluations of heuristic values use in probability calculation, estimation of cycle times, updates of cycle times and heuristic values and also proposed. A prototype system namely, RAELBP Solver, that implements the proposed methods is constructed for numerical tests and to verify the proposed methods. To facilitate numerical tests, a data generator for the introduced problem is developed by integrating the numerical data from line balance problems and automatically generate data about the operators. Three sample problems with different scales are therefore generated and used for the tests. Numerical results from different settings for different problems are separately compared against the objective values, and associations of cycle time and labor cost. Results show that the proposed methods are all able to solve the problems with different achievements of non-dominated solutions. In general, the LBAF ACO method covers a large area of Pareto frontier than that of the RAF ACO method