臺灣博碩士論文加值系統

近年來學習效應(Learning Effect, LE)在排程領域中受到眾多學者的關注，許多文獻皆將學習效應加入到各類排程問題當中，學習效應意謂著若某一工單被排在較後面的生產序列中，因為持續的重覆加工動作使生產技術提升，相較於前項工單，就會有較短的加工時間。為使問題更貼近真實情況，在本研究中除了將學習效應加入單機排程問題中，還加入變動維修(Variable Maintenance)做進一步的探討。本研究使用的學習效應模型考慮了工單的位置以及已排定工單的長度；維修作業持續時間則是會隨著維修作業的開始時間而增加，且必須在維修最晚期限之前開始作業。主要目的在探討四個與加工時間相關的目標函數，提出求解具有學習效應與變動維修作業單機排程問題包括總完工時間最小化(Minimize Total Completion Time )、平均差異時間最小化（Minimize Mean Lateness）、總流程時間最小化（Minimize Total Flow Time）及平均延遲時間最小化（Minimize Mean Tardiness）的多項式時間演算法，並舉例說明，以利業者實務應用之參考。

In the recent years, learning effect in scheduling has received considerable attention in the literature. This study investigates the single machine scheduling problems with learning effect and a variable maintenance activity simultaneously. In learning effect model, the processing times of jobs are defined as functions of the length and the positions of the already scheduled jobs. The duration of the maintenance activity will increases with the starting time of maintenance, and must starts the maintenance activity before a given deadline. The objective is to present polynomial-time algorithms to solve the problems in order to minimize the objectives of total completion time, mean lateness, total flow time, and mean tardiness.

摘　要 i
ABSTRACT ii
誌　謝 iii
目　錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍 3
1.4 研究限制 4
1.5 研究流程 5
第二章 文獻探討 7
2.1 單機排程問題 7
2.2 單機排程問題之派工法則 8
2.3 具有學習效應之排程問題 9
2.4 具有變動維修之排程問題 12
第三章 研究方法 14
3.1 問題定義 14
3.1.1 問題的MILP模型 16
3.1.2 問題的MILP模型 17
3.1.3 問題的MILP模型 18
3.1.4 問題的MILP模型 18
3.2 證明最佳工單排序的派工法則 19
3.3 問題最佳解範例說明 19
第四章 研究結果 20
4.1 求解 問題 20
4.1.1 問題工單排序最佳化的引理 20
4.1.2 SMLEVM-TC演算法 22
4.1.3 SMLEVM-TC演算法複雜度分析 22
4.1.4 範例說明 23
4.2 求解 問題 24
4.2.1 問題工單排序最佳化的引理 25
4.2.2 SMLEVM-ML演算法 26
4.2.3 SMLEVM-ML演算法複雜度分析 27
4.2.4 範例說明 27
4.3 求解 問題 28
4.3.1 問題工單排序最佳化的引理 29
4.3.2 SMLEVM-TF演算法 30
4.3.3 SMLEVM-TF演算法複雜度分析 31
4.3.4 範例說明 31
4.4 求解 問題 33
4.4.1 問題工單排序最佳化的引理 33
4.4.2 SMLEVM-MT演算法 34
4.4.3 SMLEVM-MT演算法複雜度分析 34
4.4.4 範例說明 35
第五章 結論與建議 37
5.1 研究結論 37
5.2 研究貢獻 38
5.3 未來研究建議 39
參考文獻 40

