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

作者：Tavakkoli Moghaddam R^*; Khalili M; Naderi B

来源：Soft Computing, 2009, 13(10): 995-1006.

DOI：10.1007/s00500-008-0367-z

• Job shop
• Sequence-dependent setup times
• Machine availability constraints
• Simulated annealing
• Electromagnetism-like mechanism
• Hybrid meta-heuristic method

In this paper, we explore job shop problems with two recently popular and realistic assumptions, sequence-dependent setup times and machine availability constraints to actualize the problem. The criterion is a minimization of total weighted tardiness. We establish a simple criterion to integrate machine availability constraints and scheduling decisions simultaneously. We propose a hybrid meta-heuristic to tackle the given problem. This meta-heuristic method, called EMSA, is a combination of two meta-heuristics: (1) Electromagnetic-like mechanism (EM); and (2) simulated annealing (SA). The hybridization is done to overcome some existing drawbacks of each of these two algorithms. To evaluate the proposed hybrid meta-heuristic method, we carry out a benchmark by which the proposed EMSA is compared with some existing algorithms as well as simulated annealing and electromagnetic-like mechanism alone in a fixed given computational time. All the related results and analysis obtained through the benchmark illustrate that our proposed EMSA is very effective and supersedes the foregoing algorithms.

• 出版日期2009-8