臺灣博碩士論文加值系統

本研究探討相關性平行機在工件有釋放時間和到期日限制的情況下求解最小化最大延誤時間和總加權完工時間的雙目標排程問題，本研究隨機產生不相關平行機的處理時間，根據不同的機器(Γ)和工件相關性(Δ)，根據不同程度的相關性組合來產生不同的處理時間，以至於能貼近現實的考量。本研究提出一個能求解有相關性的平行機雙目標問題的混合整數規劃模型(mixed integer programming, MIP)來求解小題目的最佳解，並提出一個可以快速找到近似解的啟發式演算法WCT-LSTF，再將WCT-LSTF所求出的解來當作萬用型演算法的起始解，最後發展了一個可以快速求解且效果不錯的人工免疫演算法(Artificial Immune algorithm)。本研究將AIA的求解結果與最佳解、WCT-LSTF和遺傳基因演算法(Genetic algorithm)做比較，結果顯示本研究所發展出來的WCT-LSTF可以有效地解出這類問題的近似解，並加速AIA的求解速度，AIA能夠有效地進一步提升起始解的品質及求解這一類的雙目標排程問題，且AIA求解的品質也優於GA。

We consider the problem of scheduling correlated parallel machines with release time to minimize maximum lateness and total weighted completion time. We first present a mixed integer programming (MIP) model that can find pareto-optimal schedules for the studied problem. Next, we have proposed a heuristic and an artificial immune algorithm (AIA) that can find non-dominated solutions for the studied problem efficiently. For small problem instances, we have compared the proposed heuristic and AIA with the pareto-optimal solutions found by solving the MIP model. For large problem instances, we have compared the proposed heuristic and AIA with a genetic algorithm (GA). The computational results show that the proposed heuristic is computationally efficient and provides solution of reasonable quality. The proposed AIA outperforms GA in terms of the number of non-dominiated solutions and the quality of the solutions.

摘　　要 I
ABSTRACT III
目　　錄 IV
圖目錄 VI
表目錄 VII
第一章 緒論 1
1.1 研究背景及動機 1
1.2 研究目的 5
1.3 論文架構 6
第二章 文獻探討 7
2.1 考慮相關性排程問題 7
2.2 不相關平行機排程問題 7
2.3 人工免疫演算法相關之應用 8
第三章 問題描述 10
3.1 參數定義 10
3.2 數學模式 11
3.3 雙目標排程問題 12
3.4 起始解 15
3.5 範例說明 17
第四章 研究方法 21
4.1 人工免疫演算法(ARTIFICIAL IMMUNE SYSTEM) 21
4.2 免疫系統(IMMUNE SYSTEMS) 22
4.3 名詞解釋 23
4.4 編碼 24
4.5 親和力計算(AFFINITY) 24
4.6 基因重組 25
4.7 突變 26
4.8 超突變 29
4.9 強化策略 31
4.10 人工免疫演算法流程 32
第五章 數據測試與分析 34
5.1 測試題目產生 34
5.2 求解成效評估方式 34
5.3 實驗設計 35
5.4 數據測試及分析 40
5.5 小題目題型求解效果比較 42
5.6大題目題型求解效果比較 45
5.7非劣解分佈圖 47
5.8與遺傳基因演算法比較 48
第六章 結論與未來發展 52
參考文獻 54

