English  |  正體中文  |  简体中文  |  Items with full text/Total items : 69937/69937 (100%)
Visitors : 23026081      Online Users : 412
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/71200


    Title: 機台可用區間及合適度限制求最小化總完工時間之平行機台排程問題;Identical Parallel Machine Scheduling with Machine Availability and Eligibility Constraints to Minimize Total Completion Time
    Authors: 陳昱全;Chen,Yu-Cyuan
    Contributors: 工業管理研究所
    Keywords: Parallel machine;Available interval;Eligibility constraint;Release time;Total completion time;平行機台;可用區間限制;機台合適度;工作釋放時間;總完工時間
    Date: 2016-07-20
    Issue Date: 2016-10-13 12:12:07 (UTC+8)
    Publisher: 國立中央大學
    Abstract: 在此研究中,我們考慮最小化總完工時間時,在機器可用區間與機器和適度限制下, n 個具有不同發放時間且無法被分割的工作與 m 台工作效率相同的平行機台之排程問題。每台機器並非一直處於可使用狀態,也就是我們也考慮會有例行停機維修的狀況;而每個工作可開始執行的時間通常是不盡相同,工作也會因工作本身的特性而對應出其合適加工的機台。
    我們提出一個分支界限的演算法去尋找此問題的最佳解。在演算法中,我們探討了兩種分支的方式:一種為採用Melloui et al. (2009)所提出的分支方法;另一種則是自己提出的分支方法,兩者最大不同在於後者方式具有順序排程的概念,根據自己提出的分支方式再提出減少分支的規則。接著在未排的時間區間下將原問題釋放機器和適度限制並允許工作可以被切割,藉此可採用Yalaoui and Chu (2006)提出之特性來解轉換後問題並求得下界。
    ;In most scheduling problem, machines are always continuously available to process jobs all the time. However, it usually exist unavailable time intervals for routine maintenance in practice. Besides, some job is suitable for specific machines to process based on the property of job. In this study, we consider the problem of scheduling n non-preemptive jobs with distinct release time on m identical parallel machines under machine availability and eligibility constraints to minimize total completion time.
    For the scheduling problem, we use branch and bound method to find the optimal solution. In the branch and bound algorithm, we discuss two way of branching. First one is, we adopted the branching scheme from Mellouli et al. (2009) which concept is through assigning an additional job on each available interval. We also propose the other approach of branching which contained the concept of forward scheduling. Based on the branching scheme we proposed, we also propose a dominance rule to eliminate redundant nodes. We adopted the property in Yalaoui and Chu (2006) which could solve the reduced problem by relaxing the restriction of machine eligibility constraint and allow jobs split, and let the optimal solution to be our lower bound.
    Appears in Collections:[工業管理研究所 ] 博碩士論文

    Files in This Item:

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