仿電磁演算法為近年來發展出的新興共通啟發式演算法，主要啟發自電磁吸引與排斥理論，目前已發展出連續型與離散型兩種版本以求解最佳化問題，但應用於排程問題上仍相當稀少；因此，本論文以仿電磁演算法為基礎，發展新興的「熱帶氣旋演算法」。更進一步，提出新興離散型仿電磁演算法，用以求解流程型工廠與單機環境下之兩種排程問題。
本論文首先提出新興共通啟發式演算法「熱帶氣旋演算法」，以求解具上下界限制之最佳化問題。此方法係模擬大氣中熱帶氣旋的形成，透過粒子移動過程來搜尋最佳解。由於形成熱帶氣旋的確切因素至今尚無定論，本論文根據目前已知，以氣體流動、空氣擾動及對流等三項主要因素來搜尋最佳解。經應用於各種非線性方程式，實驗結果證明熱帶氣旋演算法明顯優於仿電磁演算法。
在第二部份，本研究將探討流程型工廠之最佳化排程問題。由於此問題的高度複雜度，目前已知的最佳化演算法僅能求解小問題；因此，本論文發展新興啟發式演算法「離散型仿電磁演算法」，能夠在合理的計算時間內得到近似最佳解。相較於其它離散型仿電磁演算法，本方法採用交配與突變的方式來執行吸引與排斥的機制，以最小化流程型工廠之完工時間。經實驗證明，本論文提出之演算法顯著優於目前已知的兩個離散型仿電磁演算法。
第三部份中，針對具有相依整備時間的單機環境，提出更有效的離散型仿電磁演算法以最小化總加權延遲時間。主要改善方式為採用更複雜的排斥機制，以及加入有效的局部搜尋法。與目前最佳之「離散型微分進化演算法」比較結果，在120個標竿題目中，提出之演算法能夠更新30個標竿題目，且其餘70個標竿題目也都能達到相同的解，顯示提出之演算法能更有效地求解此問題。

Electromagnetism-like mechanism (EM) is a novel meta-heuristic, inspired by the attraction and repulsion mechanism. In recent years, the continuous and discrete versions of EM have been developed for solving global optimization problems. However, the applications of EM to scheduling problems are extremely few. This dissertation studies the properties and characteristics of EM and constructs a new meta-heuristic, named tropical cyclone-based method. Then, this dissertation focuses on developing an efficient discrete EM to solve scheduling problems. Different scheduling problems are considered in this dissertation including the single machine and flowshop scheduling problems. The content of each chapter in the dissertation is sketched below.
First, this dissertation proposes a new meta-heuristic, tropical cyclone-based method (TCM), for solving global optimization problems with box constraints. TCM mimics the formation process of tropical cyclones in the atmosphere to move a set of sample points towards optimality. The formation of a tropical cyclone in nature is still not completely understood by people. Nevertheless, inspired by the known formation factors of a tropical cyclone, TCM is designed to seek optimal solutions by considering airflow, disturbance, and convection in order to traverse the solution space. Experimental results on some well-known nonlinear test functions are included. Compared with the well-known electromagnetism-like mechanism, TCM is both effective and efficient for solving the reported test functions.
Second, this dissertation addresses the permutation flow-shop scheduling problem (PFSP), which is one of the hardest combinatorial optimization problems. As the computational complexity of PFSP, the current exact methods are limited to solve small to moderate size problems. Hence, lots of meta-heuristics have been developed for PFSP to obtain a near-optimal solution within a reasonable computational time. This dissertation presents a new discrete EM (DEM) for minimizing the makespan of PFSP. In our algorithm, this dissertation proposes an attraction-repulsion mechanism involving crossover and mutation operators. To validate the proposed algorithm, comparisons with two other discrete EMs are conducted. Computational results show that the proposed DEM is the best of the three versions.
Finally, this dissertation presents a discrete EM (DEM) for minimizing the total weighted tardiness in a single-machine scheduling problem with sequence-dependent setup times. The proposed DEM adopts a more complicated procedure to execute the repulsion mechanism and involves an effective local search. To verify the algorithm, it is compared with a discrete differential evolution (DDE) algorithm, which is the best meta-heuristic for the considered problem. Computational experiments show that the performance of the proposed DEM is better than that of the DDE algorithm in most benchmark problem instances. Specifically, 30 out of 120 aggregated best-known solutions in the literature are further improved by the DEM, while other another 70 instances are solved to an equivalent degree.

