Solving multi-objective job shop problem using nature-based algorithms: new Pareto approximation features

Jarosław Rudy, Dominik Żelazny

Abstract


In this paper the job shop scheduling problem (JSP) with minimizing two criteria simultaneously is considered. JSP is frequently used model in real world applications of combinatorial optimization. Multi-objective job shop problems (MOJSP) were rarely studied. We implement and compare two multi-agent nature-based methods, namely ant colony optimization (ACO) and genetic algorithm (GA) for MOJSP. Both of those methods employ certain technique, taken from the multi-criteria decision analysis in order to establish ranking of solutions. ACO and GA differ in a method of keeping information about previously found solutions and their quality, which affects the course of the search. In result, new features of Pareto approximations provided by said algorithms are observed: aside from the slight superiority of the ACO method the Pareto frontier approximations provided by both methods are disjoint sets. Thus, both methods can be used to search mutually exclusive areas of the Pareto frontier.

Keywords


Multi-objective optimization; job shop scheduling; multi-criteria decision analysis; nature inspired

Full Text:

PDF

References


Bozejko W., Pempera J., Smutnicki C., Parallel Simulated Annealing for the Job Shop Scheduling Problem Lecture Notes in Computer Science, Vol. 5544, pp 631–640 (2009).

Deb K., Pratap A., Agarwal S., Meyarivan T., A fast and elitist multi–objective genetic algorithm: NSGA–II, IEEE Trans. EVol. Comput., Vol. 6 (2), pp 182–197 (2002). Crossref

Dorigo M., Maniezzo V., Colorni A., Ant System: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and CyberneticsPart B, Vol. 26 (1), pp 29–41 (1996). Crossref

Fattahi P., Saidi Mehrabad M., Arynezhad M. B., An algorithm for multi objective job shop scheduling problem, Journal of Industrial International, Vol. 2 (3), pp 43–53 (2006).

Garey M., Johnson, D., Computers and Intractability: A Guide to the Theory of NP–Completeness, W. H. Freeman & Co. New York, USA, (1979).

Giffler B., Thompson G. L., Algorithms for Solving Production–Scheduling Problems, Operations Research, Vol. 8 (4), pp 487–503 (1960).

Hwang C.L., Yoon K., Multiple Attribute Decision Making: Methods and Applications, Springer–Verlag, New York (1981). Crossref

Jagie l lo S., Zelazny D., Solving multi-criteria vehicle routing problem by parallel tabu search on GPU, Procedia Computer Science, Vol. 18, pp 2529–2532 (2013). Crossref

Kachitvichyanukul V., Sitthitham S., A two–stage genetic algorithm for multi–objective job shop scheduling problems, Journal of Intelligent Manufacturing, Vol. 22 (3), pp 355–365 (2011). Crossref

Lam N. V., Kachitvichyanukul V., Luong H. T., A multi–stage parallel genetic algorithm for multi–objective job shop scheduling, The 6th Asia Pacific Industrial Engineering and Management Systems Conference (APIEMS 2005), Philippines (2005).

Lei D., A Pareto archive particle swarm optimization for multi–objective job shop scheduling, Computers and Industrial Engineering, Vol. 54 (4), pp 960-971 (2008). Crossref

Lei D., Wu Z., Crowding–measure–based multi–objective evolutionary algorithm for job shop scheduling, International Journal of Advanced Manufacturing Technology, Vol.30, pp 112–117 (2006). Crossref

Nowicki E., Smutnicki C., Some new ideas in TS for job shop scheduling, Metaheuristic optimization via memory and evolution. Tabu search and scatter search. Kluwer Academic Publ., pp 165-190 (2005).

Pempera J., Smutnicki C., Zelazny D., Optimizing bicriteria flow shop scheduling problem by simulated annealing algorithm, Procedia Computer Science, Vol. 18, pp 936-945 (2013). Crossref

Ripon K. S. N., Hybrid evolutionary approach for multi–objective job shop scheduling problem, Malaysian Journal of Computer Science, Vol. 20 (2), pp 183–198 (2007).

Ripon K. S. N., Siddique N. H., Torresen J., Improved precedence preservation crossover for multi–objective job shop scheduling problem, Evolving Systems, Vol. 2 (2), pp 119–129 (2011). Crossref

Rudy J., Zelazny D., Memetic algorithm approach for multi-criteria network scheduling, Proceeding of the International Conference on ICT Management for Global Competitiveness and Economic Growth in Emerging Economies, pp 247–261 (2012).

Sha D. Y., Lin H–H., A multi–objective PSO for job–shop scheduling problems, Expert Systems with Applications, Vol. 37 (2), pp 1065–1070 (2010). Crossref

Stutzle T., Hoos, H. H., MAXMIN Ant System, Future Generation Computer Systems, Vol. 16 (8), pp. 889–914 (2000).

Suresh R.K., Mohanasndaram K.M., Pareto archived simulated annealing for job shop scheduling with multiple objectives, International Journal of Advanced Manufacturing Technology, Vol. 29, pp 184 –196 (2006). Crossref

Taillard E., Benchmarks for basic scheduling problems, European Journal of Operational Research, Vol. 64, pp 278-285 (1993).

Crossref

Udomsakdigoola A., Khachitvichyanukul V., Ant colony algorithm for multi–criteria job shop scheduling to minimize makespan, mean flow time and mean tardiness, International Journal of Management Science and Engineering Management, Volume 6 (2), pp 117–123 (2011).

Vazquez–Rodriguez J. A., Petrovic S., A new dispatching rule based genetic algorithm for the multi–objective job shop problem, Journal of Heuristics, Vol. 16 (6), pp 771–793 (2010). Crossref

Xionga J., Xinga L-N., Chena Y-W, Robust scheduling for multi-objective flexible jobshop problems with random machine breakdowns, International Journal of Production Economics, Vol. 141(1), pp 112–126 (2013). Crossref

Zitzler E., Thiele L., Laumanns M., Fonseca C. M., Fonseca V., Performance assessment of multi–objective optimizers: An analysis and review, IEEE Trans. Comput., Vol. 7 (2), pp 117–132 (2003).




DOI: http://dx.doi.org/10.11121/ijocta.01.2015.00232

Refbacks

  • There are currently no refbacks.


Copyright (c) 2015 Jarosław Rudy, Dominik Żelazny

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

footer_771

   ithe_170     crossref_284         ind_131_43_x_117_117  Scopus  EBSCO_Host    ULAKBIM     ZBMATH more...