進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-2908201517003200
論文名稱(中文) 不完全作業下考慮交期之兩階段混合流程式排程問題
論文名稱(英文) Two-stage Hybrid Flow Shop Scheduling with Missing Operations and Due Date
校院名稱 成功大學
系所名稱(中) 資訊管理研究所
系所名稱(英) Institute of Information Management
學年度 103
學期 2
出版年 104
研究生(中文) 吳宗霖
研究生(英文) Tsung-Lin Wu
學號 R76021142
學位類別 碩士
語文別 中文
論文頁數 73頁
口試委員 指導教授-張秀雲
口試委員-翁慈宗
口試委員-蔡青志
中文關鍵字 混合流程式排程  不完全作業  總延遲時間  總延遲工件數  派工法則 
英文關鍵字 Hybrid flow shop  Missing operations  Total tardiness  Tardy job  Dispatching rules 
學科別分類
中文摘要 在排程的領域,以最佳解方法解決小規模的問題並不是難題,但隨著環境的複雜度上升,問題也相對越來越難求得最佳解,使用派工法則等啟發式演算法,在可接受的時間內求得近似最佳解已是學者們致力多年的目標。本研究探討的系統為兩階段之混合流程式生產,因需求不同使得某些工件在第一階段作業時間為零之情形,稱之為不完全作業模式(missing operations),若以過往方式產生作業排班,將導致第二階段機台空閒之情形過長,為了改善此類情形,將這些工件直接移至第二階段進行加工,產生非排列式(non-permutation)工作序列,便可得到更好之績效。然而過去文獻中鮮少討論此類情形,其中以交期指標做為目標之研究更為稀少,因此本研究提出三個以交期指標做為目標之啟發式演算法,使此生產系統能快速回應客戶需求,本研究提出之演算法1藉由以多種派工法則產生第一階段排序,計算工件在第二階段釋放時間後,再以其他派工法則產生一組解,從不同組合中選擇最小的總延遲時間排程;演算法2亦以四種排列組合方式產生初始解,並以遞迴方式持續向下搜尋是否有較低的延遲工件數,最後回傳找到的最佳序列;演算法3則是由演算法2的步驟中,利用多個儲存空間記取所有符合最低延遲工件數的排序,從中選擇總延遲時間最低的序列,此三種演算法皆利用有效率地步驟求得近似解。
本研究先以小問題測試本研究提出之啟發式演算法有效性,再以多種參數組合之實驗,探討不同生產環境下演算法之適用性。最後根據分析結果發現,隨著不完全作業比率以及工件數的增加,本研究提出之演算法1與演算法2改善排列式排程狀況也隨之明顯。並在不同資料實驗設計的環境下,分析與交期相關之派工法則,發現當工件數較少時使用SPT派工法則;而工件數提升時使用EDD派工法則,更能快速地找到品質較佳的可行解。
英文摘要 This study discusses two-stage hybrid flow shop with missing operations, which means some jobs do not have to be processed at some stages. The production system we studied is composed of two stages in series. In this system some of jobs could pass over the first stage and only need to be processed on the second stage. Generally, we use the permutation scheduling (PS) method to tackle flow shop scheduling problem, but this doesn’t work effectively when jobs with missing operations. In this study, we proposed three heuristic algorithms to generate a non-permutation scheduling (NPS) from various dispatching rules for problems with due dates related objectives--minimizing the total tardiness and the number of tardy jobs. The computational experiments show that the proposed algorithms find near optimal solution efficiently in small scale problems and outperform PS methods in large scale problems.
論文目次 摘要 ii
Extended Abstract iii
誌謝 vii
目錄 viii
表目錄 x
圖目錄 xii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究架構與流程 4
第二章 文獻探討 6
2.1 排程分類與表示法 6
2.1.1 排程分類方式 6
2.1.2 排程問題之表示方法 7
2.2 混合流程式生產排程 8
2.3 兩階段流程 10
2.4 釋放時間限制 11
2.5 不完全作業模式與非排列式排程 12
2.6 交期指標與相關派工法則 13
2.7 小結 15
第三章 研究方法 18
3.1 問題描述 18
3.2 研究限制與範圍 19
3.3 符號定義與模型建立 20
3.4 啟發式演算法 23
3.4.1 演算法1 24
3.4.2 演算法2 28
3.4.3 演算法3 36
第四章 數據分析與啟發式演算法績效評估 42
4.1 實驗環境與問題資料 42
4.2 小問題試驗 43
4.3 數據分析 46
4.3.1 演算法1分析結果 46
4.3.2 演算法2分析結果 49
4.3.3 演算法3分析結果 51
4.4 小結 52
第五章 結論與未來研究方向 54
5.1 總結 54
5.2 未來研究方向 55
參考文獻 56
附錄A 演算法1求解結果 60
附錄B 演算法2求解結果 67
參考文獻 中文部分:
賴士葆,2004年,生產與作業管理-理論與實務,第三版。台北市:華泰。
陳俊吉,2008年,以啟發式方法解決具迴流性質之彈性流程式排程問題,國立政治大學資訊管理學系碩士班論文。
黃世傑,2010年,不完全作業下兩工作站混合流程式排程研究-最小化總完工時間,國立成功大學工業與資訊管理學系碩士班論文。

