- 學位論文
模糊多目標非相關平行機台排程交期滿意度最大化問題解算之研究
Solving Fuzzy Bi-Objective Unrelated Parallel Machine Scheduling Problems with Flexible Constraints on Due Dates
摘要
本研究以模糊理論為工具探討含不確定性參數之兩目標不相關平行機台排程問題。在實務上排程問題之工件處理時間、交期等往往參雜一些不確定性因素諸如人為因素、原料未能及時供應、機台故障、或資訊不足，而使得對工件處理時間難以精確估算(imprecision)；同時在實際上，上下游廠商對預設交期延遲時常是有著某種程度之容忍，同時決策者考量訂單生產排程不只單一目標。若決策者偏好對這些目標的達成度以主觀性滿意度來衡量，模糊多目標最佳化模式便是解決決策者問題的較佳選擇方法。在本研究中，問題兩目標分別為最大化平均工件延遲時間滿意度與最大化不算延遲工件數之比例，所提演算法包括權重式多目標模擬退火法、權重式多目標禁制搜尋法、與柏拉圖式多目標禁制搜尋法。 研究測試題產生方式參考Lee and Pinedo (1997)，以交期寬鬆因子與交期範圍因子為參數，依題目大小，各產生五題測試題。兩種測試題大小分別為：100（工件）x 5（機台）、200 x 10。演算法效果量測以generational distance (GD)、Pareto fronts distribution、以及Hypervolumn (HV)為之。實驗結果發現權重式多目標禁制搜尋法之求解效果較佳，但所花之求解時間也較長。 實驗使用兩種不同初始解進行比較，產生的方式分為最短處理時間法(SPT)及利用GRASP產生兩種不同的初始解，實驗結果發現利用最短處理時間法(SPT)之求解效果較佳。使用兩種工件滿意度的量測指標分為可能性測量 (possibility measure) 以及面積計算法 (area of intersection)，經過實驗所產生之結果顯示，可能性測量所得到的數值較面積計算法高，但演算法所求得之結果趨勢相同
並列摘要
This thesis studies unrelated parallel machine scheduling problems (UPMSP) that consider uncertainty on job processing data and job due dates, and have two simultaneous maximization objectives – average satisfaction of job tardiness and average satisfaction of the number of tardy jobs. Both objectives are concerned with the manufacturer’s performance on customer delivery. When dealing with uncertainty, fuzzy set theory may provide an acceptable compromise between expressive and computational difficulties for modeling preference and uncertainty. In the study, two measures based on fuzzy set theory are used to assess the satisfaction level of both objectives: possibility measure (height) and area ratio. Two archived meta-heuristics are applied to solve this bi-objective UPMSP: simulated annealing (SA) and tabu search (TS). In SA, random-weight direction (RWD) and fix-weight direction (FWD) are incorporated into the SA framework. In TS, other than RWD and FWD, a Pareto-based method adopting nadir distance (ND) to guide the TS iteration. The three TS search methods use shortest processing time rule (SPT) to construct an initial solution for each TS iteration step. In addition, greedy randomized adaptive search procedure (GRASP) is also applied to create an initial solution for TS. An experiment was conducted using five test sets with two problem sizes, 100 (jobs) x 5 (machines) and 200 x 10, which were generated based on Lee and Pinedo (1997) and Saidi Mehrabad et al. (2009). Each test set is characterized by problem size and due date factors, and has five instances. The numerical results indicate the following: (1) TS with SPT-initial solution outperforms TS with GRASP-initial solution; (2) The satisfaction values calculated based on possibility measure are generally higher than those based on area ratio method, but their conclusions are consistent with each other; (3) TS-FWD and TS-RWD perform better in terms of hyper-volume and generational distance performance measures for problems with loose due dates; on the other hand, there is little difference among SA and TS with distinct weighting direction approaches; finally, TS-ND is inferior to the other algorithms in most instances.
參考文獻
延伸閱讀
- 鍾愛蓮（2009）。模糊多目標非相關平行機台排程問題之解算〔碩士論文，元智大學〕。華藝線上圖書館。https://doi.org/10.6838/YZU.2009.00110
- Nanthapodej, R. (2022). 考量能源耗用與工作負荷平衡之非相關平行機台排程問題之啟發式解法研究 [doctoral dissertation, National Pingtung University of Science and Technology]. Airiti Library. https://doi.org/10.6346/NPUST202200099
- 翁欣瑜（2021）。模糊多目標規劃法於多機離岸風力系統之最佳維修批量決策〔碩士論文，國立屏東科技大學〕。華藝線上圖書館。https://doi.org/10.6346/NPUST202100141
- Lin, C. F. (2006). 在具機器可用時間與機器合適度限制之平行機台排程問題下運用分枝界限法尋求最佳解 [master's thesis, National Central University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0031-0207200917341128
- Harikrishnan, K. K., & Ishii, H. (2001). Some Fuzzy Resource Constrained Scheduling Problems. Asia Pacific Management Review, 6(4), 477-484. https://doi.org/10.6126/APMR.2001.6.4.06