進階搜尋


下載電子全文  
系統識別號 U0026-2306201409551200
論文名稱(中文) 退化性工作中整備工作具學習效應的兩機台流程生產排程問題-最大完工時間最小化
論文名稱(英文) Minimizing the Makespan of Two-machine Flow Shop with Deteriorating Jobs and Truncated Learning Effect Setup time
校院名稱 成功大學
系所名稱(中) 工業與資訊管理學系
系所名稱(英) Department of Industrial and Information Management
學年度 102
學期 2
出版年 103
研究生(中文) 蘇柏霖
研究生(英文) Bo-Lin Su
學號 R36011220
學位類別 碩士
語文別 中文
論文頁數 65頁
口試委員 指導教授-張秀雲
口試委員-陳明德
口試委員-葉丁鴻
中文關鍵字 兩機台流程生產  退化性工作  學習效應  分枝界限法  基因演算法 
英文關鍵字 Two-machine flow shop  Deteriorating jobs  Learning effect  Branch and bound algorithm  Genetic algorithm 
學科別分類
中文摘要 本研究探討退化性工作在兩機台流程生產中,整備工作具有學習效應的排程問題,尋找最大完工時間最小化的排程方式,此類問題可能發生在洗衣業與金屬壓延業中,每件工作必須依序經過兩座機台進行作業,而工作本身會隨著開始時間增加而產生所需作業時間遞增的情形,此外須經由人工操作的整備工作會隨著操作員反覆的執行,使得所需整備時間有遞減的情形。
在研究過程中首先建構問題之數學模式,然後分別以分枝界限法與基因演算法進行求解,在分枝界限法的部分中,與作業研究軟體LINGO的求解結果進行比較,可以得知以LINGO只能求得局部最佳解的問題,本研究所建構的分枝界限法能夠更有效率地求得最佳解,此外在分枝界限法的求解過程中,將以數種優先指派法則來設定上限值,透過分析不同的優先指派法則的排程結果,歸納出何種指派法則會有較佳的表現;在基因演算法的部分,將透過分枝界限法求得的最佳解來驗證求解的品質。
由研究結果可知在當退化效應與學習效應的影響較大時,分枝界限法中的上限值與最佳解的相對誤差百分比會有遞增的情形;當退化效應與學習效應的影響改變時,對於本研究所建構的基因演算法求解品質並無顯著的影響,此外求解過程中發現,根據不同的資料特性,以合適的SPT法則,能夠快速的找到品質較佳的可行解。
英文摘要 This study investigates the two-machine flow shop scheduling problem with deteriorating jobs and truncated learning effect setup time. The objective is to minimize the makespan. A dominance property, five upper bounds and two lower bounds are employed to construct the branch and bound algorithm. Furthermore, a genetic algorithm is developed to find a near optimal solution efficiently. Finally, computation experiments are conducted to evaluate the performance of these two algorithms.
論文目次 目錄
摘要 i
Extended Abstract ii
誌謝 v
目錄 vi
表目錄 viii
圖目錄 ix
第一章 緒論 1
1.1研究背景與動機 1
1.2研究目的 3
1.3研究流程 4
第二章 文獻探討 5
2.1兩機台流程生產 7
2.2 退化性工作與學習效應 8
2.3分枝界限法 11
2.4啟發式演算法 13
2.4.1基因演算法 13
2.4.2模擬退火法 15
2.4.3人工免疫演算法 17
2.5小結 18
第三章 研究方法 19
3.1問題敘述與研究假設 19
3.2符號定義與模型建立 20
3.3分枝界限法 22
3.3.1優勢法則 23
3.3.2上限值 24
3.3.3下限值 25
3.3.4求解過程 28
3.4基因演算法 30
3.4.1編碼、族群大小與初始解 30
3.4.2適配值函數 31
3.4.3選擇 31
3.4.4交配 32
3.4.5突變與終止條件 32
3.5 小結 34
第四章 問題試驗與分析 35
4.1實驗環境與問題資料 35
4.2問題試驗 36
4.2.1 分枝界限法驗證 37
4.2.2 分枝界限法上限值分析 38
4.2.3 基因演算法參數分析 40
4.2.4 基因演算法求解結果 43
4.3 小結 51
第五章 研究結論 52
5.1 總結 52
5.2 未來研究方向 53
參考文獻 54
附錄A 分枝界限法上限值 57
附錄B 基因演算法求解結果 61
參考文獻 中文部分
柯惠雯. (2000). 結合模擬退火法與禁忌搜尋法在流程式生產排程之應用. 大葉大學碩士學位論文。
陳昭吉. (2003). 應用遺傳基因演算法於晶圓製造廠之施規佈置問題. 元智大學工業工程與管理系碩士學位論文。
曾佳盈. (2012). 以分枝界限法求解可中斷式開放工廠排程問題. 朝陽科技大學工業工程與管理系學位論文。
劉昱德. (2007). 比較三種萬用啓發式演算法於 TSP 問題之探討. 國立高雄應用科技大學工業工程與管理系碩士論文。
蘇恆磊.(2001).「遺傳演算法於零工式生產排程系統之應用. 國立海洋大學系統工程暨造船學系碩士論文。

