Solving multi-objective job shop problem using nature-based algorithms: new Pareto approximation features
DOI:
https://doi.org/10.11121/ijocta.01.2015.00232Keywords:
Multi-objective optimization, job shop scheduling, multi-criteria decision analysis, nature inspiredAbstract
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.Downloads
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).
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).
Downloads
Published
How to Cite
Issue
Section
License
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
