進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-2806201615450600
論文名稱(中文) 考慮具中斷點學習效應之混合流線式生產排程問題
論文名稱(英文) Solving a Hybrid Flow Shop Scheduling Problem with Truncated Learning Effects
校院名稱 成功大學
系所名稱(中) 工業與資訊管理學系
系所名稱(英) Department of Industrial and Information Management
學年度 104
學期 2
出版年 105
研究生(中文) 林宸毅
研究生(英文) Cheng-Yi Lin
學號 R36044053
學位類別 碩士
語文別 中文
論文頁數 114頁
口試委員 指導教授-王泰裕
口試委員-盧浩鈞
口試委員-林君維
口試委員-陳梁軒
中文關鍵字 排程  混合流線式生產  學習效應  以瓶頸為基礎啟發式演算法 
英文關鍵字 scheduling  hybrid flow shop  learning effect  bottleneck-based heuristic 
學科別分類
中文摘要 排程是製造流程中不可或缺的一個環節,目的是在有限的資源中,藉由工作順序及機台分配,降低生產成本並提高企業的經濟效益和競爭力。現今的工廠內部大多是屬於多個加工階段、多個機台的複合式生產環境,而本研究所探討的混合流線式生產 (Hybrid Flow Shop, HFS)就是現今許多製造業的生產環境。

本研究同時考量了學習效應(learning effect),工廠內的人力會經由重複性的加工動作累積經驗而減少作業時間、增加效率,為了避免學習效應的過度擴張,加入學習中斷點,讓學習效應更合理。在傳統排程中往往忽略學習效應的影響而導致結果偏差,本研究將學習效應導入大規模的生產排程問題中,能提供更符合現實狀況的排程決策。
本研究藉由建立一個混整數非線性規化模型來描述具中斷點學習效應的生產線情況,並使用能求解非線性問題的優化軟體Lingo進行求解,然而考慮到求解效率,在面對大規模問題時將以瓶頸效應和限制理論的概念建構演算法RR-MOD求出近似解,並於前測結果中確定了RR-MOD的求解穩定性,再將RR-MOD和常見的啟發式演算法進行比較,最後透過實際跨國工廠的內部資料來證實本研究提出的RR-MOD啟發式演算法。

實驗結果證明了本研究所提出的RR-MOD相較於其他求解排程問題的啟發式演算法具有更高的求解力和效率,而且也能夠在短時間解決實際工廠的大規模排程問題,平均可以改善13.6個加工工作天,也顯示了本研究提出的啟發式演算法不僅能有效求解問題,未來更有發展至其他排程環境的潛力。
英文摘要 Scheduling is the most crucial part of production management. Enterprises can reduce cost and enhance competitiveness by scheduling the important resources. Nowadays, most manufacturing environments become more complex. Hybrid Flow Shop system (HFS) is a combination of flow shop and parallel machines, it is a common system for modern factories.

As the manufacturing scale grows, more and more people will be involved. This will make the learning effect become a key factor of scheduling. However, there is a limit to human’s learning. That is, the concept of “truncated” is needed to be considered because learning effect will definitely stop at some point.

In this research, we proposed two methods to solve the above problem: mathematical programming and heuristic algorithm methods. At first, we construct a mixed integer non-linear programming model which can find optimal solution. In order to enhance the efficiency, we proposed a heuristic algorithm: RRMOD which is composed by machine selecting rule and scheduling decision rule.

To assure the efficiency of RRMOD, we compare RRMOD with other algorithms which are commonly used to solve similar scheduling problems. In addition, to demonstrate the ability of RRMOD to solve the real HFS scheduling problem. A case study from a clothing factory is used to as an example and feasibility of the RRMOD algorithm.

