政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/109771
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  Items with full text/Total items : 113648/144635 (79%)
Visitors : 51628248      Online Users : 547
RC Version 6.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
    Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer Goto mobile version


    Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/109771


    Title: 開發一個以區塊特性為基礎的啟發式演算法求解流程式排程問題
    Authors: 陳春龍
    Contributors: 資管系
    Keywords: 區塊特性;流程式排程問題;總完成時間;啟發式演算法
    Block;Metaheuristic;Permutation Flow Shop Scheduling;Makespan
    Date: 2015
    Issue Date: 2017-05-18 10:58:58 (UTC+8)
    Abstract: 流程式排程問題（PFSP）是製造現場常見的問題。因為它在實務上的價值以及計算的複雜度，流程式排程問題長久以來都是學術界和產業界非常重視的問題。以總完成時間為目標的流程式排程問題（PFSP- makespan）是研究者最有興趣的問題之一。我從1993就開始該問題的研究，我的兩篇主要的論文分別刊登在EJOR (1995，在WOS資料庫中被引用118次) 和 C&IE (1996，在WOS資料庫中被引用66次)。2011年和2012年國科會計畫的研究成果也以分別刊登在IJAMT (2012), Soft Computing和Applied Soft Computing。2014年的國科會研究計畫則已開發一個比IGRIS 和 DDERLS（兩個到目前為止最好的演算法）為佳的啟發式演算法(BBLS)，因此求解PFSP-makespan，研究的成果最近已經被Soft Computing所接受
    （DOI10.1007/s00500-013-1199-z）。本研究計畫利用PFSPmakespan問題之解的區塊特性（Block）開發一個新的演算法（block-based local search, BBLS）。BBLS先利用NEHT產生一個起使解，設定其為起使期之週期最佳解(local best solution)。然後在每一週期（iteration），利用週期最佳解的區塊特性，產生有效的鄰近解(neighbor solutions)，再應用一個新的篩選方法（filtered local search）在這些鄰近解上，以產生新的週期最佳解，再重複下一週期的搜尋；篩選機制的主要目的是希望將搜尋的方向導引向尚未搜尋的區域。此外，如果搜尋陷入區域最佳解中（local optimum），我們也計畫開發一個逃離策略（jumpstrategy），幫助搜尋跳出區域最佳解。最後，我們會利用IGRIS和 DDERLS（兩個到目前為止最好的演算法）來評價BBLS的效能。
    Permutation flow shop scheduling problem (PFSP) is a common problem in the manufacturing shop floor. Due to its value in the real-world and its computational complexity, it has received considerable attention in academia and in practitioners for years. PFSP with minimum makespan as the objective (PFSP-makespan) is one of the most studied NPhard scheduling problems; more than 1000 technical papers for solving PFSP-makespan can be found in Web of Science (WOS). I started conducting research in this field in 1994, and two of my notable works were published in European Journal of Operational Research (1995, cited 109 times in WOS) and Computers and Industrial Engineering (1996, cited 66 times in WOS). This proposal is a follow-up research of my NSC projects in 2011 and 2012 (100-2221-E-004-004 and 101-2221-E-004-004). The project in 2011 developed a novel metaheuristic (EDAACS) to solve PFSP-makespan, and the result of the project was published in International Journal of Advanced Manufacturing Technology (2012). The project in 2012 developed another metaheuristic (RDPSO) to solve PFSPmakespan, and the result of the project has recently been
    accepted for publication by Soft Computing
    (DOI10.1007/s00500-013-1199-z). This research utilizes the block property of the solution of PFSP-makespan to develop a new metaheuristic (block-based local search, BBLS) for solving PFSP-makespan. BBLS applies NEHT to generate an initial solution and set the solution be the local best solution. Then, in each iteration, BBLS utilizes the block property of the local best solution to efficiently generate promising neighbor solutions and applies a new filtered
    local search method to the generated neighbor solutions to update the local best solution. The purpose of the filtered local search is to filter the solution regions that have been reviewed and guides the search to new solution regions in order to keep the search from trapping into local optima. In addition, a new jump strategy will be developed to help the search escape if the search does become trapped
    at a local optimum. Computational experiments on the wellknown Taillard‘s benchmark data sets will be conducted to compare the performance of BBLS with that of IGRLS and DDERLS, the two most effective heuristics for PFSP-makespan up to now.
    Relation: MOST 103-2221-E-004-002
    Data Type: report
    Appears in Collections:[Department of MIS] NSC Projects

    Files in This Item:

    File Description SizeFormat
    103-2221-E-004-002.pdf609KbAdobe PDF2295View/Open


    All items in 政大典藏 are protected by copyright, with all rights reserved.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback