多機台間不具有儲存空間下極小化總延遲時間之流程式生產排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：99

、訪客IP：3.15.34.244

姓名

黃培軒(Pei-shiuan Huang) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

多機台間不具有儲存空間下極小化總延遲時間之流程式生產排程問題
(Minimizing Total Tardiness in Flow Shop Scheduling Problem with Blocking)

相關論文

★ 以類神經網路探討晶圓測試良率預測與重測指標值之建立	★ 六標準突破性策略—企業管理議題
★ 限制驅導式在製罐產業生產管理之應用研究	★ 應用倒傳遞類神經網路於TFT-LCD G4.5代Cell廠不良問題與解決方法之研究
★ 限制驅導式生產排程在PCBA製程的運用	★ 平衡計分卡規劃與設計之研究-以海軍後勤支援指揮部修護工廠為例
★ 木製框式車身銷售數量之組合預測研究	★ 導入符合綠色產品RoHS之供應商管理-以光通訊產業L公司為例
★ 不同產品及供應商屬性對採購要求之相關性探討－以平面式觸控面板產業為例	★ 中長期產銷規劃之個案探討 -以抽絲產業為例
★ 消耗性部品存貨管理改善研究-以某邏輯測試公司之Socket Pin為例	★ 封裝廠之機台當機修復順序即時判別機制探討
★ 客戶危害限用物質規範研究-以TFT-LCD產業個案公司為例	★ PCB壓合代工業導入ISO/TS16949品質管理系統之研究-以K公司為例
★ 報價流程與價格議價之研究–以機殼產業為例	★ 產品量產前工程變更的分類機制與其可控制性探討-以某一手機產品家族為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

本研究探討在多機台間不具有儲存空間下極小化總延遲時間之流程式生產排程問題。在一般製造過程中，兩相鄰的機台間可以有空間存放已經做完的半成品，而在此研究中，兩相鄰機台間不能有儲存空間。
本文針對不具有儲存空間的多機台排程問題發展出分支界限法以求得最小的總延遲時間，該演算法的下限值是在考慮不具儲存空間下計算出來的，此下限值可以幫助我們決定分支的方向，而初始上限值則是使用NEH-EDD啟發式演算法而得，除了兩個上下限值以外，我們還提出了三個定理來決定未排工作在已選定排程外的位置以及一個準則來比較兩個排程在其目標值與工作順序上的優劣。在實驗分析中，將本研究的演算法與窮舉的分支界限演算法比較以驗證本研究演算法的正確性，接下來比較Ronconi and Armentano(2001)的結果，我們演算法平均產生的節點數比Ronconi and Armentano(2001)這篇論文來的有效率。

摘要(英)

This research considers the flow shop scheduling problem with blocking to minimize total tardiness where this problem appears in serial manufacturing processes. There are no buffers between adjacent machines in these processes and a completed job has to stay on a machine until the next downstream machine is available. We propose a lower bound which considers the blocking constraint and several propositions to determine the position of the next unscheduled job and a dominance criterion for comparing two selected sequences. The NEH-EDD heuristic provides a feasible solution which is used as an initial upper bound in our branch-and-bound algorithm. Our algorithm is validated by comparing with an enumeration method and its efficiency is evaluated via several instances. The results show that the average numbers of nodes generated in our algorithm are fewer than algorithm of Ronconi and Armentano(2001).

關鍵字(中)

★ 流程式生產
★ 不具儲存空間
★ 總延遲時間

關鍵字(英)

★ Flow shop
★ Blocking
★ Total tardiness

論文目次

摘要 i
Abstract ii
Table of Contents iii
List of Figures v
List of Tables vi
Chapter 1 Introduction 1
1.1 Research Motivation and Background 1
1.2 Problem Description 3
1.3 Research Objectives 4
1.4 Research Methodology and Framework 4
Chapter 2 Literature Review 7
2.1 Flow Shop Scheduling Problem for Total Tardiness 7
2.2 Flow Shop Scheduling Problem with Blocking 8
Chapter 3 Branch and Bound Algorithm in Flow Shop with Blocking 11
3.1 Notations 11
3.2 Propositions 12
3.3 Initial Upper Bound 18
3.4 Lower Bound 19
3.5 Dominance Criteria 21
3.6 Branching and Bound Algorithm 24
Chapter 4 Computational Analysis 33
4.1 The Validation of the Algorithm 34
4.2 The Evaluation of the Algorithm 35
Chapter 5 Conclusion 47
5.1 Research Contribution 47
5.2 Limitation of Research 47
5.3 Future Research 48
References 49

參考文獻

C. Chung, J. Flynn and O. Kirca (2002) “A Branch and Bound Algorithm to Minimize the Total Flow Time for m-Machine Permutation Flowshop Problems” , Int. J. Production Economics, Vol. 79, 185-196.

C. Chung, J. Flynn and O. Kirca (2006) “A Branch and Bound Algorithm to Minimize the Total Tardiness for m-Machine Permutation Flowshop Problems” , European Journal of Operational Research, Vol. 174, 1-10.