Biskup, D., 1999, "Single-machine scheduling with learning considerations," European Journal of Operational Research, vol. 115, no. 1, pp. 173-178.
Blackstone, J. H., Phillips, D. T., & Hogg, G. L., 1982, "A state-of-the-art survey of dispatching rules for manufacturing job shop operations," International Journal of Production Research, vol. 20, no. 1, pp. 27-45.
Chang, Y., Sueyoshi, T., & Sullivan, S. R., 1996, "Ranking Dispatching Rules by Data Envelopment Analysis in a Job Shop Environment," IIE Transactions, vol. 28, no. 8, pp. 631-642.
Chen, W.-J., 2009, "Minimizing number of tardy jobs on a single machine subject to periodic maintenance," Omega, vol. 37, no. 3, pp. 591-599.
Chen, W. J., 2005, "Minimizing total flow time in the single-machine scheduling problem with periodic maintenance," JORS, vol. 57, no. 4, pp. 410-415.
Cheng, T. C. E., Hsu, C.-J., Huang, Y.-C., & Lee, W.-C., 2011, "Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness," Computers & Operations Research, vol. 38, no. 12, pp. 1760-1765.
Cheng, T. C. E., Wu, C.-C., & Lee, W.-C., 2008, "Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects," Information Sciences, vol. 178, no. 11, pp. 2476-2487.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & RinnooyKan, A. H. G., 1979, "Optimization and approximation in deterministic sequencing and scheduling: a survey," Annals of Discrete Mathematics, vol. 5, no. 8, pp. 287-326.
Haupt, R., 1989, "A survey of priority rule-based scheduling," Operations Research Spektrum, vol. 11, no. 1, pp. 3-16.
Hino, C. M., Ronconi, D. P., & Mendes, A. B., 2005, "Minimizing earliness and tardiness penalties in a single-machine problem with a common due date," European Journal of Operational Research, vol. 160, no. 1, pp. 190-201.
Koulamas, C., & Kyparisis, G. J., 2007, "Single-machine and two-machine flowshop scheduling with general learning functions," European Journal of Operational Research, vol. 178, no. 2, pp. 402-407.
Kubzin, M. A., & Strusevich, V. A., 2006, "Planning Machine Maintenance in Two-Machine Shop Scheduling," Operations Research, vol. 54, no. 4, pp. 789-800.
Kuo, W.-H., & Yang, D.-L., 2006, "Minimizing the makespan in a single machine scheduling problem with a time-based learning effect," Information Processing Letters, vol. 97, no. 2, pp. 64-67.
Kuo, W.-H., & Yang, D.-L., 2006, "Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect," European Journal of Operational Research, vol. 174, no. 2, pp. 1184-1190.
Lee, W.-C., & Wu, C.-C., 2004, "Minimizing total completion time in a two-machine flowshop with a learning effect," International Journal of Production Economics, vol. 88, no. 1, pp. 85-93.
Lemos, R. F., & Ronconi, D. P., 2015, "Heuristics for the stochastic single-machine problem with E/T costs," International Journal of Production Economics, vol. 168, no. 1, pp. 131-142.
Li, G., Luo, M. L., Zhang, W. J., & Wang, X. Y., 2015, "Single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation," International Journal of Production Research, vol. 53, no. 4, pp. 1228-1241.
Li, Y., Li, G., Sun, L., & Xu, Z., 2009, "Single machine scheduling of deteriorating jobs to minimize total absolute differences in completion times," International Journal of Production Economics, vol. 118, no. 2, pp. 424-429.
Low, C., & Lin, W.-Y., 2013, "Some scheduling problems with time-dependent learning effect and deteriorating jobs," Applied Mathematical Modelling, vol. 37, no. 20-21, pp. 8865-8875.
Luo, W., Chen, L., & Zhang, G., 2010, "Approximation Algorithms for Scheduling with a Variable Machine Maintenance," Algorithmic Aspects in Information and Management, vol. 6124, no. 1, pp. 209-219.
Luo, W., Cheng, T. C. E., & Ji, M., 2015, "Single-machine scheduling with a variable maintenance activity," Computers & Industrial Engineering, vol. 79, no. 1, pp. 168-174.
Mosheiov, G., & Sidney, J. B., 2010, "Scheduling a deteriorating maintenance activity on a single machine," JORS, vol. 61, no. 5, pp. 882-887.
Niu, Y.-P., Wan, L., & Wang, J.-B., 2015, "A Note on Scheduling Jobs with Extended Sum-of-Processing-Times-Based and Position-Based Learning Effect," APJOR, vol. 32, no. 2, pp. 1-12.
Sels, V., & Vanhoucke, M., 2014, "A hybrid Electromagnetism-like Mechanism/tabu search procedure for the single machine scheduling problem with a maximum lateness objective," Computers & Industrial Engineering, vol. 67, no. 1, pp. 44-55.
Wang, J. B., Ng, C. T., Cheng, T. C. E., & Liu, L. L., 2008, "Single-machine scheduling with a time-dependent learning effect," International Journal of Production Economics, vol. 111, no. 2, pp. 802-811.
Wu, C.-H., Lee, W.-C., Lai, P.-J., & Wang, J.-Y., 2016, "Some single-machine scheduling problems with elapsed-time-based and position-based learning and forgetting effects," Discrete Optimization, vol. 19, no. 1, pp. 1-11.
Xu, D., Wan, L., Liu, A., & Yang, D.-L., 2015, "Single machine total completion time scheduling problem with workload-dependent maintenance duration," Omega, vol. 52, no. 1, pp. 101-106.
Xu, D., Yin, Y., & Li, Y., 2010, "Scheduling jobs under increasing linear machine maintenance time," Journal of Scheduling, vol. 13, no. 4, pp. 443-449.
Yang, S.-J., 2012, "Single-machine scheduling problems simultaneously with deterioration and learning effects under deteriorating multi-maintenance activities consideration," Computers & Industrial Engineering, vol. 62, no. 1, pp. 271-275.
Yin, Y., Ye, D., & Zhang, G., 2014, "Single machine batch scheduling to minimize the sum of total flow time and batch delivery cost with an unavailability interval," Information Sciences, vol. 274, no. 1, pp. 310-322.
Ying, K.-C., Lu, C.-C., & Chen, J.-C., 2016, "Exact algorithms for single-machine scheduling problems with a variable maintenance, " Computers & Industrial Engineering, vol. 98, no. 1, pp. 427-433.