模糊多目標非相關平行機台排程問題之解算

現今科技產業生產製造現場存在著許多屬於非相關平行機台排程問題(Unrelated Parallel Machine Scheduling Problem，UPMSP)，決策者考量的目標取向也越趨越廣，且多目標的非相關平行機台排程問題近幾年研究皆加入了更多時間上的考量因子，包括整備時間、設置時間等，但此法在應用啟發式演算法解決排程問題上仍有其不足處，故本研究將模糊理論(Fuzzy theory)的概念應用在解決排程問題重要的已知資訊上—加工以及交期時間，將此兩項資訊以模糊化表示，以別以往研究增加固定的數值因子，使得解決排程問題考量更為完善。　　本研究選擇三種演算法、兩種解算的取向作為實驗結果分析的依據，第一種解算取向為固定目標權重而針對此權重下做搜尋最佳解，此法對於搜尋方向的確切性有助於提高解的品質性，但其缺點為一定要預知決策者對與多種目標的偏好重要性，在此研究選擇模擬退火法(Simulated Annealing，SA)作為分析的依據；第二種解算方式不用先預知決策者的多目標偏好，在搜尋解時將非支配解存在於外部非支配解母體中保留，最後在提供非支配解集合給予決策者多重的選擇，在此本研究選擇兩種演算法—柏拉圖保存式演化策略演算法(Pareto Archived Evolution Strategy，PAES)與保存式多目標模擬退火法(Archived Multi-Objective Simulated Annealing，AMOSA)，作為數據分析的依據。在實驗分析階段，將柏拉圖式求解演算法，加入固定特定權重以及隨機權重，加以分析其求解特性。　　期望藉由考量兩種多目標規劃作法並比較不同的求解機制提供排程決策者更適合工廠現況的排程方法機制。

關鍵字

非相關平行機台排程問題；模糊理論；模擬退火法；柏拉圖保存式演化策略演算法；保存式多目標模擬退火法

並列摘要

This research studies unrelated parallel machine scheduling problems (UPMSP) with two objectives – minimizing average tardiness and the number of tardy jobs. To make the study better fit a real world application, job processing times are defined as triangular fuzzy numbers whereas due dates as trapezoidal fuzzy numbers. Three state-of-art algorithms, multi-objective simulated annealing (MOSA), Pareto archived evolution strategy (PAES), and archived multi-objective simulated annealing (AMOSA), are applied to solve the bi-objective UPMSP. Each algorithm consists of three decoding schemes, one of which is the commonly used decoding scheme - machine-group assignment with fixed weighted vectors (MGA_FW) on objectives, and the other two are novel schemes: (1) machine-group matching improvement with fixed weighted vectors (MGMI_FW); (2) machine-group matching improvement with random weighted vectors (MGMI_RW). 　　Benchmark instances with problem size 100 (jobs) x 5 (machines) and 100 x 10 using three levels for each of the two parameters, due-date tightness and due-date range, are generated according to a method in the literature. Our experimental results indicate that the decoding scheme MGMI_RW excels in eight out of nine instances. Additionally, AMOSA_MGMI_RW outperforms the others for problems with loose due-date tightness, and PAES_MGMI_RW works best for problems with moderate due-date tightness. Finally, for problems with strict due-date tightness, the MOSA_MGMI_FW surpasses the others for narrow due-date range, while PAES_MGMI_FW and PAES_MGMI_RW are better for moderate- to wide- due-date range.

並列關鍵字

Multi-objective optimizations ； unrelated parallel machine scheduling ； Hungarian method ； archive ； simulated annealing ； Pareto archive evolution strategy ； fuzzy numbers ； tardiness ； tardy jobs

參考文獻

莊宗南，「模糊零工式排程之研究」，國立成功大學企業管理研究所 (2002)。

Bank J. and Werner F. (2001) “Heuristic algorithms for unrelated parallel machine scheduling with a common due date, release dates”, Mathematical and Computer Modelling, Vol. 33, No. (3-5), pp. 363–383

Chen J. F. (2005) “Unrelated parallel machine scheduling with secondary resource constraints”, International Journal of Advanced Manufacturing Technology, Vol. 26, No. 3, pp. 285-292

Dong Y. and Masatoshi K. (2000) “Solving Unrelated Parallel Machine Scheduling Problems with Fuzzy Processing Time”, Journal of Japan Industrial Management Association, Vol. 51, No. 1, pp. 9-16

Glass C. A., Potts C. N. and Shade P. (1994) “Unrelated parallel machine scheduling using local search”, Mathematical and Computer Modelling, Vol. 20, No. 2, pp. 41–52

國際替代計量

模糊多目標非相關平行機台排程問題之解算

全文下載

主題瀏覽