DocumentCode :
3112996
Title :
Ant colony optimization for solving a bi-criteria hybrid flow shop problem
Author :
Khalouli, Safa ; Ghedjati, Fatima ; Hamzaoui, Abdelaziz
Author_Institution :
CReSTIC-Reims, UFR Sci. Exactes et Naturelles, Reims
fYear :
2008
fDate :
12-15 Oct. 2008
Firstpage :
1440
Lastpage :
1445
Abstract :
In this paper we address a bi-criteria hybrid flow shop scheduling problem consisting in the earliness and tardiness penalties with different job due dates. This problem is proven to be NP-hard, and consequently the development of heuristic and meta-heuristic approaches to solve it is well justified. So, we propose an ant colony optimization method based on the ant colony system (ACS) to deal with this problem. Our proposed method has several features, including some heuristics that specifically take into account both earliness and tardiness penalties to compute the heuristic values. The performance of our ACS algorithm is tested by numerical experiments on a large number of randomly generated problems. A Comparison with solution performance obtained by some constructive heuristics based on some dispatching rules are presented. The results show that our proposed method performs better than the constructive heuristics.
Keywords :
computational complexity; flow shop scheduling; optimisation; NP-hard problem; ant colony optimization; ant colony system; bicriteria hybrid flow shop problem; constructive heuristics; dispatching rules; earliness penalties; job due dates; metaheuristic approaches; tardiness penalties; Ant colony optimization; Costs; Dispatching; Job production systems; Job shop scheduling; Manufacturing; Parallel machines; Random number generation; Single machine scheduling; Testing; ant colony optimization; ant colony system; bi-criteria; earliness/tardiness; hybrid flow shop; scheduling;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Systems, Man and Cybernetics, 2008. SMC 2008. IEEE International Conference on
Conference_Location :
Singapore
ISSN :
1062-922X
Print_ISBN :
978-1-4244-2383-5
Electronic_ISBN :
1062-922X
Type :
conf
DOI :
10.1109/ICSMC.2008.4811488
Filename :
4811488
Link To Document :
بازگشت