臺灣博碩士論文加值系統

生活中隨處都可發現排程問題的應用，本研究所探討之排程為模擬製造業訂單排程，在過去，許多排程業者未曾考量產能上限，這導致無法按時交付而帶來延遲成本，因此本研究探討訂單接受排程問題(OAS)，該問題考量了產能上限下的訂單截止日期與相關信息，以獲得帶來最高價值的訂單接受順序。近年來許多研究人員，開始研究環境污染與能源相關議題，也包含使用時間電價(TOU)的研究，這表示昂貴的電費成本已經為企業帶來了沉重的負擔。由於沒有研究將OAS與TOU問題相結合，在這樣的情況下經常會為製造商帶來更大的用電成本，因此這項研究的重要貢獻在此。我們採用了OĞUZ et al.[41]提供的測試資料與基礎模型，並分別將TOU限制式與處理功耗添加到模型與實例中。為了解決這個新問題，我們開發了一種結合多層感知器(MLP)神經網路的遺傳算法，我們使用MLP來預測染色體的適應度函數，並指導遺傳進化過程。CPLEX提供的上限值用來驗證算法的有效性，以及與簡單遺傳算法(SGA)相比，我們發現，在部分實例中，即使計算時間較長，所提出的算法也能找到比SGA更好的解決方案。

Scheduling problems can be seen everywhere in life, and the scheduling discussed in this research is to simulate manufacturing order scheduling. In the past, many dispatching companies did not consider capacity limitations, which caused the tardiness. This research explores the order acceptance scheduling problem (OAS), which considers the due day under the capacity constraints toward higher revenue. In recent years, many researchers have changed the study of environmental pollution and time-of-use electricity cost (TOU). It means that the cost of electricity has made a heavy burden on enterprises. Because no study combines the OAS with the TOU cost, it is the significant contribution of this research. We employed the model and benchmark instances from OĞUZ et al.[41], and add the TOU constraints and power consumptions into the model and instances, respectively. In order to solve this new problem, a genetic algorithm with the multi-layer perceptron (MLP) neural network is developed. We use MLP predicts the fitness function of the chromosomes and guide the evolution process. CPLEX is used to provide the upper bound value to validate the effectiveness of the proposed algorithm compared to stand genetic algorithms (SGA). We found the proposed algorithm founds better solutions than SGA in some instances, even though the computational time is higher.

目錄
中文摘要.................................................................................................i
英文摘要.................................................................................................ii
誌謝........................................................................................................iii
目錄........................................................................................................iv
一、緒論................................................................................................1
　1.1 研究背景......................................................................................1
　1.2 研究動機與目的...........................................................................3
　1.3 研究流程......................................................................................4
二、文獻回顧.........................................................................................5
　2.1 訂單接受排程問題........................................................................5
　2.2 單目標的節能排程問題................................................................8
　2.3 雙目標的節能排程問題...............................................................11
　2.4 使用神經網路作為GA的適應度函數...........................................14
　2.5 使用機器學習作為GA的適應度函數...........................................17
　2.6 其他使用回歸模型加速算法的研究.............................................20
三、研究方法.......................................................................................24
　3.1 問題考量與所用數據的描述以及數學模型..................................24
　3.2 遺傳算法的主程式流程...............................................................29
　3.3 預測染色體適合度方法的運用....................................................32
　3.4 遺傳算法內使用的交配運算元....................................................33
　3.5 遺傳算法內使用的突變運算元....................................................34
　3.6 迭代貪婪區域搜尋法(Iteration Greedy Local Search, IGLS)......35
四、訂單接受問題實驗方式與結果討論...............................................36
　4.1 簡單遺傳算法(SGA)的實驗設計.................................................36
　4.2 SGA加入多層感知器(MLP)參數實驗設計...................................39
　4.3 訂單接受問題實驗結果比較表....................................................42
　4.4 兩種方法間的差異檢定...............................................................47
五、結合時間電價表的訂單接受問題實驗與結果討論.........................48
　5.1 結合時間電價表的簡單遺傳算法(SGA)實驗設計........................49
　5.2 SGA加入多層感知器(MLP)參數實驗設計..................................50
　5.3 結合時間電價表的訂單接受問題實驗結果比較表.......................53
　5.4 兩種方法在解決該議題上的差異檢定........................................58
　5.5 兩種問題間的實際差異說明.......................................................59
　5.6 降低MLP使用次數後的實驗結果討論.........................................60
六、結論..............................................................................................63

[1] D. Anghinolfi and M. Paolucci, “A new mip heuristic based on randomized neighborhood search," in Agra, Agostinho and Doostmohammadi, Mahdi (2011) A Polyhedral Study of Mixed 0-1 Set. In: Proceedings of the 7th ALIO/EURO Workshop. ALIO-EURO 2011, Porto, pp. 57-59., 2011, p. 85.