From the results, we found that mathematical programming can provide an optimal solution. However, it performs inefficiently when problem’s scale become large. On the contrary, the RRMOD algorithm performs well regardless the scale of problem. In addition, it effectively improves the original schedule of the clothing factory.
論文目次 摘要 II
致謝 XII
目錄 XIII
圖目錄 XV
表目錄 XVI
第一章 緒論 1
第一節 研究背景與動機 1
第二節 研究目的 2
第三節 研究範圍與限制 3
第四節 研究流程 4
第五節 論文架構 6
第二章、文獻探討 7
第一節 排程理論 7
第二節 混合流線式生產 18
第三節 學習效應 22
第四節 以瓶頸為基礎啟發式演算法(bottleneck based heuristic) 27
第五節 小結 31
第三章、求解具中斷點學習效應之混合流線式排程問題 32
第一節 問題定義與基本假設 33
第二節 建立具中斷點學習效應混合流線式生產排程問題 35
第三節 問題求解 44
第四節 小結 59
第四章、數據分析與模式驗證 61
第一節 以瓶頸為基礎的啟發式演算法內部比較 61
第二節 與其他啟發式演算法在不同生產情境下比較 78
第三節 案例分析 87
第四節 小結 102
第五章、結論與建議 104
第一節 結論 104
第二節 未來研究建議 105
參考文獻 107
附錄 I 訂單資料A-36 112
附錄 II 訂單資料A-18 113
附錄 III 訂單資料B-36 114
參考文獻 Acero-Dominguez, M. J., & Paternina-Arboleda, C. D. (2004, April). Scheduling jobs on a K-stage flexible flow shop using a TOC-based (bottleneck) procedure. In Systems and Information Engineering Design Symposium, 2004. Proceedings of the 2004 IEEE (pp. 295-298). IEEE.

Adams, J., Balas, E., & Zawack, D. (1988). The shifting bottleneck procedure for job shop scheduling. Management Science, 34(3), 391-401.

Adler, L., Fraiman, N., Kobacker, E., Pinedo, M., Plotnicoff, J. C., & Wu, T. P. (1993). BPSS: a scheduling support system for the packaging industry. Operations Research, 41(4), 641-648.

Anderson, E. J., & Nyirenda, J. C. (1990). Two new rules to minimize tardiness in a job shop. The International Journal of Production Research, 28(12), 2277-2292.

Baker, K. R. (1984). Sequencing rules and due-date assignments in a job shop. Management Science, 30(9), 1093-1104.

Baker, K. R., & Bertrand, J. W. M. (1982). A dynamic priority rule for scheduling against due-dates. Journal of Operations Management, 3(1), 37-42.

Baker, K. R., & Kanet, J. J. (1983). Job shop scheduling with modified due dates. Journal of Operations Management, 4(1), 11-22.

Biskup, D. (1999). Single-machine scheduling with learning considerations. European Journal of Operational Research, 115(1), 173-178.

Carroll, D. C. (1965). Heuristic Sequencing of Single and Multiple Component Jobs, unpublished Ph. D (Doctoral dissertation, dissertation, Sloan School of Management, MIT, Cambridge, Massachusetts).

Cheng, J., Karuno, Y., & Kise, H. (2001). A shifting bottleneck approach for a parallel-machine flowshop scheduling problem. Journal of the Operations Research Society of Japan, 44(2), 140-156.

Carlos, D. P.-A., Jairo, R. M.-T., Milton, J. A.-D., & Maria, C. H.-H. (2008). Scheduling jobs on a k-stage flexible flow-shop. Annals of Operations Research, 164(1), 29-40.

Chen, C.-L., & Chen, C.-L. (2008). Bottleneck-based heuristics to minimize tardy jobs in a flexible flow line with unrelated parallel machines. International Journal of Production Research, 46(22), 6415-6430.

Chen, C.-L., & Chen, C.-L. (2009). A bottleneck-based heuristic for minimizing makespan in a flexible flow line with unrelated parallel machines. Computers & Operations Research, 36(11), 3073-3081.

Chen, C.-L., & Chen, C.-L. (2009). Bottleneck-based heuristics to minimize total tardiness for the flexible flow line with unrelated parallel machines. Computers & Industrial Engineering, 56(4), 1393-1401.