Allahverdi, A., Gupta, J.N.D., Aldowaisan, T.A., 1999. A review of scheduling research involving setup considerations. OMEGA 27, 219-239.
Andreas, N., Omirou, S., 2006. Differential evolution for sequencing and scheduling optimization. Journal of Heuristics 12, 395-411.
Anghinolfi, D., Paolucci, M., 2009. A new discrete particle swarm optimization approach for the single machine total weighted tardiness scheduling problem with sequence dependent setup times. European Journal of Operational Research 193, 73-85.
Anghinolfi, D., Paolucci, M., 2008. A new ant colony optimization approach for the single machine total weighted tardiness scheduling problem. International Journal of Operations Research 5, 1-17.
Armentano, V.A., Mazzini, R., 2000. A genetic algorithm for scheduling on a single machine set-up times and due dates. Production Planning & Control 11, 713-720.
Birbil, Ş.İ., Fang, S.-C., Sheu, R.-L., 2004. On the convergence of a population-based global optimization algorithm. Journal of Global Optimization 30, 301-318.
Birbil, Ş.İ., Fang, S.-C., 2003. An electromagnetism-like mechanism for global optimization. Journal of Global Optimization 25, 263-282.
Campbell, H.G., Dudek, R.A., Smith, M.L., 1970. A heuristic algorithm for the n job, m machine sequencing problem. Management Science 16, B630-B637.
Chang, P.-C., Chen, S.-H., Fan, C.-Y., 2009. A hybrid electromagnetism-like algorithm for single machine scheduling problem. Expert Systems with Applications 36, 1259-1267.
Chen, C.-L., Vempati, V.S., Aljaber, N., 1995. An application of genetic algorithms for flow shop problems. European Journal of Operational Research 80, 389-396.
Cicirello, V.A., Smith, S.F., 2005. Enhancing stochastic search performance by value-based randomization of heuristics. Journal of Heuristics 11, 5-34.
Cowan, E.W., 1968. Basic Electromagnetism. Academic Press, NY, USA.
Dannenbring, D.G., 1977. An evaluation of flow shop sequencing heuristics. Management Science 23, 1174-1182.
Das, S.R., Gupta, J.N.D., Khumawala, B.M., 1995. A saving index heuristic algorithm for flowshop scheduling with sequence dependent set-up times. Journal of the Operational Research Society 46, 365-373.
David, L., 2008. Encyclopedia of Hurricanes, Typhoons, and Cyclones. Facts on File, NY, USA. pp. 112-115.
Debels, D., Vanhoucke, M., 2006. The electromagnetism meta-heuristic applied to the resource-constrained project scheduling problem. Lecture Notes in Computer Science 3871, 259-270.
Demirhan, M., Ozdamar, L., Helvacıoĝlu, L., Birbil, Ş.İ., 1999. FRACTOP: A geometric partitioning metaheuristic for global optimization. Journal of Global Optimization 14, 415-435.
Dixon, L.C.W., Szego, G.P., 1978. The global optimization problem: An introduction. Towards Global Optimization, Vol. 2, Edited by L.C.W. Dixon and G.P. Szego, North-Holland, Amsterdam, 1-15.
Dorigo, M., 1992. Optimization, Learning, and Natural Algorithms. PhD Thesis, Dip. Elettronica, Politecnico di Milano, Italy.
Du, J., Leung, J.Y.T., 1990. Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research 15, 483-494.
Etiler, O., Toklu, B., Atak, M., Wilson, J., 2004. A genetic algorithm for flow shop scheduling problems. Journal of the Operational Research Society 55, 830-835.
Forbes, N., 2004. Imitation of Life: How Biology Is Inspiring Computing. MIT Press, MA, USA.
Franca, P.M., Mendes, A., Moscato, P., 2001. A memetic algorithm for the total tardiness single machine scheduling problem. European Journal of Operational Research 132, 224-242.
Frank, W.M., 1987. Tropical cyclone formation. A Global View of Tropical Cyclones. Edited by R.L. Elsberry, U.S. Office of Naval Research, Marine Meteorology Program, Washington, DC, USA. pp. 53-90.
Gagne, C., Price, W.L., Gravel, M., 2002. Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times. Journal of the Operational Research Society 53, 895-906.
Glover, F., 1986. Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13, 533-549.
Grabowski, J., Wodecki, M., 2004. A very fast tabu search algorithm for the permutation flowshop problem with makespan criterion. Computers & Operations Research 31, 1891-1909.
Gravel, M., Price, W.L., Gagne, C., 2000. Scheduling jobs in an Alcan aluminium factory using a genetic algorithm. International Journal of Production Research 38, 3031-3041.
Holland, J.H., 1975. Adaptation in Natural and Artificial System: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. Ann Arbor, Michigan, University of Michigan Press, USA.
Huyer, W., Neumaier, A., 1999. Global optimization by multilevel coordinate search. Journal of Global Optimization 14, 331-355.
Ignall, E., Schrage, L., 1965. Application of the branch-and-bound technique to some flowshop scheduling problems. Operations Research 13, 400-412.
Javadian, N., Gol Alikhani, M., Tavakkoli-Moghaddam, R., 2009. Solving a single machine scheduling problem by a discrete version of electromagnetism-like method. Journal of Circuits, Systems, and Computers 18, 1597-1608.
Javadian, N., Gol Alikhani, M., Tavakkoli-Moghaddam, R., 2008. A discrete binary version of the electromagnetism-like heuristic for solving traveling salesman problem. Lecture Notes in Computer Science 5227, 123-130.
Karaboga, D., 2005. An idea based on honey bee swarm for numerical optimization. Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department.
Kennedy, J., Eberhart, R., 1995. Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, USA, pp. 1942-1948.
Lawler, E.L., 1997. A ‘pseudopolynomial’ algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics 1, 331-342.
Lee, Y.H., Bhaskaram, K., Pinedo, M., 1997. A heuristic to minimize the total weighted tardiness with sequence-dependent setups. IIE Transactions 29, 45-52.
Lian, Z., Gu, X., Jiao, B., 2006. A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan. Applied Mathematics and Computation 175, 779-785.
Liao, C.-J., Juan, H.-C., 2007. An ant colony optimization for single machine tardiness scheduling with sequence dependent setups. Computers & Operations Research 34, 1899-1909.
Liao, C.-J., Tseng, C.-T., Luarn, P., 2007. A discrete version of particle swarm optimization for flowshop scheduling problems. Computers & Operations Research 34, 3099-3111.
Lin, S.-W., Ying, K.-C., 2007. Solving single-machine total weighted tardiness problems with sequence-dependent setup times by meta-heuristics. International Journal of Advanced Manufacturing Technology 34, 1183-1190.
Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E., 1953. Equation of state calculations by fast computing machines. Journal of Chemical Physics 21, 1087-1092.
Mirabi, M., Fatemi Ghomi, S.M.T., Jolai, F., Zandieh, M., 2008. Hybrid electromagnetism-like algorithm for the flowshop scheduling with sequence- dependent setup times. Journal of Applied Sciences 8, 3621-3629.
Bonyadi, M.R., Li, X., 2010. A new discrete electromagnetism-based meta-heuristic for solving the multidimensional knapsack problem using genetic operators. Operational Research, DOI 10.1007/s12351-010-0084-0.
More, J.J., Wu, Z., 1995. Global smoothing and continuation for large-scale molecular optimization. Argonne National Laboratory, Illinois: Preprint MCS-P539-1095, USA.
Naderi, B., Tavakkoli-Moghaddam, R., Khalili, M., 2010. Electromagnetism-like mechanism and simulated annealing algorithms for flowshop scheduling problems minimizing the total weighted tardiness and makespan. Knowledge- Based Systems 23, 77-85.
Nawaz, M., Enscore, Jr. E.E., Ham, I.A., 1983. Heuristic algorithm for the m-machine, n-job flow shop sequencing problem. OMEGA 11, 91-95.
Ogbu, F., Smith, D., 1990. The application of the simulated annealing algorithm to the solution of the flowshop problem. Computers & Operations Research 17, 243-253.
Onwubolu, G., Davendra, D., 2006. Scheduling flow shops using differential evolution algorithm. European Journal of Operational Research 171, 674-692.
Pan, Q.-K., Tasgetiren, M.F., Liang, Y.-C., 2008. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Computers & Industrial Engineering 55, 795-816.
Pan, Q.-K., Tasgetiren, M.F., Liang, Y.-C., 2008. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem with makespan and total flowtime criteria. Computers & Operations Research 35, 2807-2839.
Pan, Q.-K., Tasgetiren, M.F., Liang, Y.-C., 2006. A discrete particle swarm optimization algorithm for the permutation flowshop sequencing problem with makespan criterion. In: Proceedings of the 26th SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence (AI-2006), Cambridge, UK, pp. 19-31.
Pielke, Jr., R.A., Pielke, Sr., R.A., 1997. Hurricanes: Their Nature and Impacts on Society. John Wiley and Sons Press, London, pp. 68-91.
Rajendran, C., Ziegler, H., 2004. Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research 155, 426-438.
Rinnooy Kan, A.H.G., 1976. Machine Scheduling Problems: Classification, Complexity, and Computations. PhD Thesis, University of Amsterdam, Holland.
Roshanaei, V., Khaleghei, A., Balagh, G., Esfahani, M.M.S., Vahdani, B., 2010. A mixed-integer linear programming model along with an electromagnetism-like algorithm for scheduling job shop production system with sequence-dependent set-up times. International Journal of Advanced Manufacturing Technology 47, 783-793.
Rubin, P.A., Ragatz, G.L., 1995. Scheduling in a sequence-dependent setup environment with genetic search. Computers & Operations Research 22, 85-99.
Ruiz, R., Stutzle, T., 2007. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research 177, 2033-2049.
Ruiz, R., Maroto, C., 2005. A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research 165, 479-494.
Schoen, F., 1989. A wide class of test functions for global optimization. In: Proceedings of the 3rd International Conference on Genetic Algorithms, Fairfax, VA, USA, pp. 51-60.
Stafford, E.F., 1988. On the development of a mixed integer linear programming model for the flowshop sequencing problem. Journal of Operational Research Society 39, 1163-1174.
Stutzle, T., 1998. Applying iterated local search to the permutation flowshop problem. Technical Report, AIDA-98-04, FG Intellektik, FB Informatik, TU Darmstadt.
Taillard, E., 1993. Benchmarks for basic scheduling problems. European Journal of Operational Research 64, 278-285.
Taillard, E., 1990. Some efficient heuristic methods for the flowshop sequencing problems. European Journal of Operational Research 47, 65-74.
Tan, K.C., Narasimhan, R., 1997. Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach. OMEGA 25, 619-634.
Tasgetiren, M.F., Pan, Q.K., Liang, Y.C., 2009. A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times. Computers & Operations Research 36, 1900-1915.
Tavakkoli-Moghaddam, R., Khalili, M., Naderi, B., 2009. A hybridization of simulated annealing and electromagnetic-like mechanism for job shop problems with machine availability and sequence-dependent setup times to minimize total weighted tardiness. Soft Computing 13, 995-1006.
Torn, A., Ali, M.M., Viitanen, S., 1999. Stochastic global optimization: problem classes and solution techniques. Journal of Global Optimization 14, 437-447.
Valente, J.M.S., Alves, R.A.F.S., 2008. Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups. Computers & Operations Research 35, 2388-2405.
Watson, J.P., Barbulescu, L., Whitley, L.D. Howe, A.E., 2002. Contrasting structured and random permutation flowshop scheduling problems: Search space topology and algorithm performance. ORSA Journal of Computing 14, 98-123.
Wu, P., Yang, K.-J., Hung, Y.-Y., 2005. The study of electromagnetism-like mechanism based fuzzy neural network for learning fuzzy if-then rules. Knowledge-based Intelligent Information and Engineering Systems 3687, 382-388
Yu, L., 2011. An electromagnetism-like method for solving linearly and convex quadratically constrained optimization problems. PhD Thesis, Department of Industrial and Systems Engineering, North Carolina State University, USA.
Yurtkuran, A., Emel, E., 2010. A new hybrid electromagnetism-like algorithm for capacitated vehicle routing problems. Expert Systems with Applications 37, 3427-3433.