International Journal of Advanced and Applied Sciences

Int. j. adv. appl. sci.

EISSN: 2313-3724

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

Affiliation(s):

College of Business Administration, Northern Border University, Arar, Saudi Arabia

https://doi.org/10.21833/ijaas.2017.09.023

Full Text - PDF          XML

Abstract:

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: 

https://doi.org/10.21833/ijaas.2017.09.023

Citation:

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

Permanent link:

http://www.science-gate.com/IJAAS/V4I9/Allouche.html

References (24)

  1. 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 
  2. 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.     
  3. 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 
  4. 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 
  5. 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 
  6. 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 
  7. 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 
  8. 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 
  9. 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 
  10. 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 
  11. 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 
  12. 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 
  13. 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 
  14. 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 
  15. 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 
  16. 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 
  17. 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 
  18. 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 
  19. 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 
  20. 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 
  21. 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 
  22. 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 
  23. 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 
  24. 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.