英文部分:
Allahverdi, A., & Aydilek, H. (2014). The two stage assembly flowshop scheduling problem to minimize total tardiness. Journal of Intelligent Manufacturing, 26(2), 225-237.
Allaoui, H., & Artiba, A. (2004). Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints. Computers & Industrial Engineering, 47(4), 431-450.
Arthanary, T. S., & Ramamurthy, K. G. (1971). An extension of two machines sequencing problem. Opsearch, 8(1), 10-22.
Brah, S. A. (1996). A comparative analysis of due date based job sequencing rules in a flow shop with multiple processors. Production Planning & Control, 7(4), 362-373.
Brah, S. A., & Loo, L. L. (1999). Heuristics for scheduling in a flow shop with multiple processors. European Journal of Operational Research, 113(1), 113-122.
Choi, H. S., & Lee, D. H. (2009). Scheduling algorithms to minimize the number of tardy jobs in two-stage hybrid flow shops. Computers & Industrial Engineering, 56(1), 113-120.
Figielska, E. (2009). A genetic algorithm and a simulated annealing algorithm combined with column generation technique for solving the problem of scheduling in the hybrid flowshop with additional resources. Computers & Industrial Engineering, 56(1), 142-151.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman and Company, New York, 18, 41.
Gupta, Jatinder N.D., (1988). Two-stage, hybrid flowshop scheduling problem. Journal of the Operational Research Society, 359-364.
Gupta, Jatinder N.D., & Enar A. Tunc. (1991) Schedules for a two-stage hybrid flowshop with parallel machines at the second stage. International Journal of Production Research, 29(7), 1489-1502.
Gupta, Jatinder N.D., & Enar A. Tunc. (1998). Minimizing tardy jobs in a two-stage hybrid flowshop. International Journal of Production Research, 36(9), 2397-2417.
Haouari, M., & Hidri, L. (2008). On the hybrid flowshop scheduling problem. International Journal of Production Economics, 113(1), 495-497.
Komaki, G. M., Teymourian, E., & Kayvanfar, V. (2015). Minimising makespan in the two-stage assembly hybrid flow shop scheduling problem using artificial immune systems. International Journal of Production Research, (ahead-of-print), 1-21.
Kuo, R. J., & Cheng, W. C. (2013). Hybrid meta-heuristic algorithm for job shop scheduling with due date time window and release time. The International Journal of Advanced Manufacturing Technology, 67(1-4), 59-71.
Kuo, Y., Yang, T., Cho, C., & Tseng, Y. C. (2008). Using simulation and multi-criteria methods to provide robust solutions to dispatching problems in a flow shop with multiple processors. Mathematics and Computers in Simulation,78(1), 40-56.
Lee, G. C., & Kim, Y. D. (2004). A branch-and-bound algorithm for a two-stage hybrid flowshop scheduling problem minimizing total tardiness. International Journal of Production Research, 42(22), 4731-4743.
Lee, G. C., Kim, Y. D., & Choi, S. W. (2004). Bottleneck-focused scheduling for a hybrid flowshop. International Journal of Production Research, 42(1), 165-181.
Liao, C. J., Liao, L. M., & Tseng, C. T. (2006). A performance evaluation of permutation vs. non-permutation schedules in a flowshop. International Journal of Production Research, 44(20), 4297-4309.
Mahnam, M., Moslehi, G., & Ghomi, S. M. T. F. (2013). Single machine scheduling with unequal release times and idle insert for minimizing the sum of maximum earliness and tardiness. Mathematical and Computer Modelling,57(9), 2549-2563.
Marichelvam, M. K., & Prabaharan, T. (2014). Performance evaluation of an improved hybrid genetic scatter search (IHGSS) alogorithm for multistage hybrid flow shop scheduling problems with missing operations. International Journal of Industrial and Systems Engineering, 16(1), 120-141.
Mirsanei, H. S., Karimi, B., & Jolai, F. (2009). Flow shop scheduling with two batch processing machines and nonidentical job sizes. The International Journal of Advanced Manufacturing Technology, 45(5-6), 553-572.
Nawaz, M., Enscore Jr, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine job flow-shop sequencing problem. Omega, 11(1), 91-95.
Pinedo, M. L. (2012). Scheduling: theory, algorithms, and systems. Springer. New York.
Pugazhendhi, S., Thiagarajan, S., Rajendran, C., & Anantharaman, N. (2002). Performance enhancement by using non-permutation schedules in flowline-based manufacturing systems. Computers & industrial engineering, 44(1), 133-157.
Rajendran, Chandrasekharan, & Hans Ziegler (2001). A performance analysis of dispatching rules and a heuristic in static flowshops with missing operations of jobs. European Journal of Operational Research 131(3), 622-634.
Ruiz, R., & Vázquez-Rodríguez, J. A. (2010). The hybrid flow shop scheduling problem. European Journal of Operational Research, 205(1), 1-18.
Saravanan, M., Sridhar S., & Harikannan N. (2014). Optimization of realistic multi-stage hybrid flow shop scheduling problems with missing operations using meta-Heuristics. International Journal of Engineering and Technology, 6(1), 483-496.
Tseng, Chao-Tang, Ching-Jong Liao, & Tai-Xiang Liao (2008). A note on two-stage hybrid flowshop scheduling with missing operations. Computers & Industrial Engineering 54(3), 695-704.
Van Dyke Parunak, H. (1991). Characterizing the manufacturing scheduling problem. Journal of Manufacturing Systems, 10(3), 241-259.
Vignier, A., Billaut, J. C., & Proust, C. (1999). Les problèmes d'ordonnancement de type flow-shop hybride: état de l'art. RAIRO-Operations Research, 33(02), 117-183.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2020-09-08起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw