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 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 multicriteria 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.
[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 forjob 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., Optimizing 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 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).
[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).