英文部分
Aydilek, H., & Allahverdi, A. (2013). A polynomial time heuristic for the two-machine flowshop scheduling problem with setup times and random processing times. Applied Mathematical Modelling, 37(12-13), 7164-7173.
Afshar-Nadjafi, B., Rahimi, A., & Karimi, H. (2013). A genetic algorithm for mode identity and the resource constrained project scheduling problem. Scientia Iranica,20(3), 824-831.
Bagheri, A., Zandieh, M., Mahdavi, I., & Yazdani, M. (2010). An artificial immune algorithm for the flexible job-shop scheduling problem. Future Generation Computer Systems, 26(4), 533-541.
Bank, M., Fatemi Ghomi, S. M. T., Jolai, F., & Behnamian, J. (2012a). Application of particle swarm optimization and simulated annealing algorithms in flow shop scheduling problem under linear deterioration. Advances in Engineering Software, 47(1), 1-6.
Bank, M., Fatemi Ghomi, S. M. T., Jolai, F., & Behnamian, J. (2012b). Two-machine flow shop total tardiness scheduling problem with deteriorating jobs. Applied Mathematical Modelling, 36(11), 5418-5426.
Brucker, P., Burke, E. K., & Groenemeyer, S. (2012). A branch and bound algorithm for the cyclic job-shop problem with transportation. Computers & Operations Research, 39(12), 3200-3214.
Chandra, C., Liu, Z., He, J., & Ruohonen, T. (2014). A binary branch and bound algorithm to minimize maximum scheduling cost. Omega, 42(1), 9-15.
Chen, W. (2009). Minimizing number of tardy jobs on a single machine subject to periodic maintenance. Omega, 37(3), 591-599.
Cheng, T. C. E., Wu, C.-C., Chen, J.-C., Wu, W.-H., & Cheng, S.-R. (2013). Two-machine flowshop scheduling with a truncated learning function to minimize the makespan. International Journal of Production Economics, 141(1), 79-86.
Cheng, T. C. E., Wu, W.-H., Cheng, S.-R., & Wu, C.-C. (2011). Two-agent scheduling with position-based deteriorating jobs and learning effects. Applied Mathematics and Computation, 217(21), 8804-8824.
Damodaran, P., & Vélez-Gallego, M. C. (2012). A simulated annealing algorithm to minimize makespan of parallel batch processing machines with unequal job ready times. Expert Systems with Applications, 39(1), 1451-1458.
Gharbi, A., Ladhari, T., Msakni, M. K., & Serairi, M. (2010). Polynomial lower bounds for the two-machine flowshop problem with sequence-independent setup times. Electronic Notes in Discrete Mathematics, 36, 1089-1096.
Gharbi, A., Ladhari, T., Msakni, M. K., & Serairi, M. (2013). The two-machine flowshop scheduling problem with sequence-independent setup times: New lower bounding strategies. European Journal of Operational Research, 231(1), 69-78.
Huang KL, Liao CJ. (2006). Ant colony optimization combined with tabu search for the job shop scheduling problem. Computers and Operations Research; 35(4):1030–46.
Jarosław, P., Czesław, S., & Dominik, Ż. (2013). Optimizing bicriteria flow shop scheduling problem by simulated annealing algorithm. Procedia Computer Science, 18, 936-945.
Lee, W.-C., Shiau, Y.-R., Chen, S.-K., & Wu, C.-C. (2010). A two-machine flowshop scheduling problem with deteriorating jobs and blocking. International Journal of Production Economics, 124(1), 188-197.
Lin SW, Ying KC. (2008). A hybrid approach for single-machine tardiness problems with sequence-dependent setup times. Journal of the Operational Research Society;59:1109–19.
Low, C., & Lin, W. Y. (2013). Some scheduling problems with time-dependent learning effect and deteriorating jobs. Applied Mathematical Modelling.
Mazloumi, E., Mesbah, M., Ceder, A., Moridpour, S., & Currie, G. (2012). Efficient transit schedule design of timing points: a comparison of ant colony and genetic algorithms. Transportation Research Part B: Methodological, 46(1), 217-234.
Ng, C. T., Wang, J. B., Cheng, T. C. E., & Liu, L. L. (2010). A branch-and-bound algorithm for solving a two-machine flow shop problem with deteriorating jobs. Computers & Operations Research, 37(1), 83-90.
Pang, K.-W. (2013). A genetic algorithm based heuristic for two machine no-wait flowshop scheduling problems with class setup times that minimizes maximum lateness. International Journal of Production Economics, 141(1), 127-136.
Pinedo, M. L. (2012). Scheduling: Theory, Algorithms, and Systems. Springer, New York.
Wang, J.-B., & Wang, M.-Z. (2013). Minimizing makespan in three-machine flow shops with deteriorating jobs. Computers & Operations Research, 40(2), 547-557.
Wang, X., Xie, X., & Cheng, T. C. E. (2013). Order acceptance and scheduling in a two-machine flowshop. International Journal of Production Economics, 141(1), 366-376.
Wu, C.-C., Wu, W.-H., Hsu, P.-H., & Lai, K. (2012). A two-machine flowshop scheduling problem with a truncated sum of processing-times-based learning function. Applied Mathematical Modelling, 36(10), 5001-5014.
Wu, Y.-B., Wang, M.-Z., & Wang, J.-B. (2011). Some single-machine scheduling with both learning and deterioration effects. Applied Mathematical Modelling, 35(8), 3731-3736.
Yang, D. L., & Kuo, W. H. (2010). Some scheduling problems with deteriorating jobs and learning effects. Computers & Industrial Engineering, 58(1), 25-28.
Yang, S.-J. (2011). Group scheduling problems with simultaneous considerations of learning and deterioration effects on a single-machine. Applied Mathematical Modelling, 35(8), 4008-4016.
Yang, S.-J., & Yang, D.-L. (2010). Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities. Omega, 38(6), 528-533.
Yao, S., Jiang, Z., & Li, N. (2012). A branch and bound algorithm for minimizing total completion time on a single batch machine with incompatible job families and dynamic arrivals. Computers & Operations Research, 39(5), 939-951.
Zhang CY, Li P, Rao Y, Guan Z. (2008). A very fast TS/SA algorithm for the job shop scheduling problem. Computers and Operations Research;35(1): 282–94.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2019-07-01起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2019-07-01起公開。


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