International Journal of Advanced and Applied Sciences
Int. j. adv. appl. sci.
Print ISSN: 2313-626X
Volume 4, Issue 9 (September 2017), Pages: 161-167
Title: Multicriteria scheduling problem: a hybrid ant colony algorithm integrating the decision-maker’s preferences
Author(s): Mohamed Anis Allouche *, Tahar Jouili, Mohamed Ali Omri
College of Business Administration, Northern Border University, Arar, Saudi Arabia
Full Text - PDF XML
The aim of this paper is to present a new hybrid metaheuristic approach based on Ant colony algorithm and the variable neighborhood search noted by ACS_VNS to solve a permutation flowshop scheduling problem. In this context, several criteria are considered which are: the makespan, the total flowtime and the total tardiness of jobs. The proposed approach uses the compromise programming model and the concept of satisfaction function taking into account, explicitly, the decision-maker preferences (DMP). It has been tested through a computational experiment and the obtained results are compared to others for all criteria and for the makespan criterion. The obtained results show the performance of the proposed approach which can be considered as a good tool for multicriteria scheduling problem, especially since it does not necessitate a long computational time.
© 2017 The Authors. Published by IASE.
This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
Keywords: Multicriteria scheduling problem, Ant colony algorithm, Variable neighborhood search, Satisfaction functions, Decision-maker’s preferences
Article History: Received 18 May 2017, Received in revised form 8 August 2017, Accepted 8 August 2017
Digital Object Identifier:
Allouche MA, Jouili T, and Omri MA (2017). Multicriteria scheduling problem: a hybrid ant colony algorithm integrating the decision-maker’s preferences. International Journal of Advanced and Applied Sciences, 4(9): 161-167
- Allouche M, Aouni B, Martel J, Loukil T, and Rebaï A (2009). Solving multi-criteria scheduling flow shop problem through compromise programming and satisfaction functions. European Journal of Operational Research, 192(2): 460-467. https://doi.org/10.1016/j.ejor.2007.09.038
- Allouche MA (2010). Manager's preferences modeling within multi-criteria flowshop scheduling problem: A metaheuristic approach. International Journal of Business Research and Management ISSN, 1(2): 33-45.
- Chang P, Chen S, Fan C, and Chan C (2008). Genetic algorithm integrated with artificial chromosomes for multi-objective flowshop scheduling problems. Applied Mathematics and Computation, 205(2): 550-561. https://doi.org/10.1016/j.amc.2008.05.027
- Daniels RL and Chambers RJ (1990). Multiobjective flow‐shop scheduling. Naval Research Logistics (NRL), 37(6): 981-995. https://doi.org/10.1002/1520-6750(199012)37:6<981::AID-NAV3220370617>3.0.CO;2-H
- Dorigo M, Maniezzo V, and Colorni A (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1): 29-41. https://doi.org/10.1109/3477.484436 PMid:18263004
- Eren T (2007). A multicriteria flowshop scheduling problem with setup times. Journal of Materials Processing Technology, 186(1): 60-65. https://doi.org/10.1016/j.jmatprotec.2006.12.022
- Gagné C, Gravel M, and Price W (2004). Optimisation multi-objectifs à l'aide d'un algorithme de colonie de fourmis. INFOR: Information Systems and Operational Research, 42(1): 23-42. https://doi.org/10.1080/03155986.2004.11732689
- Gagné C, Gravel M, and Price W (2005). Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems. Journal of the Operational Research Society, 56(6): 687-698. https://doi.org/10.1057/palgrave.jors.2601868
- Gambardella LM and Dorigo M (1995). Ant-Q: A reinforcement learning approach to the traveling salesman problem. In the 12th International Conference on Machine Learning, Morgan Kaufmann, Burlington, USA: 252–260. https://doi.org/10.1016/B978-1-55860-377-6.50039-6
- Gambardella LM and Dorigo M (1996). Solving symmetric and asymmetric TSPs by ant colonies. In the IEEE International Conference on Evolutionary Computation, IEEE, Nagoya, Japan: 622-627. https://doi.org/10.1109/ICEC.1996.542672
- Gangadharan R and Rajendran C (1994). A simulated annealing heuristic for scheduling in a flowshop with bicriteria. Computers and Industrial Engineering, 27(1-4): 473-476. https://doi.org/10.1016/0360-8352(94)90337-9
- Hansen P and Mladenović N (1997). Variable neighborhood search for the p-median. Location Science, 5(4): 207-226. https://doi.org/10.1016/S0966-8349(98)00030-8
- Javadi B, Saidi-Mehrabad M, Haji A, Mahdavi I, Jolai F, and Mahdavi-Amiri N (2008). No-wait flow shop scheduling using fuzzy multi-objective linear programming. Journal of the Franklin Institute, 345(5): 452-467. https://doi.org/10.1016/j.jfranklin.2007.12.003
- Lin B, Lu C, Shyu S, and Tsai C (2008). Development of new features of ant colony optimization for flowshop scheduling. International Journal of Production Economics, 112(2): 742-755. https://doi.org/10.1016/j.ijpe.2007.06.007
- Loukil T, Teghem J, and Tuyttens D (2005). Solving multi-objective production scheduling problems using metaheuristics. European Journal of Operational Research, 161(1): 42-61. https://doi.org/10.1016/j.ejor.2003.08.029
- Martel J and Aouni B (1990). Incorporating the decision-maker's preferences in the goal-programming model. Journal of the Operational Research Society, 41(12): 1121-1132. https://doi.org/10.1057/jors.1990.179
- Qian B, Wang L, Huang D, Wang W, and Wang X (2009). An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Computers and Operations Research, 36(1): 209-233. https://doi.org/10.1016/j.cor.2007.08.007
- Rajendran C and Ziegler H (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155(2): 426-438. https://doi.org/10.1016/S0377-2217(02)00908-6
- Ruiz R and Allahverdi A (2009). Minimizing the bicriteria of makespan and maximum tardiness with an upper bound on maximum tardiness. Computers and Operations Research, 36(4): 1268-1283. https://doi.org/10.1016/j.cor.2007.12.013
- Taillard E (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2): 278-285. https://doi.org/10.1016/0377-2217(93)90182-M
- Tavakkoli-Moghaddam R, Rahimi-Vahed AR, and Mirzaei AH (2007). Solving a bi-criteria permutation flow shop problem using immune algorithm. In the IEEE Conference on Computational Intelligence in Scheduling, IEEE, Honolulu, USA: 49-56. https://doi.org/10.1109/SCIS.2007.367669
- T'kindt V and Billaut JC (2002). Multicriteria Scheduling: Theory, Models and algorithms. Springer-Verlag, Berlin, Germany. https://doi.org/10.1007/978-3-662-04986-0
- Varadharajan T and Rajendran C (2005). A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs. European Journal of Operational Research, 167(3): 772-795. https://doi.org/10.1016/j.ejor.2004.07.020
- Zeleny M (1973). Compromise programming. In: Zeleny M and Cochrane JL (Eds.), Multiple criteria decision making: 262–301. University of South Carolina Press, South Carolina, Columbia.