多目標排程問題都為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.
為了持續優化網站功能與使用者體驗,本網站將Cookies分析技術用於網站營運、分析和個人化服務之目的。
若您繼續瀏覽本網站,即表示您同意本網站使用Cookies。