中大機構典藏-NCU Institutional Repository-提供博碩士論文、考古題、期刊論文、研究計畫等下載:Item 987654321/68062
English  |  正體中文  |  简体中文  |  Items with full text/Total items : 70548/70548 (100%)
Visitors : 23174552      Online Users : 379
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/68062


    Title: 具工作可切割特性與機台可用區間及合適度限制求最小化總完工時間之平行機台排程問題;Preemptive Parallel Machine Scheduling with Machine Availability and Eligibility Constraints to Minimize Total Completion Time
    Authors: 鮑可軒;Pao,Ko-hsuan
    Contributors: 工業管理研究所
    Keywords: 平行機台;可用區間限制;機台合適度;工作釋放時間;先佔;總完工時間;parallel machine;available interval;eligibility constriant;release time;preemption;total completion time
    Date: 2015-07-07
    Issue Date: 2015-09-23 10:21:01 (UTC+8)
    Publisher: 國立中央大學
    Abstract: 在此研究中,我們討論 n 個可以分割且具有工作釋放時間的工作和 m 台平行機台的排程問題,針對機台合適度與可用區間限制的狀況,亦即工作有自己適合加工的機台且機台並非一開機就可以重頭做到尾,會有停機維修的狀況加入其中,考慮最小化總完工時間。為了找到此問題的最佳解,我們提出一個分枝界限的演算法,在此演算法中首先利用Liao and Sheen (2008)提出的時間切點的概念,將可用區間對應到時間軸上會發生狀態改變的時間點做切割,根據這樣調整後的區間做分枝,之後,利用二分配對圖發展此分之界限演算法的上界,此上界為一個反覆性的啟發示演算法,得以在演算法一開始便有一初始上界,用以提升演算效率,在最後的實驗分析中可得知此上界演算法不僅是一個複雜度極小的演算法,還是一個效果很好的界限。接著釋放掉機台合適度的限制法展一個複雜度亦極小的下界。實驗結果顯示此分枝界限演算法可以砍掉99%以上非必要的節點,說明此演算法的效率很好,且確實可以找到原問題的最佳解。;In this research, we consider the problem of scheduling n preemptive jobs with distinct release time on m identical parallel machines under machine availability and eligibility constraints to minimize total completion time. To find the optimal solution, we propose a branch and bound algorithm. First, using the idea of time epochs which was proposed from Liao and Sheen (2008) to separate machine available intervals. Then adopt the branching scheme from Mellouli et al. (2009) to branch out a node by assigning an additional job on each available interval specified by two adjacent time epochs. Second, according to our bounding scheme, we develop an iterated heuristic upper bound based on bipartite matching algorithm to find an initial feasible upper bound. By relaxing the restriction of machine eligibility constraint, we used extended shortest remaining processing time (SRPT) which proposed from Yalaoui and Chu (2006) to solve the reduced problem optimally, and set the optimal solution of it to be our lower bound. Computational analysis shows that the efficiency of our branch and bound algorithm can eliminate unnecessary nodes up to 99%. Due to the result of the average percentage gap of our upper bound, it can show that this upper bound is not only a polynomial time bound but also a tight bound.
    Appears in Collections:[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

    Files in This Item:

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