[2] T. C. Bora, V. C. Mariani, and L. dos Santos Coelho, "Multi-objective opti mization of the environmental-economic dispatch with reinforcement learning based on non-dominated sorting genetic algorithm,” Applied Thermal Engi neering, vol. 146, pp. 688-700, 2019.

[3] A. E. Brownlee, 0. Regnier-Coudert, J. A. McCall, and S. Massie, “Using a markov network as a surrogate fitness function in a genetic algorithm," in Evolutionary Computation (CEC), 2010 IEEE Congress on. IEEE, 2010, pp. 1-8.

[4] A. E. Brownlee and J. A. Wright, "Constrained, mixed-integer and multi objective optimisation of building designs by nsga-ii with fitness approximation,” Applied Soft Computing, vol. 33, pp. 114-126, 2015.

[5] A. Bruzzone, D. Anghinolfi, M. Paolucci, and F. Tonelli, "Energy-aware scheduling for improving manufacturing process sustainability: A mathemat ical model for flexible flow shops,” CIRP Annals-Manufacturing Technology, vol. 61, no. 1, pp. 459–462, 2012.

[6] D. Buche, N. N. Schraudolph, and P. Koumoutsakos, “Accelerating evolution ary algorithms with gaussian process fitness function models," IEEE Transac tions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 35, no. 2, pp. 183–194, 2005.

[7] L. T. Bui, J. Branke, and H. A. Abbass, “Diversity as a selection pressure in dynamic environments," in Proceedings of the 7th annual conference on Genetic and evolutionary computation. ACM, 2005, pp. 1557–1558.

[8] B. Cesaret, C. Oğuz, and F. S. Salman, “A tabu search algorithm for order acceptance and scheduling," Computers & Operations Research, vol. 39, no. 6, pp. 1197–1205, 2012.

[9] S. N. Chaurasia and A. Singh, “Hybrid evolutionary approaches for the single machine order acceptance and scheduling problem,” Applied Soft Computing, vol. 52, pp. 725–747, 2017.

[10] A. Che, X. Wu, J. Peng, and P. Yan, “Energy-efficient bi-objective single machine scheduling with power-down mechanism," Computers & Operations Research, vol. 85, pp. 172–183, 2017.

[11] A. Che, Y. Zeng, and K. Lyu, “An efficient greedy insertion heuristic for energy conscious single machine scheduling problem under time-of-use electricity tariffs,” Journal of cleaner production, vol. 129, pp. 565–577, 2016.

[12] A. Che, S. Zhang, and X. Wu, "Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs," Journal of Cleaner Production, vol. 156, pp. 688–697, 2017.

[13] S.-H. Chen and M.-C. Chen, “Addressing the advantages of using ensemble probabilistic models in estimation of distribution algorithms for scheduling problems,” International Journal of Production Economics, vol. 141, no. 1, pp. 24–33, 2013.

[14] C. Cheng, Z. Yang, L. Xing, and Y. Tan, “An improved genetic algorithm with local search for order acceptance and scheduling problems," in Computational Intelligence In Production And Logistics Systems (CIPLS), 2013 IEEE Workshop on. IEEE, 2013, pp. 115–122.

[15] T. Chugh, Y. Jin, K. Miettinen, J. Hakanen, and K. Sindhya, "A surrogate assisted reference vector guided evolutionary algorithm for computationally expensive many-objective optimization," IEEE Transactions on Evolutionary Computation, vol. 22, no. 1, pp. 129–142, 2018.

[16] G. Cybenko, “Approximation by superpositions of a sigmoidal function,” Math ematics of control, signals and systems, vol. 2, no. 4, pp. 303–314, 1989.

[17] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiob jective genetic algorithm: Nsga-ii," IEEE transactions on evolutionary computation, vol. 6, no. 2, pp. 182–197, 2002.

[18] Y. Deng, Y. Liu, and D. Zhou, “An improved genetic algorithm with initial population strategy for symmetric tsp," Mathematical Problems in Engineering, vol. 2015, 2015.

[19] A. Díaz-Manríquez, G. Toscano-Pulido, and W. Gómez-Flores, “On the se lection of surrogate models in evolutionary optimization algorithms," in Evolutionary Computation (CEC), 2011 IEEE Congress on. IEEE, 2011, pp. 2155-2162.

[20] J.-Y. Ding, S. Song, R. Zhang, R. Chiong, and C. Wu, “Parallel machine scheduling under time-of-use electricity prices: New models and optimiza tion approaches," IEEE Transactions on Automation Science and Engineering, vol. 13, no. 2, pp. 1138-1154, 2016.

