Algoritmo Híbrido para o Problema Flow Shop de Permutação Multiobjetivo
Resumo
Os algoritmos evolucionários são uma abordagem não determinística para resolver problemas de otimização que não podem ser resolvidos em tempo polinomial, como problemas clássicos NP-Hard.
O Flow Shop de Permutação (FSP) é um problema de otimização combinatória do ambiente de produção, em que tarefas devem ser processadas por máquinas, mantendo o mesmo fluxo de processamento. Neste trabalho a abordagem multiobjetivo foi utilizada para o FSP, tendo como objetivos de minimização o makespan e o total flowtime. Dois algoritmos híbridos compostos por NSGA-II com Busca Tabu foram considerados na abordagem e aplicados em 11 instâncias do FSP com diferentes dimensões. Uma análise foi feita sobre o uso de regras de proibição na Busca Tabu e sua restritividade. Os resultados foram analisados utilizando as métricas de qualidade IGD e Função de Conquista Empírica, comparando-os com o NSGA-II canônico.
Referências
Arroyo, J. E. and Pereira, A. (2011). A grasp heuristic for the multi-objective permutation flowshop scheduling problem. The International Journal of Advanced Manufacturing Technology, 55:741–753.
Arroyo, J. E. C. and Armentano, V. A. (2005). Genetic local search for multiobjective flowshop scheduling problems. European Journal of Operational Research, 167(3):717 – 738. Multicriteria Scheduling.
Blot, A., Pernet, A., Jourdan, L., Kessaci-Marmion, M.-É., and Hoos, H. H. (2017). Autmatically configuring multi-objective local search using multi-objective optimisation. In Trautmann, H., Rudolph, G., Klamroth, K., Schütze, O., Wiecek, M., Jin, Y., and Grimme, C., editors, Evolutionary Multi-Criterion Optimization, pages 61–76, Cham. Springer International Publishing.
Coello, C. A. C., Lamont, G. B., Van Veldhuizen, D. A., et al. (2007). Evolutionary algorithms for solving multi-objective problems, volume 5. Springer.
Conway, R. W., Miller, L. W., and Maxwell, W. L. (2003). Theory of scheduling. Dover.
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE transactions on evolutionary computation, 6(2):182–197.
Durillo, J. J. and Nebro, A. J. (2011). jmetal: A java framework for multi-objective optimization. Advances in Engineering Software, 42(10):760–771.
Engelbrecht, A. P. (2007). Computational intelligence: an introduction. John Wiley & Sons.
Gaspar-Cunha, A., Takahashi, R., and Antunes, C. H. (2012). Manual de computação evolutiva e metaheurı́stica. Imprensa da Universidade de Coimbra/Coimbra University Press.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5):533 – 549. Applications of Integer Programming.
Ishibuchi, H., Yoshida, T., and Murata, T. (2003). Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation, 7(2):204–223.
Taillard, E. (1991). Robust taboo search for the quadratic assignment problem. Parallel Computing, 17(4):443 – 455.
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278–285.
Varadharajan, T. and Rajendran, C. (2005). A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs. European Journal of Operational Research, 167(3):772–795.
Zitzler, E., Knowles, J., and Thiele, L. (2008). Quality assessment of pareto set approximations. In Multiobjective Optimization: Interactive and Evolutionary Approaches, volume 5252 of Lecture Notes in Computer Science, pages 373–404. Springer Berlin Heidelberg.
