臺灣博碩士論文加值系統

在製造產業中，機器有新舊之分，而工件也有大小之分，不同的工件在不同的機台會有不同的處理時間，本研究考慮不同等級的機器相關性與工件相關性，進而對於工件產生不同的處理時間，以符合現實案例，本研究探討相關性平行機在工件有釋放時間和到期日的限制下求解最小化加權總完工時間與總延遲工件數的排程問題，本研究提出一個混合整數規劃模型(mixed integer programming, MIP)來求解此雙目標問題的最佳解，並發展一套啟發式演算法WCT-EDD以快速求得靠近最佳解的近似解，最後，發展一種能夠快速求解且效果良好的人工蜂群演算法(artificial bee colony algo-rithm, ABC)，並將啟發式演算法所得到的近似解加入至ABC中作為起始解，加速求解本研究的雙目標排程問題，本研究將求解結果與其他演算法進行比較，研究結果顯示，本研究所發展的演算法在求解的品質與找出柏拉圖解的數量皆有不錯的效果。

We consider the problem of scheduling correlated parallel machines with release time to minimize total weighted completion time and number of tardy jobs. We first present a mix integer programming (MIP) model that can find pareto-optimal schedules for the studied problem. Next, we have proposed a heuristic and an artificial bee colony algorithm (ABC) that can find non-dominated solutions for the studied problem efficient-ly. We compare our proposed ABC algorithm with other existing algo-rithm. Computation results indicate that the proposed ABC outperforms existing algorithm in terms of the number of non-dominated solutions and the quality of its solutions.

摘　　要 I
ABSTRACT II
目　　錄 III
圖目錄.... V
表目錄.... VI
第一章 緒論 1
第一節、 研究動機及背景 1
第二節、 研究目的 4
第三節、 研究方法與流程 5
第二章 文獻探討 6
第三章 問題描述 10
第一節、 參數定義 10
第二節、 數學模型 11
第三節、 啟發式演算法 12
第四節、 題目範例 15
4.1 NEH排序範例 16
4.2 方法(c) 17
4.3 方法(d) 17
4.4 兩階段排程結合範例 18
第四章 研究方法 19
第一節、 非凌駕解(NON-DOMINATED SOLUTION)介紹 19
第二節、 人工蜂群演算法介紹 20
第三節、 人工蜂群演算法演算流程 21
3.1 編碼 21
3.2 起始解 22
3.3 工蜂初步探查 – 隨機交換 22
3.4 偵查蜂尋找新蜜源 - PBX 22
3.5 群聚距離(crowding distance) 23
3.6 輪盤選擇法 25
3.7 觀察蜂深度探查 – 區域搜尋法(local search) 25
3.8 菁英名單區域搜尋法 28
3.9 終止條件 28
3.10 人工蜂群演算法流程 29
第五章 數據測試與分析 32
第一節、 測試題目產生 32
第二節、 求解成效評估方式 33
第三節、 實驗設計 34
第四節、 數據測試及分析 40
4.1 求解目標值 41
4.2 演算法解的個數 43
4.3 演算法解與最佳柏拉圖前緣解之距離 45
4.4 求解時間 47
4.5 柏拉圖解分佈圖 49
第六章 結論與未來發展 51
第一節、 結論 51
第二節、 未來研究方向 51
參考文獻 52