[21] A. F. El-Samak and W. Ashour, "Optimization of traveling salesman problem using affinity propagation clustering and genetic algorithm,” Journal of Ar tificial Intelligence and Soft Computing Research, vol. 5, no. 4, pp. 239-245, 2015.

[22] K.-T. Fang and B. M. Lin, “Parallel-machine scheduling to minimize tardiness penalty and power cost,” Computers & Industrial Engineering, vol. 64, no. 1, pp. 224-234, 2013.

[23] D. R. Fernandes, C. Rocha, D. Aloise, G. M. Ribeiro, E. M. Santos, and A. Silva, "A simple and effective genetic algorithm for the two-stage capacitated facility location problem," Computers & Industrial Engineering, vol. 75, pp. 200-208, 2014.

[24] D. E. Goldberg et al., Genetic Algorithms in Search, 1989, vol. 432.

[25] P. Guo, W. Cheng, and Y. Wang, "Hybrid evolutionary algorithm with extreme machine learning fitness function evaluation for two-stage capacitated facility location problems,” Expert Systems with Applications, vol. 71, pp. 57–68, 2017.

[26] G. R. Harik, "Finding multimodal solutions using restricted tournament selec tion." in ICGA, 1995, pp. 24–31. S. Haykin, Neural networks: a comprehensive foundation. Prentice Hall PTR,
1994.

[28] K. Hornik, M. Stinchcombe, and H. White, “Multilayer feedforward networks are universal approximators," Neural networks, vol. 2, no. 5, pp. 359–366, 1989.

[29] Y. D. Ko, “An efficient integration of the genetic algorithm and the reinforce ment learning for optimal deployment of the wireless charging electric tram system,” Computers & Industrial Engineering, 2018.

[30] S. Lee, B. Do Chung, H. W. Jeon, and J. Chang, "A dynamic control ap proach for energy-efficient production scheduling on a single machine under time-varying electricity pricing," Journal of Cleaner Production, vol. 165, pp. 552–563, 2017. B IN *

[31] Y. H. Lee, K. Bhaskaran, and M. Pinedo, "A heuristic to minimize the total weighted tardiness with sequence-dependent setups,” IIE transactions, vol. 29, no. 1, pp. 45–52, 1997.

[32] K. Li, X. Zhang, J. Y.-T. Leung, and S.-L. Yang, "Parallel machine scheduling problems in green manufacturing industry," Journal of Manufacturing Systems, vol. 38, pp. 98-106, 2016.

[33] S.-W. Lin and K. Ying, “Increasing the total net revenue for single machine
order acceptance and scheduling problems using an artificial bee colony algorithm,” Journal of the Operational Research Society, vol. 64, no. 2, pp. 293–311, 2013.

[34] C. Liu, J. Yang, J. Lian, W. Li, S. Evans, and Y. Yin, “Sustainable performance oriented operational decision-making of single machine systems with determin istic product arrival time," Journal of cleaner production, vol. 85, pp. 318-330, 2014.

[35] S. A. Mansouri, E. Aktas, and U. Besikci, "Green scheduling of a two-machine flowshop: Trade-off between makespan and energy consumption," European Journal of Operational Research, vol. 248, no. 3, pp. 772–788, 2016.

[36] A. Massaro and E. Benini, “A surrogate-assisted evolutionary algorithm based on the genetic diversity objective,” Applied Soft Computing, vol. 36, pp. 87-100, 2015.

[37] R. McNaughton, “Scheduling with deadlines and loss functions,” Management Science, vol. 6, no. 1, pp. 1-12, 1959.

[38] 0. J. Mengshoel and D. E. Goldberg, "The crowding approach to niching in genetic algorithms,” Evolutionary computation, vol. 16, no. 3, pp. 315–354, 2008.

[39] G. Mouzon and M. B. Yildirim, “A framework to minimise total energy con sumption and total tardiness on a single machine," International Journal of Sustainable Engineering, vol. 1, no. 2, pp. 105–116, 2008.

[40] F. T. Nobibon and R. Leus, "Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment," Computers & Operations Research, vol. 38, no. 1, pp. 367–378, 2011.

[41] C. Og, F. S. Salman, Z. B. Yalçın et al., "Order acceptance and scheduling decisions in make-to-order systems," International Journal of Production Economics, vol. 125, no. 1, pp. 200-211, 2010.

[42] V. Pandiyan, W. Caesarendra, T. Tjahjowidodo, and H. H. Tan, “In-process tool condition monitoring in compliant abrasive belt grinding process using support vector machine and genetic algorithm,” Journal of Manufacturing Processes, vol. 31, pp. 199-213, 2018.