Du, J., & Leung, J. Y. T. (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of operations research, 15(3), 483-495.

Gupta, J. N. D. (1988). Two-stage, hybrid flow shop scheduling problem. Journal of the Operational Research Society, 39(4) 359-364.

Goldratt, E. M. (1990). Theory of constraints. Croton-on-Hudson, NY: North River.

Gupta, J. N. D., & Tunc, E. A. (1998). Minimizing tardy jobs in a two-stage hybrid flow shop. International Journal of Production Research, 36(9), 2397-2417.

Haouari, M., Hidri, L., & Gharbi, A. (2006). Optimal scheduling of a two-stage hybrid flow shop. Mathematical Methods of Operations Research, 64(1), 107-124.

Ho, N. B., & Tay, J. C. (2005, September). Evolving dispatching rules for solving the flexible job-shop problem. In Evolutionary Computation, 2005. The 2005 IEEE Congress on (Vol. 3, pp. 2848-2855). IEEE.

Hunsucker, J. L., & Shah, J. R. (1992). Performance of priority rules in a due date flow shop. Omega, 20(1), 73-89.

Imma, R., Rainer, L., & Jose, M. F. (2010). Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Computers & Operations Research, 37(8), 1439-1454.

Jitti, J., Manop R., Paveena C., & Frank, W. (2009). A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. Computers & Operations Research, 36(2), 358-378.

Kuo, W. H., & Yang, D. L. (2006). Single-machine group scheduling with a time-dependent learning effect. Computers & Operations Research, 33(8), 2099-2112.

Liu, J., & MacCarthy, B. L. (1991). Effective heuristics for the single machine sequencing problem with ready times. International Journal of Production Research, 29(8), 1521-1533.

Lee, G.-C., Kim, Y.-D., & Choi, S.-W. (2004). Bottleneck-focused scheduling for a hybrid flow shop. International Journal of Production Research, 42(1), 165-181.

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.

Mosheiov, G. (2001). Scheduling problems with a learning effect. European Journal of Operational Research, 132(3), 687-693.

Nawaz, M., Enscore, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95.

Nowicki, E., & Smutnicki, C. (1998). The flow shop with parallel machines: A tabu search approach. European Journal of Operational Research, 106(2), 226-253.

Pinedo, M. L. (2012). Scheduling: theory, algorithms, and systems. Springer Science & Business Media.

Raghu, T. S., & Rajendran, C. (1993). An efficient dynamic dispatching rule for scheduling in a job shop. International Journal of Production Economics, 32(3), 301-313.

Ramasesh, R. (1990). Dynamic job shop scheduling: a survey of simulation research. Omega, 18(1), 43-57.

Ruiz, R., & Vázquez-Rodríguez, J. A. (2010). The hybrid flow shop scheduling problem. European Journal of Operational Research, 205(1), 1-18.

Toksari, D. M., & Ertan, G. (2010). The common due-date early/tardy scheduling problem on a parallel machine under the effects of time-dependent learning and linear and nonlinear deterioration. Expert Systems with Applications, 37(1), 92-112.

Vepsalainen, A. P., & Morton, T. E. (1987). Priority rules for job shops with weighted tardiness costs. Management science, 33(8), 1035-1047.

Wright, T. P. (1936). Factors affecting the cost of airplanes. Journal of the aeronautical sciences, 3(4), 122-128.

Wang, W. (2011, September). Review on Hybrid Flow Shop Scheduling. In Information Technology, Computer Engineering and Management Sciences (ICM), 2011 International Conference on (Vol. 4, pp. 7-10). IEEE.

Wu, C. C., Yin, Y., & Cheng, S. R. (2011). Some single-machine scheduling problems with a truncation learning effect. Computers & Industrial Engineering, 60(4), 790-795.

Yang, D. L., & Kuo, W. H. (2007). Single-machine scheduling with an actual time-dependent learning effect. Journal of the Operational Research Society, 58(10), 1348-13.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2021-06-28起公開。


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