[1]Asadzadeh, L. (2016). A parallel artificial bee colony algorithm for the job shop scheduling problem with a dynamic migration strategy. Computers & Industrial Engineering, 102, 359-367.1
[2]Bozorgirad, M. A., and Logendran, R. (2012). Sequence-dependent group scheduling problem on unrelated-parallel machines. Expert Systems with Applications, 39(10): 9021-9030.
[3]Cao, D., Chen, M., and Wan, G. (2005). Parallel machine selection and job scheduling to minimize machine cost and job tardiness. Computers & operations research, 32(8): 1995-2012.
[4]Caniyilmaz, E., Benli, B., & Ilkay, M. S. (2015). An artificial bee colony algorithm approach for unrelated parallel machine scheduling with processing set restrictions, job sequence-dependent setup times, and due date. The International Journal of Advanced Manufacturing Technology, 77(9-12), 2105-2115.
[5]Cochran, J. K., Horng, S. M., & Fowler, J. W. (2003). A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines. Computers & Operations Research, 30(7), 1087-1102.
[6]Dugardin, F., Yalaoui, F., & 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]Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182-197.
[8]Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey.Annals of discrete mathematics, 5, 287-326.
[9]Gupta, J. N., and Ruiz-Torres, A. J. (2005). Generating efficient schedules for identical parallel machines involving flow-time and tardy jobs. European Journal of Operational Research, 167(3): 679-695.
[10]Ho, J. C., & Chang, Y. L. (1995). Minimizing the number of tardy jobs for m parallel machines. European Journal of Operational Research,84(2), 343-355.
[11]Hancer, E., Xue, B., Zhang, M., Karaboga, D., & Akay, B. (2018). Pareto front feature selection based on artificial bee colony optimization. Information Sciences, 422, 462-479.
[12]Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization. Technical report-tr06, Erciyes university, engineering faculty, computer engineering department.
[13]Karaboga, D., & Basturk, B. (2007). A powerful and efficient algo-rithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of global optimization, 39(3), 459-471.
[14]Karaboga, D., & Akay, B. (2009). A comparative study of artificial bee colony algorithm. Applied mathematics and computa-tion, 214(1), 108-132.
[15]Kellegöz, T., Toklu, B., & Wilson, J. (2008). Comparing efficiencies of genetic crossover operators for one machine total weighted tardi-ness problem. Applied Mathematics and Computation, 199(2), 590-598.
[16]Lin, Y. K., Fowler, J. W., & Pfund, M. E. (2013). Multiple-objective heuristics for scheduling unrelated parallel machines. European Journal of Operational Research, 227(2), 239-253.
[17]Lin, Y. K., Pfund, M. E., & Fowler, J. W. (2014). Processing time generation schemes for parallel machine scheduling problems with various correlation structures. Journal of Scheduling,17(6), 569-586.
[18]Lin, Y. K., & Lin, H. C. (2015). Bicriteria scheduling problem for unrelated parallel machines with release dates. Computers & Opera-tions Research, 64, 28-39.
[19]Lin, Y. K., & Lin, C. W. (2013). Dispatching rules for unrelated parallel machine scheduling with release dates. International Journal of Advanced Manufacturing Technology, 67, 269-279.
[20]Li, J. Q., Pan, Q. K., & Gao, K. Z. (2011). Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems. The International Journal of Advanced Manufacturing Technology, 55(9-12), 1159-1169.
[21]Lin, S. W., & Ying, K. C. (2014). ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times. Computers & Operations Research, 51, 172-181.
[22]Mönch, L., Balasubramanian, H., Fowler, J. W., & 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.
[23]Nawaz, M., Enscore, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing prob-lem. Omega, 11(1), 91-95..
[24]Nagar, A., Haddock, J., & Heragu, S. (1995). Multiple and bicriteria scheduling: A literature survey. European journal of operational research, 81(1), 88-104.
[25]Oyetunji, E. O., & Oluleye, A. E. (2008). Heuristics for minimizing total completion time and number of tardy jobs simultaneously on single machine with release time. Research Journal of Applied Sciences, 3(2), 147-152.
[26]Pinedo, M. (2012). Scheduling. New York: Springer.
[27]Pan, Q. K., Tasgetiren, M. F., Suganthan, P. N., & Chua, T. J. (2011). A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Information scienc-es, 181(12), 2455-2468.
[28]Ruiz-Torres, A. J., Enscore, E. E., and Barton, R. R. (1997). Simulated annealing heuristics for the average flow-time and the number of tardy jobs bi-criteria identical parallel machine problem. Computers & industrial engineering, 33(1-2): 257-260.
[29]Silva, J. D. L., Burke, E. K., & Petrovic, S. (2004). An introduction to multiobjective metaheuristics for scheduling and timetabling. Metaheuristics for multiobjective optimisation, 91-129.
[30]Shahvari, O., and Logendran, R. (2017). An enhanced tabu search algorithm to minimize a bi-criteria objective in batching and scheduling problems on unrelated-parallel machines with desired lower bounds on batch sizes. Computers & Operations Research 77: 154-176.
[31]Szeto, W. Y., Wu, Y., & Ho, S. C. (2011). An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 215(1), 126-135.
[32]Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., Izadi, M., and Sassani, F. (2009). Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints. Computers & Operations Research, 36(12): 3224-3230.
[33]Ying, K. C., & Lin, S. W. (2012). Unrelated parallel machine scheduling with sequence-and machine-dependent setup times and due date constraints. International Journal of Innovative Computing, Information and Control, 8(5), 3279-3297.