多種模擬退火法於雙目標流線型排程問題解算效果之評估比較

Performance Evaluation of Various Simulated Annealing Algorithms on Solving the Bi-Objective Flow Shop Scheduling Problem

廖昱翔(Yu-Hsiang Liao)

指導教授 ： 徐旭昇

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

摘要

長期以來，生產排程問題之研究多以單目標為主；在實際上，生產排程的考量因素往往不只一種。本研究之主旨即在探討兩種目標之排序流線型排程問題，目的在於找出ㄧ群非支配之可行方案，經由生產管理者加以定鐸。本論文研究所涵蓋的兩目標為：(一)最小化總完工時間(Cmax)與(二)最小化總延遲時間(Total tardiness)。研究方法採用多目標模擬退火演算法(Multi-objective simulated annealing；MOSA)，依三種不同接受機率方式與兩種不同之降溫方式，而組合出六種演算法。

為測試此六種MOSA之解算效果，本研究採用Valente與Alves(2008)之方法產生三組不同規模之測試例題，每組含一個訓練題與二至三個測試題；其中訓練題是用來決定演算法之參數，而測試題用來比較演算法之效果。本研究採用之績效指標有三種：(一)誤差比例值(Error rate；ER)，(二)廣泛式距離值(Generalized distance；GD)，(三)散佈性(Spread)；前兩者為量度所搜尋非支配解集合之收斂性，而最後者則是量度所搜尋非支配解集合之分散性。實驗結果發現，在收斂性指標方面，以接受機率方式採用機率相乘法則，降溫採用傳統幾何級數之MOSA表現為最佳，且計算時間為最短；分散性指標則六個演算法並無明顯差異。

關鍵字

排序流線型排程問題 ； 多目標模擬退火演算法 ； 多目標問題最佳化 ； 柏拉圖最佳解集合

並列摘要

For a long time, the production scheduling problem has been studied based on a single objective. Some commonly adopted objectives for these problem are minimizing makespan (total completion time), total weighted tardiness, mean flow time, etc. In reality, the decision factors of a production manager on scheduling production activities are customarily not only one. In this thesis, we focus our study on two-objective permutation flow shop scheduling problems, with an aim to develop several multi-objective simulated annealing (MOSA) algorithms that can find near Pareto optimal solutions to the problem under study within an acceptable computational time. The production manager then can have many good alternatives for making a choice. The two objectives considered in this study are the minimizations of makespan and total tardiness. The proposed MOSA considers three different acceptance probability rules and two distinct cooling schemes, the combination of which will yield a total of six MOSAs.

In order to evaluate the performance of the six MOSAs, a test set that includes small, medium and large problem size instances were generated according to Valente and Alves (2008). Each size test set contains one training instance and two or three test instances. The training instance is used to decide the parameters of the MOSA algorithms, and the resultant decisions are then applied to the test instances for evaluating the performances of the six MOSAs. Our numerical results indicate that the MOSA utilizing the combination of product of acceptance probabilities and geometrical cooling scheme outperforms the others, in terms of two convergence measures: error rate (ER) and generalized distance (GD), as well as the shortest computational time. However, the six algorithms do not deviate significantly from each other in the diversity measure, SPREAD.

並列關鍵字

Permutation flow shop scheduling problems ； multi-objective simulated annealing algorithms ； Pareto optimal solutions ； total tardiness ； makespan

參考文獻

林昆霖，「子群體基因演算法於多目標排程之應用─以PCB鑽孔作業

林水耕，「應用混合式基因演算法求解流程型工廠之多目標排程問

汪玉柏，「運用基因演算法求解流程型工廠之多目標排程」，碩士

algorithm for flowshop scheduling problem,”

evolutionary algorithm for job shop scheduling,” The