Call for Paper - August 2019 Edition
IJCA solicits original research papers for the August 2019 Edition. Last date of manuscript submission is July 20, 2019. Read More

A Performance Study for the Multi-objective Ant Colony Optimization Algorithms on the Job Shop Scheduling Problem

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2015
Authors:
I.D.I.D. Ariyasingha, T.G.I. Fernando
10.5120/ijca2015907638

I D I D Ariyasingha and T G I Fernando. Article: A Performance Study for the Multi-objective Ant Colony Optimization Algorithms on the Job Shop Scheduling Problem. International Journal of Computer Applications 132(14):1-8, December 2015. Published by Foundation of Computer Science (FCS), NY, USA. BibTeX

@article{key:article,
	author = {I.D.I.D. Ariyasingha and T.G.I. Fernando},
	title = {Article: A Performance Study for the Multi-objective Ant Colony Optimization Algorithms on the Job Shop Scheduling Problem},
	journal = {International Journal of Computer Applications},
	year = {2015},
	volume = {132},
	number = {14},
	pages = {1-8},
	month = {December},
	note = {Published by Foundation of Computer Science (FCS), NY, USA}
}

Abstract

Most of the research on job shop scheduling problem are concerned with minimization of a single objective. However, the real world applications of job shop scheduling problems are involved in optimizing multiple objectives. Therefore, in recent years ant colony optimization algorithms have been proposed to solve job shop scheduling problems with multiple objectives. In this paper, some recent multi-objective ant colony optimization algorithms are reviewed and are applied to the job shop scheduling problem by considering two, three and four objectives. Also in this study, four criteria: makespan, mean flow time, mean tardiness and mean machine idle time are considered for simultaneous optimization. Two types of models are used by changing the number of ants in a colony and each multi-objective ant colony optimization algorithm is applied to sixteen benchmark problem instances of up to 20 jobs X5 machines, for evaluating the performances of these algorithms. A detailed analysis is performed using the performance indicators, and the experimental results have shown that the performance of some multi-objective ant colony optimization algorithms depend on the number of objectives and the number of ants.

References

  1. I. Alaya, C. Solnon, and K. Ghedira. Ant colony optimization for multi-objective optimization problems. In 19th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2007), pages 450–457, Los Alamitos, CA, vol. 1, 2007. IEEE Computer Society Press.
  2. D. Angus. Crowding population-based ant colony optimization for the multi-objective travelling salesman problem. In Proceedings of the 2007 IEEE Symposium on Computational Intelligence in Multi-criteria Decision Making (MCDM 2007), pages 333–340. Honolulu, Hawaii, USA, IEEE Press, 2007.
  3. D. Angus and C. Woodward. Multiple objective ant colony optimisation. Swarm Intelligence, 3(1):69–85, 2009.
  4. I. D. I. D. Ariyasingha and T. G. I Fernando. Performance analysis of the multi-objective ant colony optimization algorithms for the traveling salesman problem. Swarm and Evolutionary Computation, 23:11–26, 2015.
  5. B. Baran and M. Schaerer. A multi objective ant colony system for vehicle routing problem with time windows. In Proceedings of the 21st IASTED International Conference on Applied Informatics, pages 97–102. Insbruck, Austria, February 10-13, 2003.
  6. L. T. Bui, J. M. Whitacre, and H. A. Abbass. Performance analysis of elitism in multi-objective ant colony optimization algorithms. In 2008 Congress on Evolutionary Computation (CEC2008), pages 1633–1640. Hong Kong, IEEE Service Center, 2008.
  7. K. Deb. Multi-objective Optimization using Evolutionary Algorithms. Wiley, 2001.
  8. M. Dorigo and T. Stutzle. Ant colony optimization. MIT Press, Cambridge, MA, 2004.
  9. C. Garcia-Martinez, O. Cordon, and F. Herrera. A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria tsp. European Journal of Operational Research, 180(1):116–148, 2007.
  10. M. R. Garey and D. S. Johnson. Computers abd Intertracability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, California, 1979.
  11. S. Lawrence. Resource Constrained Project Scheduling: An experimental Investigation of Heuristic Scheduling Techniques. Graduate School of Industrial Administration,Carnegie-Mellon University, Pittsburgh, Pennsylvania, 1984.
  12. M. Lopez-Ibanez and T. Stutzle. An experimental analysis of design choices for multi-objectives ant colony optimisation algorithms. Swarm Intelligence, 6(3):207–232, 2012.
  13. M. Pinedo. Scheduling: Theory, Algorithms, and Systems. Prentice-Hall, New York, 2001.
  14. A. Rabanimotlagh. An efficient ant colony optimization algorithm for multi-objective flow shop scheduling problem. World Academy of Science, Engineering and Technology, 75:127–133, 2011.
  15. I. Sabuncuoglu and M. Bayiz. Job shop scheduling with beam search. European Journal of Operational Research, 118:390– 412, 1999.
  16. P. Semanco and V. Modrak. A comparison of constructive heuristics with the objective of minimizing makespan in the flow-shop scheduling problem. 9(5), 2012.
  17. R. Shrivastava, S. Singh, and G. C. Dubey. Multi-objective optimization of time cost quality quantity using multi colony ant algorithm. International Journal of Contemporary Mathematical Sciences, 7:773–784, 2012.
  18. G. I. F. Thantulage. Ant colony optimization based simulation of 3D automatic hose / pipe routing. PhD Thesis, School of Engineering and Design, London, UK, March 2009.
  19. A. Udomsakdigool and V. Khachitvichyanukul. Ant colony algorithm for multi-criteria job shop scheduling to minimize makespan, mean flow time and mean tardiness. Int J Manag Sci Eng Manag, 6(2):117–123, 2011.
  20. M. Ventresca and B. Ombuki. Ant colony optimization for job shop scheduling problem. In Proceedings of the 8th International Conference on Artificial Intelligence and Soft Computing (ASC 2004). Marbella, Spain, September 2004, CDROM 451–152, 2004.

Keywords

Ant colony optimization, job shop scheduling problem, multiobjective problem, non-dominated solution, pareto optimal front, performance indicator