分支定界法是常被用來求解離散與組合優化問題（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.