[43] H. Peng and W. Wang, "Adaptive surrogate model based multi-objective trans fer trajectory optimization between different libration points,” Advances in Space Research, vol. 58, no. 7, pp. 1331-1347, 2016.

[44] W. 0. Rom and S. A. Slotnick, "Order acceptance using genetic algorithms," Computers & Operations Research, vol. 36, no. 6, pp. 1758–1767, 2009.

[45] D. E. Rumelhart, G. E. Hinton, and R. J. Williams, “Learning representations by back-propagating errors," nature, vol. 323, no. 6088, p. 533, 1986.

[46] N. Sadeh, “Look-ahead techniques for micro-opportunistic job shop scheduling," CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE, Tech. Rep., 1991.

[47] M. Salehi, M. Jalalian, and M. M. V. Siar, “Green transportation scheduling with speed control: trade-off between total transportation cost and carbon emission,” Computers & Industrial Engineering, vol. 113, pp. 392–404, 2017.

[48] M. Sayyafzadeh, “Reducing the computation time of well placement optimisa tion problems using self-adaptive metamodelling," Journal of Petroleum Science and Engineering, vol. 151, pp. 143-158, 2017.

[49] M. D. Schmid, “A neural network package for octave user's guide version: 0.1. 9.1.” 2009.

[50] H.-n. Shi, T. Ma, W.-x. Chu, and Q.-w. Wang, "Optimization of inlet part of a microchannel ceramic heat exchanger using surrogate model coupled with genetic algorithm," Energy Conversion and Management, vol. 149, pp. 988-996, 2017.

[51] F. Shrouf, J. Ordieres-Meré, A. García-Sánchez, and M. Ortega-Mier, “Optimizing the production scheduling of a single machine to minimize total energy consumption costs,” Journal of Cleaner Production, vol. 67, pp. 197–207, 2014.

[52] P. Snijders, E. D. de Jong, B. de Boer, and F. Weissing, “Multi-objective diversity maintenance,” in Proceedings of the 8th annual conference on Genetic and evolutionary computation. ACM, 2006, pp. 1429–1430.

[53] X. Sun, D. Gong, Y. Jin, and S. Chen, “A new surrogate-assisted interactive genetic algorithm with weighted semisupervised learning,” IEEE transactions on cybernetics, vol. 43, no. 2, pp. 685-698, 2013.

[54] S. Tanaka, "A unified approach for the scheduling problem with rejection," in 2011 IEEE International Conference on Automation Science and Engineering. IEEE, 2011, pp. 369-374.

[55] C.-K. Ting and H. Buning, “A mating strategy for multi-parent genetic algorithms by integrating tabu search," in Evolutionary Computation, 2003. CEC'03. The 2003 Congress on, vol. 2. IEEE, 2003, pp. 1259–1266.

[56] A. Toffolo and E. Benini, “Genetic diversity as an objective in multi-objective evolutionary algorithms," Evolutionary computation, vol. 11, no. 2, pp. 151– 167, 2003.

[57] H. Wang, Y. Jin, and J. O. Jansen, "Data-driven surrogate-assisted multiobjec tive evolutionary optimization of a trauma system.” IEEE Trans. Evolutionary Computation, vol. 20, no. 6, pp. 939–952, 2016.

[58] X. Xie and X. Wang, “An enhanced abe algorithm for single machine order acceptance and scheduling with class setups,” Applied Soft Computing, vol. 44, pp. 255-266, 2016.

[59] M. B. Yildirim and G. Mouzon, "Single-machine sustainable production planning to minimize total energy consumption and total completion time using a multiple objective genetic algorithm,” IEEE transactions on engineering management, vol. 59, no. 4, pp. 585-597, 2012.

[60] A.-C. Zăvoianu, G. Bramerdorfer, E. Lughofer, S. Silber, W. Amrhein, and E. P. Klement, “Hybridization of multi-objective evolutionary algorithms and artificial neural networks for optimizing the performance of electrical drives," Engineering Applications of Artificial Intelligence, vol. 26, no. 8, pp. 1781–1794, 2013.

[61] H. Zhang, F. Zhao, K. Fang, and J. W. Sutherland, “Energy-conscious flowshop scheduling under time-of-use electricity tariffs," CIRP Annals, vol. 63, no. 1, pp. 37–40, 2014.

[62] R. Zhang and R. Chiong, "Solving the energy-efficient job shop scheduling problem: a multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption," Journal of Cleaner Production, vol. 112, pp. 3361–3375, 2016.

[63] E. Zitzler, K. Deb, and L. Thiele, "Comparison of multiobjective evolutionary algorithms: Empirical results," Evolutionary computation, vol. 8, no. 2, pp. 173–195, 2000.