結合配對理論與萬用啟發式演算法於多目標非相關平行機台排程問題求解之研究

Optimizing Multi-Objective Scheduling Problems of Unrelated Parallel Machines via Archived Metaheuristics with Matching Techniques

張煒嵩(Wei-Shung Chang)

指導教授 ： 徐旭昇

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

https://doi.org/10.6838/YZU.2011.00149

摘要

非相關平行機台排程問題(unrelated parallel machine scheduling problems)常見於現實環境中，諸如: 玻璃裁切業，木材裁切業，偏光板裁切等，且生產管理者所考量的生產目標往往是多重的。但過去幾年，學者針對非相關平行機台排程問題大部分僅考慮單一個目標目問題，較少探討多目標且具不確定性之非相關平行型機台排程問題。本論文之主旨在於開發新的啟發式演算法與依照不同目標特質設計相對應之配對解碼模式(matching-based decoding)，以求解多目標與具不確定性之非相關平行型機台排程問題。本論文依照機台稼動率、即時化生產(JIT)、顧客交期滿意度與在製品持有成本等目標特質，將問題目標組合分為四個類型研究。
針對第一與第二類型研究，本論文提出 (1) 演化式演算法 : PCGA、NSGAII、SPEA2與CEMA；(2) 多目標模擬退火法 : UMOSA與SMOSA，求解最小化(minimizing) 兩目標特質均為和 (sum-type) 之非相關平行機台排程問題，諸如:權重式總流程時間(在製品持有成本)與權重式總延遲時間(顧客交期滿意度)，並探討Weighted bipartite matching (WBM) 配對解碼模式於演算法效果之表現。實驗結果顯示，演化式演算法優於多目標模擬退火法，另外CEMA為本研究所發展之重點演算法，其使用配對解碼模式表現優於此案例其他演算法。
第三類型研究為求解最小化三目標之非相關平行機台排程問題，其目標型特質分為兩種： (1) 最大化特質(max-type)，目標式包括最大完工時間(機台稼動率)、最大延遲時間與提前完工時間 (即時化生產)；(2) 混合型特質 (mixed- type)：目標式，其一為最大化特質 - 最大完工時間，另兩個為和之特質 – 此為第一、二類型研究之兩目標式。本論文在類型研究提出SPEA2、CEMA與CRASP演算法，結合min-max matching (MMM) 配對解碼模式求解最大化特質目標；另外結合MMM-WBM求解混合型特質目標。實驗結果顯示， CEMA使用配對解碼模式表現最佳。
第四類型研究主旨為探討模糊雙目標(fuzzy bi-objective)之非相關平行機台排程問題，提出以GRAS、F-MOSA以及D-MOSA演算法，求解目標式為：最大化決策者生產滿意度與顧客平均延遲滿意度問題，並探討配對解碼模式Max-Min matching與WBM使用於演算法之影響與效果表現。實驗結果顯示，演算法使用配對解碼模式表現較佳，其中F-MOSA表現最佳，GRASP表現次佳。
整體而言，本論文所提出之配對解碼模式可提升演算法之效果表現，但當求解機台數增加時則必須花費較多的求解時間。

關鍵字

多目標排程問題 ； 柏拉圖式支配 ； 非相關平行機台排程問題 ； 啟發式演算法 ； 配對解碼模式

並列摘要

Over the years, parallel machine scheduling problems with a single objective or weighted sum of selected objectives have been widely studied. In practice, the layout of unrelated parallel machines is more common than that of their identical counterparts in real manufacturing environments, and management concerns of production scheduling are often multi-fold. In addition, there have been relatively few studies on unrelated parallel machine scheduling problems (UPMSP) considering multiple objectives and uncertain production situation. The research area of multi-objective unrelated machine scheduling problems (MO-UPSMP) is fertile, not only in development of theories and problem solving techniques, but also in practical applications. The main purpose of this thesis is to develop new algorithms for MO-UPMSP, and demonstrate that they are more effective than several popular algorithms.
The thesis presents four studies on MO-UPMSP with sequence- and machine-dependent setup times. The first two studies present different evolutionary algorithms with matching-based decoding scheme to solve UPMSP with two minimization objectives: total weighted tardiness and total weighted flow time. In the two studies, the performances of the proposed hybrid evolutionary algorithms are compared with other metaheuristics, such as multi-objective simulated annealing (MOSA), and two well-known multi-objective population-based evolutionary algorithms.
The third study aims to solve UPMSP with two configurations of three objectives: (1) three min-max objectives; (2) one min-max and two weighted-sum objectives. Three algorithms with matching-based decoding schemes are employed to solve the tri-objective UPMSPs, including SPEA2, CEMA (developed in this research), and GRASP. The GRASP has been successfully applied to solve many single-objective combinatorial optimization problems, but relative few research articles are published on multi-objective scheduling problems. We develop two matching-based decoding schemes, one for three min-max objectives and the other for mixed-type objectives. The experimental results indicate that CEMA with matching-based decoding is superior to the others in terms of several performance metrics often used in multi-objective optimization theory.
The fourth study applies fuzzy approach to solve MO-UPMSP involving uncertainties on job processing times and job due dates. Two objectives are to maximize the decision maker’s satisfaction grade of production makespan and average satisfaction grade of jobs’ tardiness. The solution methods include archived MOSA and GRASP with path-relinking. The numerical results indicate that the GRASP technique has potentials to find good quality solutions for the problem under study.

並列關鍵字

evolutionary algorithms ； performance metrics ； Multi-objective scheduling problems ； Pareto dominance ； unrelated parallel machine scheduling ； meta-heuristics

參考文獻

Adamopoulos, G.I., Pappis, C.P., (1998) Scheduling under a common due-date on parallel unrelated machines. European Journal of Operational Research 105:494-501.

Alisantoso, D., Khoo, L.P., Jiang, P.Y., (2003) An immune algorithm approach to the scheduling of a flexible PCB flow shop. International Journal of Advanced Manufacturing 22 (11-12):819-27.

Allahverdi, A., Ng, C.T., Ceng, T.C.E., Kovalyov, M.Y., (2008) A survey of scheduling problems with setup times or costs. European Journal of Operational Research 187:985-1032.

Armentano A.V., de Araujo (2006) Grasp with memory-based mechanisms for minimizing total tardiness in single machine scheduling with setup times. Journal of Heuristics 12:427-446.

Armentano V.A., de Franca Filho M.F., (2007) Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach. European Journal of Operational Research 183:100-114.