English  |  正體中文  |  简体中文  |  全文筆數/總筆數 : 63753/63753 (100%)
造訪人次 : 19166802      線上人數 : 369
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜尋範圍 查詢小技巧:
  • 您可在西文檢索詞彙前後加上"雙引號",以獲取較精準的檢索結果
  • 若欲以作者姓名搜尋,建議至進階搜尋限定作者欄位,可獲得較完整資料
  • 進階搜尋


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


    題名: 近似求解平行機台具機器預防性維修、機器合適度及與工作相關之設置時間限制求最小化總完工時間的排程問題;Approximation of a Parallel Machine Scheduling Problem with the Consideration of Preventive Maintenance, Machine Eligibility and Sequence-Dependent Setup Times to Minimize the Total Completion Time
    作者: 黃覺慧;Huang, Chueh-Hui
    貢獻者: 工業管理研究所
    關鍵詞: 近似解;機器合適度;可用區間;平行機台
    日期: 2018-08-10
    上傳時間: 2018-08-31 11:28:35 (UTC+8)
    出版者: 國立中央大學
    摘要: 在此研究中,我們考慮在機器可用區間、機器合適度及與工作順序相關之設置時間限制下求取最小總完工時間之近似解的排程問題。我們有n個具不同發放時間及與工作順序相關之設置時間的工作,以及m台平行機台。每台機器並非可以一直使用,我們考慮在每部機台中皆會有一例行維修的情況;每個工作可以加工的機台與可以開始加工的時間也不同;並且還有工作順序相關之設置時間,也就是設置時間會根據目前將要加工的工作以及前一個在此機台上加工的工作來決定。為了減少求解問題的時間與記憶體,我們求取其近似解。
    在本研究中,我們提出一個近似演算法去尋找這個排程問題的近似解。在演算法中,我們採Woeginger(2000)與Kacem and Mahjoub (2009)提出的方法。首先,用動態規劃來求取每一輪的子結果,再把每一輪中有近似關係的子結果刪除到僅剩一個,並用剩下的子結果再去進行下一輪計算直到動態規劃結束,並取最後一輪的子結果中最小的總完工時間作為此排程問題的答案。
    ;In this research, we find the minimizing total completion time of a scheduling problem on parallel machines with consideration of machine eligibility, preventive maintenance and sequence-dependent setup times. In our problem, we have n non-preemptive jobs with their release times and sequence-dependent setup times on m parallel machines. Each machine cannot serve jobs at every time point, that is, we consider a preventive maintenance on each machine. Each job has its release time and a set of eligible machines, and also a sequence-dependent setup time which determined by current job and the previous job. In order to reduce CPU run time and memory while solving a scheduling problem by finding an optimal solution, we try to find out a near-optimal solution for the problem.
    We propose an approximation algorithm to solve our scheduling problem approximately. In the algorithm, we use methods which proposed by Woeginger (2000) and Kacem and Mahjoub (2009). At first, a dynamic program is presented to calculate output of partial schedule in each iteration. After mapping at the end of each iteration, we use trimming-the-state-space technique to trim outputs which are close to each other and left only one of these states in state space. Finally, at the end of the final iteration, we find the minimum objective value which is stored in the left states.
    顯示於類別:[工業管理研究所 ] 博碩士論文

    文件中的檔案:

    檔案 描述 大小格式瀏覽次數
    index.html0KbHTML29檢視/開啟


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

    社群 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 ©   - 回饋  - 隱私權政策聲明