具縮減狀態空間機制的分支定界法;A Trimming-The-State-Space Mechanism Embedded Branch-And-Bound Approach

NCU Institutional Repository > 管理學院 > 工業管理研究所 > 研究計畫 > Item 987654321/81984

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/81984

題名:	具縮減狀態空間機制的分支定界法;A Trimming-The-State-Space Mechanism Embedded Branch-And-Bound Approach
作者:	沈國基
貢獻者:	國立中央大學工業管理研究所
關鍵詞:	分支定界法;具縮減狀態空間方法;廣度優先搜尋;最佳優先搜尋;混合搜尋策略;近似演算法;平行機器排程問題;Brand and bound algorithm;Trimming-the-state-space approach;Breath-first search;Best-first search;Hybrid search strategy;Approximation algorithm;Parallel machine scheduling problem
日期:	2020-01-13
上傳時間:	2020-01-13 14:01:59 (UTC+8)
出版者:	科技部
摘要:	分支定界法是常被用來求解離散與組合優化問題（Discrete and combinatorial optimization problems）的方法, 但其求解過程常需要花較長的時間，本研究將提出一個具有縮減狀態空間機制的分支定界法來改善這個問題。本研究中，一個結合廣度優先搜尋與最佳優先搜尋的混合搜尋策略將被採用在演算法中；同時，一般在分支定界法中常用到的排除準則(Elimination criteria) 與定界方式(Bounding schemes) 將被用到縮減狀態空間機制中，以刪除分支過程產生的相關節點。我們首先將發展分支定界法以求極小化總完工時間的平行機台排程問題（具機器可用時間限制）的最佳解，然後再將縮減狀態空間方法整合進去此分支定界法中，而得近似解的分支定界法，以求解其近似解；本研究將評估求解最佳解的分支定界法與求解近似解的分支定界法兩者間在執行時間(Running time) 與答案品質(Solution quality)或誤差上限(Error bound)方面的成效，以了解縮減狀態空間機制的價值。 ;The branch-and-bound algorithm is a well-known method for discrete and combinatorial optimization problems, but it is time-consuming. In this research, a trimming-the-state-space mechanism embedded branch-and-bound approach will be proposed to improve its performance when the algorithm meets certain conditions. A hybrid search strategy combining the breath-first search and the best-first search will be developed. Elimination criteria and bounding schemes which are commonly seen in the branch-and-bound algorithm will be embedded to the trimming-out-the-state-space approach proposed by Woeginger (2000) to eliminate nodes in the branching process. To evaluate the performance of the new approach, this research will first propose two branch-and-bound algorithms for two parallel machine scheduling problems to minimize total completion time with machine availability constraints. Then two branch-and-bound algorithms will further incorporate the trimming-the-state-space mechanism to become the approximation algorithms. The running time and solution quality/error bound of our proposed approach will be evaluated by comparing the performance of the approximation algorithms to its corresponding branch-and-bound algorithms.
關聯:	財團法人國家實驗研究院科技政策研究與資訊中心
顯示於類別:	[工業管理研究所 ] 研究計畫

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	282	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....