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


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


    題名: 近似求解機台可用區間限制求最小化總完工時間之平行機台排程問題;Approximation of Identical Parallel Machine Scheduling with Machine Availability Constraint to Minimize Total Completion Time
    作者: 林志佳;Lin, Chih-Chia
    貢獻者: 工業管理研究所
    關鍵詞: 平行機台;可用時間限制;總完工時間;近似解;動態規劃;Parallel Machine;Availability Constraint;Total Completion Time;Approximate Solution;Dynamic Programming
    日期: 2018-08-10
    上傳時間: 2018-08-31 11:28:41 (UTC+8)
    出版者: 國立中央大學
    摘要: 在此研究中,我們探討n個不可被分割的工作以及m個平行機台的排程問題,針對每個機台具有不同數量的可用時間間隔限制的狀況,考慮最小化總完工時間。在多數的排程問題都沒有考慮可用時間間隔的限制,然而在實際情形上這種情形十分地常見,例如在製造業中,機台不可能一直處於運轉的狀態,會針對機台進行例行停機維護,以提升機台在生產時的良率及壽命。
    為了求解此問題的近似解,我們參考了Woeginger(2000)中的trimmed動態規劃演算法,利用定義ε的值,刪減一些相似的state,進而求出近似解,在此演算法中我們加入了Chen(2016)和Tsou(2017)中所提到的三個propositions,此方法是利用到順序排程的概念,其他的則是比較兩個排滿工作時可用區間的開始時間及所被安排工作數量的關係,判斷這部分的排程是否可能為最佳解,藉以減少需要被儲存的state。我們提出了一個方程式估算每次iteration大約會產生多少states,以方便我們計算記憶體量是否足夠進行運算。最後我們與Tsou(2017)所提出的分支定界演算法進行比較,比較處理時間及與最佳解的相似程度。
    ;In this research, we discuss a scheduling problem including n non-preemptive jobs and m identical parallel machines with availability constraints. Our objective is minimizing the total completion time. . Most scheduling problems assume machines will work continuously, but in fact the situation is not always possible. So we consider the situation that each machine has its own available intervals For example, in the manufacturing industry, machines cannot always be in an operating state. Workers will stop the machines for a preventive maintenance period. It can keep the machines status stable and increase the yield of productions and the service life of the machines.
    To find out the approximation solution for our problem, we first develop a dynamic programming algorithm. We adopt the proposed schemes of Tsou.(2017) and Chen.(2016) which is/are based on the idea of scheduling. We used three propositions to eliminate the possibility which cannot lead to the optimal solutions. These propositions are compared by the starting time and the number of jobs which are assigned in the available intervals filled up with jobs. Finally, we compare our dynamic programming with the branch and bound algorithm proposed from Tsou(2017).
    顯示於類別:[工業管理研究所 ] 博碩士論文

    文件中的檔案:

    檔案 描述 大小格式瀏覽次數
    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 ©   - 回饋  - 隱私權政策聲明