English  |  正體中文  |  简体中文  |  Items with full text/Total items : 65421/65421 (100%)
Visitors : 22281332      Online Users : 226
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/64926


    Title: 利用分枝界限法求具有機台可用時間限制與工作可分割特性之平行機台排程問題;A Branch and Bound Algorithm for Parallel Machine Scheduling Problem with Machine Availability and Job Preemption Constraint
    Authors: 吳蘆恩;Wu,Lu-En
    Contributors: 工業管理研究所
    Keywords: 平行機台;可用區間限制;先佔;總完工時間;Parallel machine;Available interval;Preemption;Total completion time
    Date: 2014-07-28
    Issue Date: 2014-10-15 14:34:14 (UTC+8)
    Publisher: 國立中央大學
    Abstract: 在此研究中,我們考慮當極小化總作業之完工時間,在具機器可用時間區間且工作具有可分割性限制下,討論n個可以分割的工作和m台平行機台的排程問題。每部機台並不是在每個時間點都可以被加工,只有在特定時間區間才可以被安排處理工作。傳統的排程研究多假設機台是可以不間斷的工作,而近年來考量機台的維護保養工作在排程規畫上愈來愈具有重要性,若安排得宜,將可以避免因故障而造成不可預期的損失,故我們在討論具幾台可用區間限制為研究主題。我們提出一個分支界限演算法去尋找這個問題的最佳解。首先,我們用兩種方法找出我們的下限值。我們延伸了Kacem and Chu (2006) 找下限值的方法。我們將各個機台維護區間視為假想的工作,如此一來就可以簡化原問題,並以最短工作時間優先指派的法則得出第一個下限值。第二,我們將每個假想的工作加上工單釋放時間,其目的在於盡量延後每個機台維護區間,讓工時較短的工作可以優先處理,進而達到最小的總完工時間。實驗結果顯示,藉由我們所發展出的分枝界限法可以砍掉99%以上非必要之節點,表示淘汰法則非常具有效率。另外,從實驗得知,當可用區間長度變長時以及維護區間長度變短時,找到答案的時間就愈短,其所需展的節點數也較少。我們的演算法最大能應用於10個工作和4台機台下得到最佳解。;This paper is concerned with the problem of scheduling preemptive jobs processed within time windows on m identical parallel machines to minimizing total completion time. Each machine is not continuously available for processing job all the time. We propose a branch and bound algorithm to find the optimal solution. Firstly, we propose two lower bounds extend from Kacem and Chu (2006). We consider each maintenance period as fictive job. In this assumption, we can simplify our problem and solve it in SPT (shortest processing time first) rule. The second lower bound is that we add additional constraint to fictive jobs by adding machine release time. The purpose of adding this constraint is delaying the maintenance period and assigning the shortest processing time of job first to minimize total completion time. Computational analysis shows that the efficiency of our branch and bound algorithm is powerful. The node eliminated is up to 99%. Our solvable problem size is up to n=10,m=4. Experiment result shows that when the duration of available interval increases, the node generated is decrease. Due to the number of preemption is decrease. When the duration of maintenance is decrease, the node generated is decrease.
    Appears in Collections:[工業管理研究所 ] 博碩士論文

    Files in This Item:

    File Description SizeFormat
    index.html0KbHTML441View/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  - 隱私權政策聲明