C. Potts and L. Van Wassenhove (1982) “A Decomposition Algorithm for the Single Machine Total Tardiness Problem” , Operations Research Letters, Vol. 1, 177-181.

C. Papadimitriour and P. Kanellakis (1980) “Flowshop Scheduling with Limited Temporary Storage” , Journal of the ACM, Vol. 27, 533-549.

D. Ronconi and V. Armentano (2001) “Lower Bounding Schemes for Flowshops with Blocking In-Process” , The Journal of the Operational Research Society, Vol. 11, 1289-1297.

D. Ronconi (2004) “A Note on Constructive Heuristics for the Flowshop Problem with Blocking” , Int. J. Production Economics, Vol. 87, 39-48.

D. Ronconi (2005) “A Branch-and-Bound Algorithms to Minimize the Makespan in a Flowshop with Blocking” , Annals of Operation Research, Vol. 138, 53-65.

D. Ronconi and L. Henriques (2009) “Some Heuristic Algorithms for Total Tardiness Minimization in a Flowshop with Blocking” , Omega, Vol. 37, 272-281.

E. Vallada, R. Ruiz and G. Minella (2008) “Minimising Total Tardiness in the m-Machine Flowshop Problem - A Review and Evaluation of Heuristics and Metaheuristics” , Computers & Operations Research, Vol. 35, 1350-1373.

F. Victor and M. Jose (2015) “NEH-Based Heuristics for the Permutation Flowshop Scheduling Problem to Minimise Total Tardiness” , Computers & Operations Research, Vol. 60, 27-36.

G. Moslehi and D. Khorasanian (2013) “Optimizing Blocking Flow Shop Scheduling Problem with Total Completion Time Criterion” , Computers & Operation Research, Vol. 40, 1874-1883.

J. Grabowski and J. Pempera (2007) “The Permutation Flow Shop Problem with Blocking. A Tabu Search Approach” , Omega, Vol. 35, 302-311.

J. Grabowski and J. Pempera (2000) “Sequencing of Jobs in Some Produciton System” , European Journal of Operation Research, Vol. 125, 535-550.

L. Wang, Q. Pan and M. Tasgetiren (2010) “Minimizing the Total Time in a Flow Shop with Blocking by Using Hybrid Harmony Search Algorithms” , Computers & Operations Research, Vol. 37, 7929-7936.

M. Nawaz, E. Enscore and I. Ham (1983) “A Heuristic Algorithm for the m-Machine, n-Job Flow-Shop Sequencing Problem” , Omega, Vol. 11, 91-95.

M. Pinedo (2012) Scheduling: Theory, Algorithms, and System, Springer, New York.

N. Hall and C. Sriskandarajah (1996) “A Survey of Machine Scheduling Problem with Blocking and No-Wait in Process” , Operations Research, Vol. 44, 510-525.

P. Gilmore and R. Gomory (1961) “A Linear Programming Approach to the Cutting-Stock Problem” , Operations Research, Vol. 9, 849-859.

R. Mah and I. Suhami (1981) “An Implicit Enumeration Scheme for the Flowshop Problem with No Intermediate Storage” , Computers and Chemical Engineering, Vol. 5, 83-91.

R. Leisten (1990) “Flowshop Sequencing Problem with Limited Buffer Storage” , International Journal of Production Research, Vol. 28, 2085-2100.

S. Reddi and C. Ramamoorthy (1972) “On the Flow-Shop Sequencing Problem with No Wait in Process” , Operations Research Quarterly, Vol. 23, 323-331.

S. McCormick, M. Pinedo, S. Shenker and B. Wolf (1989) “Sequencing in an Assembly Line with Blocking to Minimize Cycle Time” , Operations Research, Vol. 37, 925-935.

T. Sen, P. Dileepan and J. Gupta (1989) “The Two-Machine Flowshop Scheduling Problem with Total Tardiness” , Computers & Operations Research, Vol. 16, 333-340.

W. Trabelsi, C. Sauvey and N. Sauer (2012) “Heuristics and Metaheuristics for Mixed Blocking Constraints Flowshop Scheduling Problems” , Computers & Operations Research, Vol. 39, 2520-2527.
W. Chen and G. Sheen (2007) “Single-Machine Scheduling with Multiple Performance Measures : Minimizing Job- Dependent Earliness and Tardiness Subject to the Number of Tardy Jobs” , Int. J. Production Economics, Vol. 109, 214-229.

W. Townsend (1977) “Note-Sequence n Jobs on m Machines to Minimise Maximum Tardiness : A Branch-and-Bound Solution” , Management Science, Vol. 23, 1016-1977.

Y. Kim (1993) “A New Branch and Bound Algorithm for Minimizing Mean Tardiness in Two-Machine Flowshops” , Computers & Operations Research, Vol 20, 391-401.

Y. Kim (1995) “Minimizing Total Tardiness in Permutation Flowshops” , European Journal of Operational Research, Vol. 85, 541-555.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2015-7-21

推文