[1]Ada, G. L., and Nossal, S. G. (1987). The clonal-selection theory. Scientific American, 257(2), 62-69.
[2]Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., and Sviridenko, M. (1999). Approximation schemes for minimizing average weighted completion time with release dates. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, 32–43.
[3]Balasubramanian, H., Fowler, J., Keha, A., and Pfund, M. (2009). Scheduling interfering job sets on parallel machines. European Journal of Operational Research, 199(1), 55-67.
[4]Coello, C. A. C., and Cortés, N. C. (2005). Solving multiobjective optimization problems using an artificial immune system. Genetic Programming and Evolvable Machines, 6(2), 163-190.
[5]Dessouky MM. (1998). Scheduling identical jobs with unequal ready times on uniform parallel machines to minimize the maximum lateness. Computers and Industrial Engineering, 34(4), 793–806.
[6]Dugardin, F., Yalaoui, F., and Amodeo, L. (2010). New multi-objective method to solve reentrant hybrid flow shop scheduling problem. European Journal of Operational Research, 203(1), 22-31.
[7]Forrest, S., Perelson, A. S., Allen, L., and Cherukuri, R. (1994, May). Self-nonself discrimination in a computer. In Research in Security and Privacy, 1994. Proceedings, 1994 IEEE Computer Society Symposium. 202-212
[8]Graham, R.L., Lawler, E.L, Lenstra, J.K, and Rinnooy Kan, A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling： a survey. Annals of Discrete Mathematics, 5, 287-326.
[9]Hariri, A. M. A. and Potts, C. N. (1991). Heuristics for scheduling unrelated parallel machines. Computers and Operations Research, 18(3), 323–331.
[10]Jiao, L., Gong, M., Shang, R., Du, H., and Lu, B. (2005, March). Clonal selection with immune dominance and anergy based multiobjective optimization. In International Conference on Evolutionary Multi-Criterion Optimization. Springer, Berlin, Heidelberg. 474-489.
[11]Lee, W. C., Wang, J. Y., and Lee, L. Y. (2015). A hybrid genetic algorithm for an identical parallel-machine problem with maintenance activity. Journal of the Operational Research Society, 66(11), 1906-1918.
[12]Lin, Q., and Chen, J. (2013). A novel micro-population immune multiobjective optimization algorithm. Computers & Operations Research, 40(6), 1590-1601.
[13]Lin, Y. –K, and Lin, H. –C. (2015). Bicriteria Scheduling Problem for Unrelated Parallel Machines with Release Dates. Computers & Operations Research, Vol. 64, 28–39.
[14]Lin, Y. K. (2017) Scheduling efficiency on correlated parallel machine scheduling problems. Operational Research, 1-22.
[15]Lin, Y. K., and Lin, C. W. (2013). Dispatching rules for unrelated parallel machine scheduling with release dates. The International Journal of Advanced Manufacturing Technology, 67, 269–279.
[16]Lin, Y. K., Pfund, M. E., and Fowler, J. W. (2014). Processing time generation schemes for parallel machine scheduling problems with various correlation structures. Journal of Scheduling, 17(6), 569-586.
[17]Lin, Y.K., Pfund, ME., Fowler, JW., and Montgomery DC. (2006). Classification of parallel machine environments under various correlation structures. In： Proceedings of the 36th international conference on computers and industrial engineering, Taipei, Taiwan, 1253–61.
[18]Luh, G. C., and Chueh, C. H. (2009). A multi-modal immune algorithm for the job-shop scheduling problem. Information Sciences, 179(10), 1516-1532.
[19]Luh, G. C., Chueh, C. H., and Liu, W. W. (2003). MOIA： multi-objective immune algorithm. Engineering Optimization, 35(2), 143-164.
[20]Mönch, L., Balasubramanian, H., Fowler, J. W., and Pfund, M. E. (2005). Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times. Computers & Operations Research, 32(11), 2731-2750.
[21]Naderi, B., Mousakhani, M., and Khalili, M. (2013). Scheduling multi-objective open shop scheduling using a hybrid immune algorithm. The International Journal of Advanced Manufacturing Technology, 66(5-8), 895-905.
[22]Panwalkar, S.S., Dudek, R.A., and Smith, M.L. (1973). Sequencing research and the industrial scheduling problem. In： Elmaghraby, S.E. (Ed.), Symposium on the Theory of Scheduling and its Applications. Springer, Berlin, 29±38.
[23]Pinedo, M. (2016). Scheduling Theory, Algorithms, and Systems (5th ed.). Prentice Hall.
[24]Ruiz, R., Maroto, C., and Alcaraz, J. (2005). Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics. European Journal of Operational Research, 165(1), 34-54.
[25]Tavakkoli-Moghaddam, R., Rahimi-Vahed, A. R., and Mirzaei, A. H. (2008). Solving a multi-objective no-wait flow shop scheduling problem with an immune algorithm. The International Journal of Advanced Manufacturing Technology, 36(9-10), 969-981.
[26]Tavakkoli-Moghaddam, R., Rahimi-Vahed, A., and Mirzaei, A. H. (2007). A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives： weighted mean completion time and weighted mean tardiness. Information Sciences, 177(22), 5072-5090.
[27]Zandieh, M., Ghomi, S. F., and Husseini, S. M. (2006). An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times. Applied Mathematics and Computation, 180(1), 111-127.