應用模擬退火法與離散粒子群演算法在排列流程式排程問題之研究

Application of Simulated Annealing and Discrete Particle Swarm Optimization Algorithm for Permutation Flow-Shop Problems

沈銘倫(Ming Lun Shen)

指導教授 ： 王明展

國立臺北科技大學/管理學院/工業工程與管理研究所/碩士(2009年)

https://doi.org/10.6841/NTUT.2009.00218

摘要

多目標排程問題都為NP-hard，通常求解此類問題需要花費較長的時間，尤其是大規模(工作數量、機器種類)問題，因此本研究提出混合式離散粒子群演算法以求解排程問題。
求解最佳化問題透過啓發式演算法，能有效地搜尋與求解NP-hard問題，其中常見NP-hard問題，例如車輛途程、生產排程、設施規劃等問題。本研究求解總完工時間與總流程時間最小化，利用本研究提出混合式離散粒子群演算法其中離散粒子群針對排程問題而內部結構改變，再加上離散粒子群本身具有探測與開發的能力，接著應用模擬退火法能夠避免離散粒子群陷入區域最佳解並改善執行效率。本研究以Taillard的排程基準並與其它演算法作比較，經過第四章的實驗結果，本研究提出的混合式離散粒子群演算法能在總完工時間與總流程時間目標求得最佳解且能適用在排列流程式排程問題。

關鍵字

排程 ； 粒子群 ； 模擬退火法

並列摘要

All the multi-objective scheduling problems are essentially NP-hard. It usually cost us much time to solve these problems. We try to apply Hybrid discrete particle swarm optimization (HDPSO) proposed to deal with multi-objective production efficient scheduling problems.
For the optimization problems, meta-heuristics have driven to be more efficiency and deal with different NP-hard problems, such as vehicle routing, production scheduling, facility layout, etc. We consider criterions which are minmize makespan and total flow time, we try to apply HDPSO where Discrete particle swarm optimization changed insides configuration to aim at scheduling problem and characteristics of exploration and exploitation itself. Furthermore, simulated annealing(SA) have escaped Discrete particle swarm optimization to trapped local optima and improvement quality solution. The proposed HDPSO was applied to well-known Taillard benchmark problems and compared with several competing meta-heuristics. Experiment result shows that we proposed HDPSO is competitive and efficient in Permutation Flow-Shop Problem(PFSP) with minmize makespan and total flow time.

並列關鍵字

Schedule ； Particle Swarm Optimization ； Simulated Annealing

參考文獻

[4] L. Wang, and D.Z. Zheng. ,“An effective optimization strategy for job shop scheduling problems,” Computers and Operations Research, 2001, pp.585-596.

[5] T. Yamada, and R. Nakano,“Job-shop scheduling by simulated annealing combined with deterministic local search,” In: Meta-heuristics: theory and applications. Dordrecht: Kluwer Academic Publishers, 1996, pp.237-248.

[6] J. Carlier, and E. Pinson, “An algorithm for solving the job-shop problem,” Management Science, 1989, pp.64-76.

[7] Kuo-Ling Huang ,“Ching-Jong Liao, Ant colony optimization combined with taboo search for the job shop scheduling problem,” Computers & Operations Research, vol.35 , 2008, pp.1030 -1046

[8] C. Blum, and M. Sampels, ”An ant colony optimization algorithm for shop scheduling problems ,” Journal of Mathematical Modelling and Algorithms, 2004, pp.285-308.