A discrete electromagnetism-like mechanism for single machine total weighted tardiness problem with sequence-dependent setup times |
| |
| Authors: | Chien-Wen Chao Ching-Jong Liao |
| |
| Affiliation: | 1. College of Mathematics, Taiyuan University of Technology, Taiyuan, China;2. Department of Mathematics, City University of Hong Kong, Hong Kong SAR, China;3. Parks College of Engineering, Aviation and Technology, Saint Louis University, St. Louis, MO 63103, USA;4. School of Engineering and Materials Science, Queen Mary, University of London, London E1 4NS, UK;1. School of Mechanical and Power Engineering, East China University of Science and Technology, 130 Meilong, Xuhui, Shanghai 200237, China;2. Department of Quantum Science and Energy Engineering, Graduate School of Engineering, Tohoku University, 6-6 Aramaki Aza Aoba, Aoba-Ku, Sendai, Miyagi 980-8579, Japan;3. Trueflaw Ltd., Tillinmäentie 3, tila A113, 02330 Espoo, Finland;1. Department of Mathematics, University of California, Irvine CA 92697, USA;2. Department of Ecology and Evolutionary Biology, University of California, Irvine CA 92697, USA;1. Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China;2. LSEC, China;3. NCMIS, China;4. Computer Network Information Center, Chinese Academy of Sciences, Beijing, 100190, China;1. Graduate School of Human and Environmental Studies, Kyoto University, Kyoto, 606-8501, Japan;2. Department of Mathematics, City University of Hong Kong, Hong Kong, PR China;3. Department of Mathematics, City University of Hong Kong, Hong Kong, PR China |
| |
| Abstract: | Electromagnetism-like mechanism (EM) is a novel meta-heuristic, inspired by the attraction–repulsion mechanism of electromagnetic theory. There are very few applications of EM in scheduling problems. This paper presents a discrete EM (DEM) algorithm for minimizing the total weighted tardiness in a single-machine scheduling problem with sequence-dependent setup times. Unlike other discrete EM algorithms that use a random key method to deal with the discreteness, the proposed DEM algorithm employs a completely different approach, with an attraction–repulsion mechanism involving crossover and mutation operators. The proposed algorithm not only accomplishes the intention of an EM algorithm but also can be applied in other combinatorial optimization problems. 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 algorithm 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 algorithm, while other another 70 instances are solved to an equivalent degree. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
