Dominik ZELAZNY, Jaros law RUDY

176

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

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

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 combinatorialoptimization. Multi-objective job shop problems (MOJSP) were rarely studied. We implement andcompare two multi-agent nature-based methods, namely ant colony optimization (ACO) and geneticalgorithm (GA) for MOJSP. Both of those methods employ certain technique, taken from the multicriteria decision analysis in order to establish ranking of solutions. ACO and GA differ in a methodof keeping information about previously found solutions and their quality, which affects the course ofthe 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 byboth methods are disjoint sets. Thus, both methods can be used to search mutually exclusive areas ofthe Pareto frontier.
PDF

___

  • [1] Bo?zejko 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).
  • [2] 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).
  • [3] 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).
  • [4] 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).
  • [5] Garey M., Johnson, D., Computers and Intractability: A Guide to the Theory of NP- Completeness, W. H. Freeman & Co. New York, USA, (1979).
  • [6] Giffler B., Thompson G. L., Algorithms for Solving Production-Scheduling Problems, Operations Research, Vol. 8 (4), pp 487-503 (1960).
  • [7] Hwang C.L., Yoon K., Multiple Attribute Decision Making: Methods and Applications, Springer-Verlag, New York (1981).
  • [8] 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).
  • [9] 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).
  • [10] 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).
  • [11] Lei D., A Pareto archive particle swarm optimization for multi-objective job shop scheduling, Computers and Industrial Engineering, Vol. 54 (4), pp 960971 (2008).
  • [12] 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).
  • [13] 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).
  • [14] Pempera J., Smutnicki C., Zelazny D., Opti- ? mizing bicriteria flow shop scheduling problem by simulated annealing algorithm, Procedia Computer Science, Vol. 18, pp 936-945 (2013).
  • [15] 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).
  • [16] 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).
  • [17] Rudy J., Zelazny D., Memetic algorithm ap- ? proach 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).
  • [18] 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).
  • [19] St¨utzle T., Hoos, H. H., MAXMIN Ant System, Future Generation Computer Systems, Vol. 16 (8), pp. 889-914 (2000).
  • [20] 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).
  • [21] Taillard E., Benchmarks for basic scheduling problems, European Journal of Operational Research, Vol. 64, pp 278-285 (1993).
  • [22] 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).
  • [23] V´azquez-Rodr´ıguez 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).
  • [24] 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).
  • [25] 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).
An International Journal of Optimization and Control: Theories & Applications (IJOCTA)-Cover
  • ISSN: 2146-0957
  • Yayın Aralığı: Yılda 2 Sayı
  • Yayıncı: Prof. Dr. Ramazan YAMAN
Arşiv
Sayıdaki Diğer Makaleler

On constrained reliability maximization using active redundancy in coherent systems with non-overlapping subsystems

Debasis BHATTACHARYA, Soma ROYCHOWDHURY

An EPQ model with imperfect items using interval grey numbers

Fevzi BEDİR, Erdal AYDEMİR, Gultekin OZDEMİR, Abdullah EROGLU

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

Dominik ZELAZNY, Jaros law RUDY

On G-invexity-type nonlinear programming problems

Tadeusz ANTCZAK, Manuel Arana JİMENEZ