MOEA/D com Busca Local para o Flow Shop Multiobjetivo

• Geovani Antunes UTFPR
• Sandra Venske UNICENTRO
• Carolina Almeida State University in the Midwest of Paraná
• Myriam Delgado UTFPR
• Ricardo Lüders UTFPR

DOI: https://doi.org/10.5753/eniac.2019.9332

Resumo

Este artigo aborda o Flow Shop de Permutação, um problema de sequenciamento presente em muitos mecanismos de gerenciamento de processos de produção industrial. A abordagem multiobjetivo considerada neste trabalho envolve a minimização do tempo máximo para completar um trabalho (makespan) e do tempo total de atraso (total tardiness). Para isso é utilizada uma plataforma multiobjetivo denominada MOEA/D-DRA (do inglês Multi-objective Evolutionary Algorithm based on Decomposition with Dynamic Resource Allocation). O foco do trabalho reside na utilização de um mecanismo muito conhecido por seus bons resultados nas versões mono-objetivo do problema. Este mecanismo, denominado NEH, é adaptado para ser utilizado na busca local incluída no MOEA/D-DRA, aplicado na solução de 11 instâncias do Flow Shop de permutação com tamanhos variando de 20 a 200 tarefas e 5 a 20 máquinas. A abordagem proposta é comparada com o MOEA/D-DRA utilizando NEH apenas na inicialização da população. Os resultados mostram que, em apenas 2 instâncias, a versão do MOEA/D-DRA sem busca local supera a abordagem proposta.

Referências

Baker, K. R. e Trietsh, D. (2009). Principles of Sequencing and Scheduling, volume 1. Wiley.

Basseur, M., Seynhaeve, F., e Talbi, E. (2002). Design of multi-objective evolutionary algorithms: application to the flow-shop scheduling problem. In Proceedings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No.02TH8600), volume 2, pages 1151–1156 vol.2.

Chiang, T.-C., Cheng, H.-C., e Fu, L.-C. (2009). Multiobjective permutation flow shop scheduling using a memetic algorithm with an NEH-based local search. In LNCS, volume 5754, pages 813–825.

Coello, C. A. C., Lamont, G. B., Van Veldhuizen, D. A., et al. (2007). Evolutionary algorithms for solving multi-objective problems, volume 5. Springer.

Conover, W. J. (1999). Practical Nonparametric Statistics. Wiley, 3 edition.

Fernandez-Viagas, V., Ruiz, R., e Framinan, J. M. (2017). A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation. European J. of Operational Research, 257(3):707–721.

Garey, M. R., Johnson, D. S., e Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2):117–129.

Goldbarg, M. C., F., G. E., e Luna, H. P. (2015). Otimização Combinatória etaheurı́sticas- Algoritmos e Aplicações, volume 1. Campus.

Li, K., Fialho, A., Kwong, S., e Zhang, Q. (2014). Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 18(1):114–130.

Li, X. e Li, M. (2015). Multiobjective local search algorithm-based decomposition for multiobjective permutation flow shop scheduling problem. IEEE Transactions on Engineering Management, 62:544–557.

Minella, G., Ruiz, R., e Ciavotta, M. (2011). Restarted iterated pareto greedy algorithm for multi-objective flowshop scheduling problems. Computers & Operations Research, 38(11):1521 – 1533.

Nawaz, M., Enscore Jr, E. E., e Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega - Elsevier, 11(1):91–95.

Taillard, E. (1993). Benchmarks for basic scheduling problems. european journal of operational research, 64(2):278–285.

Trivedi, A., Srinivasan, D., Sanyal, K., e Ghosh, A. (2017). A survey of multiobjective evolutionary algorithms based on decomposition. IEEE Transactions on Evolutionary Computation, 21(3):440–462.

Yan, J., Li, C., Wang, Z., Deng, L., e Sun, D. (2007). Diversity metrics in multi-objective optimization: Review and perspective. In 2007 IEEE International Conference on Integration Technology, pages 553–557.

Yenisey, M. M. e Yagmahan, B. (2014). Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends. Omega, 45:119–135.

Zeng, R.-Q., Basseur, M., e Hao, J.-K. (2013). Solving bi-objective flow shop problem with hybrid path relinking algorithm. Applied Soft Computing, 13(10):4118 – 4132.

Zhang, Q. e Li, H. (2007). Moea/d: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on evolutionary computation, 11(6):712–731.

Zhang, Q., Liu, W., e Li, H. (2009). The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances. In Evolutionary Computation, 2009. CEC’09. IEEE Congress on, pages 203–208. IEEE.

Zhe-jian Zhao, Xue-qing He, e Feng Liu (2017). An improved multi-objective memetic algorithm for bi-objective permutation flow shop scheduling. In 2017 International Conference on Service Systems and Service Management, pages 1–6.

Zhou, A., Qu, B.-Y., Li, H., Zhao, S.-Z., Suganthan, P. N., e Zhang, Q. (2011). Multiobjective evolutionary algorithms: A survey of the state of the art. Swarm and Evolutionary Computation, 1(1):32–49.