English  |  正體中文  |  简体中文  |  Items with full text/Total items : 68069/68069 (100%)
Visitors : 23124788      Online Users : 384
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version


    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:[工業管理研究所 ] 研究計畫

    Files in This Item:

    File Description SizeFormat
    index.html0KbHTML46View/Open


    All items in NCUIR are protected by copyright, with all rights reserved.

    社群 sharing

    ::: Copyright National Central University. | 國立中央大學圖書館版權所有 | 收藏本站 | 設為首頁 | 最佳瀏覽畫面: 1024*768 | 建站日期:8-24-2009 :::
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback  - 隱私權政策聲明