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

NCUIR > School of Management at National Central University > Graduate Institute of Industrial Management > Research Project > Item 987654321/81984

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/81984

Title:	具縮減狀態空間機制的分支定界法;A Trimming-The-State-Space Mechanism Embedded Branch-And-Bound Approach
Authors:	沈國基
Contributors:	國立中央大學工業管理研究所
Keywords:	分支定界法;具縮減狀態空間方法;廣度優先搜尋;最佳優先搜尋;混合搜尋策略;近似演算法;平行機器排程問題;Brand and bound algorithm;Trimming-the-state-space approach;Breath-first search;Best-first search;Hybrid search strategy;Approximation algorithm;Parallel machine scheduling problem
Date:	2020-01-13
Issue Date:	2020-01-13 14:01:59 (UTC+8)
Publisher:	科技部
Abstract:	分支定界法是常被用來求解離散與組合優化問題（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.
Relation:	財團法人國家實驗研究院科技政策研究與資訊中心
Appears in Collections:	[Graduate Institute of Industrial Management] Research Project

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	290	View/Open

社群 sharing

Loading...