博碩士論文 101426006 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:6 、訪客IP:3.235.140.84
姓名 黃少緯(Shao-wei Huang)  查詢紙本館藏   畢業系所 工業管理研究所
論文名稱 兩階段平行機台考慮工件可分割特性下求解最小完工時間
(Two Stage Hybrid Flow Shop Scheduling with Job Splitting Property for Minimizing the Maximum Completion Time)
相關論文
★ 應用失效模式效應分析於產品研發時程之改善★ 服務品質因子與客戶滿意度關係研究-以汽車保修廠服務為例
★ 家庭購車決策與行銷策略之研究★ 計程車車隊派遣作業之研究
★ 電業服務品質與服務失誤之探討-以台電桃園區營業處為例★ 應用資料探勘探討筆記型電腦異常零件-以A公司為例
★ 車用配件開發及車主購買意願探討(以C公司汽車配件業務為實例)★ 應用田口式實驗法於先進高強度鋼板阻抗熔接條件最佳化研究
★ 以層級分析法探討評選第三方物流服務要素之研究-以日系在台廠商為例★ 變動良率下的最佳化批量研究
★ 供應商庫存管理架構下運用層級分析法探討供應商評選之研究-以某電子代工廠為例★ 台灣地區快速流通消費產品銷售預測模型分析研究–以聯華食品可樂果為例
★ 競爭優勢與顧客滿意度分析以中華汽車為例★ 綠色採購導入對電子代工廠的影響-以A公司為例
★ 以德菲法及層級分析法探討軌道運輸業之供應商評選研究–以T公司為例★ 應用模擬系統改善存貨管理制度與服務水準之研究-以電線電纜製造業為例
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   至系統瀏覽論文 ( 永不開放)
摘要(中) 本論文我們研究一多階段平行機台環境下,有多個工件需要被進行加工處理,且每個工件具有可分割特性的排程問題,我們的目標是決定一最佳排程使得所有工件完工時間最小化。在過去大部分的排程問題都假設每個工件最多只能在一台機台上進行處理,然而在實務上經常會遇到一些情況是多個不同種類的產品,又有各自不同的數量需要在一條生產線上進行加工,在這種狀況下為了使完工時間能夠縮短,我們不會受限於原先的排程假設,我們將允許將相同工件分為多個的批量在不同的機台上同時進行加工,如此來避免機台有閒置的狀況發生。

本研究中我們假設機台環境為兩階段平行機台的排程問題,第一階段有兩台相同平行機台,而第二階段只有單一機台,另外我們假設所有工件之間的整備時間彼此獨立。我們使用分支界限法來尋找此排程問題的最佳解,在演算法中我們提出了下限值和上限值的求算方法以及一些可以刪除不必要的節點法則來提升我們演算法的求解效率。最後我們將此演算法透過JAVA來實現並透過實驗數據來進行分析。
摘要(英) In this research, we consider the problem of scheduling n jobs on hybrid flow shop with job splitting property, and our objective is to minimize the maximum completion time. In the past, the majority of scheduling studies assumed that each job can be processed on at most one machine at a time. In the real word, there are many cases that have different types of products and each type of products have numbers of units need to go through a production line. In order to make these products finished as soon as possible, it is normal to schedule each unit of the same product on different machines at the same time.

In this research, we assume that there are two identical parallel machines in the first stage and a single machine in second stage, and the setup time of each job are independent. We use a branch and bound algorithm to find the optimal solution for this problem. In this algorithm, we propose the lower bound and upper bound for this scheduling problem and we use some dominance rules to eliminate unnecessary nodes to improve the efficiency of our algorithm. Finally, we implement this algorithm by JAVA, and we conduct the computational analysis.
關鍵字(中) ★ 排程
★ 分支界限法
★ 多階段平行機台
★ 工件可分割特性
關鍵字(英) ★ Scheduling
★ Branch-and-bound algorithm
★ Hybrid flow shop
★ Job-splitting property
論文目次 Table of Content

Abstract………………………………………………………i
Table of Content…………………………………………iii
List of Tables………………………………………………v
List of Figures………………………………………………vi
Chapter 1 Introduction……………………………………1

