門檻值搜尋法求解含完工期限下多目標彈性零工型排程問題

Using Threshold Accepting Algorithms to Solve Multi-Objective Flexible Job Shop Scheduling Problems

蘇海興(Hai-Hsing Su)

指導教授 ： 徐旭昇

元智大學/工程學院/工業工程與管理學系/碩士(2011年)

摘要

從製造業的實際觀點，一個好的生產排程規劃，應該要有多方面的考量，包括降低交貨延遲時間或件數、生產效率提升、減少生產設備磨耗與怠工時間、降低半成品之存貨成本等等。彈性零工型生產方式，符合產品少量多樣化市場需求之情況，為現今許多科技產品生產型態，故本研究就多目標彈性零工型生產排程問題加以探討。
　　本研究延續Kacem et al. (2002)所提之彈性零工型生產排程問題，但在目標設定上有些改變，將生產總完工時間(makespan)改為硬性目標，有期限；其餘三個模式目標分別為所有機台總加工時間(total machine workload)、瓶頸機台加工時間(critical machine workload)以及總延遲時間(total tardiness)。
　　本研究編碼方式採用上層為作業順序，下層為作業-機台指派，解碼則使用分層式方法，在給定下層作業-機台指派後再去求解各機台最佳排程。之前學者使用的演算法包括基因演算法、混合粒子群最佳化(PSO)與模擬退火(SA)或禁制搜尋法(TS)等，大多使用權重式演算法求解多目標問題，鮮少使用柏拉圖概念去求解。本研究採用門檻值接受法為演算法架構，除使用權重目標值之接受法則外，另採用三種柏拉圖概念接受法則，分別為(1)負理想解距離比值、(2) hypervolumn 比值、以及(3)正負理想解之相對距離比值。除了主體門檻值接受法，本研究中另在演算法結尾加入路徑連結法進一步改善所得之解，以及加在求解過程最後的第二階段加強求解法再改善所得之解。
實驗中的測試基本題有五題，含部分彈性 (8 × 8)、完全彈性 (10 × 10)、完全彈性和有到達時間的 (4 × 5)、完全彈性和有到達時間的 (10 × 7) 以及完全彈性和有到達時間的 (15 × 10)，每題有五種不同的交期參數因子設定，共產生25題。經過本研究的三個實驗後，從實驗結果中可以發現，門檻接受法用柏拉圖概念之(2) hypervolumn 比值接受法則所得的結果比較佳，以及加入路徑連結法和第二階段加強求解法的確可以改善求解品質，顯示路徑連結法和第二階段加強求解法是有可行性。此外，本研究將數據結果與之前文獻中的數據互相比較，在三目標皆相同的文獻中，對於大部分測試題都有找到較佳的解，而在兩目標相同的文獻，對於不同大小的測試題都有找到不錯兩目標值的解，代表本研究演算法和區域搜尋法的求解架構是有可行性。

關鍵字

多目標最佳化 ； 彈性零工型生產排程 ； 門檻值接受法 ； 柏拉圖概念 ； 區域改善法

並列摘要

Nowadays, in the highly competitive marketplace, product orders of low volume and high variety types have been increasing in demand. Flexible Job shop scheduling (FJSS) is one of the most popular manufacturing optimization models that fit this market trend. From a practical perspective of the manufacturing industry, management goals in production scheduling are often multi-faceted. In this research, we consider the following criteria: (1) production makespan; (2) total tardiness; (3) total machine workload; (4) critical machine workload. The first criterion, which reflects the level of system utilization, will be specified as a deadline constraint in our model. The remaining three criteria will be specified as the model objectives. The model is built to find a schedule that simultaneously optimizes customers’ satisfaction on delivery due date, as well as efficient and balanced use of machines.
This multi-objective FJSS (MO-FJSS) follows the model by Kacem et al. (2002), except that the first model objective is altered. In our model, the production makespan is a model constraint instead of an objective, and this objective is replaced with total tardiness. The new MO-FJSS is still strongly NP-hard. In this research, we propose several threshold-accepting (TA) algorithms, in which the fitness is evaluated using aggregation-based and Pareto-based methods. In aggregation approach, 20 evenly distributed weighted sum objectives are used. In Pareto-based approach, three fitness measures are used: (1) nadir distance, (2) relative ratio of distances from the current solution to nadir solution and to utopian solutions in the objective space, and (3) hyper-volume.
The TA algorithm consists of three phases: normal search, path-relinking, and post-optimization. In the normal search phase, an external archive is constructed using the standard TA algorithm. The aforementioned fitness is used to determine whether a neighborhood solution can be accepted as the new current solution, and is qualified to compete for an archive position. Afterwards, path-relinking is applied using the archive solutions to refine solution quality. Finally, an enhanced two-stage local search, with the first stage on two machine-workload objectives and the second stage on total tardiness, is applied to obtain the final archive solutions.
Computational experiments are performed to evaluate the four TA algorithms using 25 instances generated according to Kacem et al. (2002) and Lee and Pinedo (1997). The results indicate that the aggregation approach and hyper-volume approach are superior in terms of proximity and diversity measures. In addition, the path relinking phase and enhanced search phase can effectively improve the archive solution quality. Our experimental results also show that the TA algorithms produce new reference Pareto optimal solutions due to better performance on the two machine work-load objectives, when compared to other published results of solving the instances by Kacem et al.

並列關鍵字

local search ； Multi-objective combinatorial optimization ； flexible job shop scheduling ； threshold accepting ； Pareto optimality

參考文獻

卓裕仁與朱佑旌，「兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問

黃文洲，「演化式演算法於多目標彈性零工型排程問題之研究」，元智大

陳仲豪，「應用時窗離散策略與可回溯式門檻接受法求解VRPBTW問題之研

呂泓儒，「以改良型可回溯式門檻接受法求解回程取貨車輛路線問題之

Azardoost EB, Imanipour N. (2011) A hybrid algorithm for multi objective flexible