DocumentCode :
2233542
Title :
A Discrete Electromagnetism-Like Mechanism Algorithm for Solving Distributed Permutation Flowshop Scheduling Problem
Author :
Liu, Hongcheng ; Gao, Liang
Author_Institution :
State Key Lab. of Digital Manuf. Equip. & Technol., Huazhong Univ. of Sci. & Technol., Wuhan, China
fYear :
2010
fDate :
13-15 Dec. 2010
Firstpage :
156
Lastpage :
163
Abstract :
A distributed permutation flow shop scheduling problem (DPFSP) is an NP-hard problem recently put forward in shop scheduling sphere. Exact algorithms for a DPFSP´s solution can be extremely computationally costly. This paper proposes to apply an electromagnetism-like mechanism (EM) algorithm as a heuristic solution method to a DPFSP. To fit into the discrete domain of a DPFSP, modifications to the original EM algorithm, including redefinition of distance and movement and of charge and force calculation, have been made, to improve the performance of the proposed algorithm, a VNS local search mechanism employing the concept of the critical factory has been devised. The experimental results show the superiority of the proposed algorithm over the original EM algorithm. New best known solutions have been found to the Naderi´s DPFSP benchmark suite adapted from Tail lard instances.
Keywords :
computational complexity; electromagnetism; flow shop scheduling; search problems; NP-hard problem; VNS local search; critical factory; discrete electromagnetism; distributed permutation flowshop scheduling problem; force calculation; original EM algorithm; shop scheduling sphere; distributed permutation flowshop scheduling; electromagnetism-like mechanism algorithm; sequencing and scheduling;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Manufacturing Automation (ICMA), 2010 International Conference on
Conference_Location :
Hong Kong
Print_ISBN :
978-1-4244-9018-9
Electronic_ISBN :
978-0-7695-4293-5
Type :
conf
DOI :
10.1109/ICMA.2010.17
Filename :
5695172
Link To Document :
بازگشت