1.1 Background and motivation.........................................................1
1.2 Problem description.......................................................................3
1.3 Research objectives.........................................................................4
1.4 Research methodology and framework .......................................4

Chapter 2 Literature Review................................................6
2.1 Hybrid flow shop scheduling problem..........................................6
2.2 Job splitting property.....................................................................9

Chapter 3 Methodology for the scheduling problem….....10
3.1 Notation…………………………………………..…………10
3.2 Bounding Scheme…….………………………….….……….12
3.2.1 Lower bound LB…………………………………………..12
3.2.2 Upper bound UB……..……………………………………17

3.3 Branching Scheme…..……………………………………………..19
3.3.1 Node Representation……...………………...……………….19
3.3.2 Branching procedure……………………...…………………20

3.5 Dominance Rules………………………………………….…….…23
3.6 Branch and bound algorithm……………………………….….…26

Chapter 4 Computational Analysis………………….……28
4.1 Generating Test Problems ……………………….…..……28
4.2 Validation of branch and bound algorithm ………...……28
4.3 Performance of the branch and bound algorithm………30
Chapter 5 Conclusion……………………………..…..……33
5.1 Research Contribution……………………………….……33
5.2 Research Limitation…………………………………..……34
5.3 Further Research........................................................................34

References………………………………………………....…35
參考文獻 [1] Fattahi, P. et al. (2013), “A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations”, Applied Mathematical Modelling , Vol. 38, pp. 119–134

[2] Brah, Shaukat A. et al. (1991) ”Branch and bound algorithm for the flowshop with multiple processors”, European Journal of Operation Research, Vol.51, pp. 88- 99.

[3] Portmann, M.C. et al. (1997) ”Branch and bound crossed with GA to solve hybrid fowshops”, European Journal of Operation Research, Vol. 107, pp.389-400.

[4] Allaoui, H. et al. (2004) ”Integrating simulation and optimization to schedule a hybrid flowshop with maintenance constraints”, Computers & Industrial Engineering, Vol. 47, pp.431– 450.

[5] Kim, Y.D. et al. (2004) ”Parallel machine scheduling considering a job-splitting property” , International Journal of Production Research, Vol. 42, pp.4531– 4546.

[6] Kis, Tamás et al. (2005) “A review of exact solution methods for the non-preemptive multiprocessor flowshop problem”, European Journal of Operation Research, Vol.164, pp.592-608.

[7] Xing Wenxun et al. (2000) “Parallel machine scheduling with splitting jobs”, Discrete Applied Mathematics, Vol.103, pp.259-269.

[8] Shim Sang-Oh et al. (2008) “A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property”, Computers & Operations Research, Vol. 35, pp.863 - 875

[9] Ruiz Ruben et al. (2010) “The hybrid flow shop scheduling problem”, European Journal of Operational Research, Vol.205, pp.1–18


[10] Rajendran, C. et al. (1992) ”Scheduling in n-job, m-stage floswhop with parallel processors to minimize makespan”, International Journal of Production Economics, Vol.27, pp.137–143.

[11] Gupta, J.N.D. et al. (1997) “Scheduling a two-stage hybrid flow shop with parallel machines at the first stage”, Annals of Operation Research, Vol.69 pp.171-191

[12] Gupta, J.N.D. et al. (1988) ”Two-stage hybrid flow shop scheduling problem”, Journal of the Operational Research Society Vol. 39, pp.359-364.

[13] Potts, C.N. et al. (1992) “Integrating scheduling with batching and lotsizing: a review of algorithm and complexity”, The Journal of the Operational Research Society Vol. 43(5), pp.395-406.

[14] Xing, W. et al. (1998) “Splitting parallel machine scheduling (in Chinese)”, Operation. Research Transactions”, Vol. 2, pp.30-41.

[15] Hoogeveen, J.A. et al. (1996) “Preemptive scheduling in a two-stage multiprocessors flow shop is NP-hard”, European Journal of Operational Research, Vol.89(1), pp.172-175.

[16 ] Haouari Mohamed et al. (2006) “Optimal Scheduling of a Two-Stage Hybrid Flow Shop”, Mathematical Methods of Operations Research, Volume 64, pp 107-124.
指導教授 葉英傑 審核日期 2014-7-28
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明