Algoritmo Genético e Busca Local para o problema Just-in-Time Job-Shop Scheduling

• Rodolfo P. Araujo UFV
• André G. dos Santos UFV
• José E. C. Arroyo UFV

Resumo

Este artigo descreve uma combinação bem sucedida de algoritmo genético e busca local para o problema de just-in-time job-shop scheduling com penalidades por atraso e adiantamento. As operações de cada tarefa têm uma ordem específica de processamento nas máquinas e cada operação tem um tempo de processamento e penalidades por atraso e adiantamento que são pagos se a tarefa é finalizada depois ou antes da data determinada. Soluções exatas são difíceis até para pequenas instâncias, mas a combinação do algoritmo genético com uma proposta de busca local se mostrou eficiente. A qualidade das soluções é avaliada e comparada com um conjunto de instâncias da literatura com até 20 tarefas e 10 máquinas. O método proposto melhorou o valor da solução para várias instâncias da literatura.

Referências

Baker, K. R. e Scudder, G. D. (1990) “Sequencing with earliness and tardiness penalties: A review”, In Operations Research, vol. 38(1), pp.22–36.

Baptiste, P., Flamini M. e Sourd F. (2008a) “Lagrangian bounds for just-in-time job-shop scheduling”, In Computers & Operations Research, vol. 35, pp.906–915.

Baptiste, P., Flamini, M. e Sourd, F. (2008b) “Job-shop scheduling with earliness-tardiness penalties”, [link], Abril

Beck, J. C. e Refalo, P. (2003) “A hybrid approach to scheduling with earliness and tardiness costs”, In Annals of Operations Research, vol. 118, pp.49–71.

Du, J. e Leung, Y. T. (1990) “Minimizing total tardiness on one machine is NP-hard”, In Mathematics of Operations Research, vol. 15, pp.483–495.

Gao, J., Sun, L. e Gen M. (2007) “A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems”, In Computers & Operations Research, vol. 35(9), pp.2892–2907.

Gonçalves, J. F., Mendes, J. J. M. e Resende, M. G. C. (2005) “A hybrid genetic algorithm for the job shop scheduling problem”, In European Journal of Operational Research, vol. 167, pp.77–95.

Jain, A. S. e Meeran, S. (1999) “A state-of-the-art review of job-shop scheduling techniques”, In European Journal of Operational Research, vol. 113, pp.390–434.

Kelbel, J. e Hanzálek. Z. (2007) “Constraint Programming Search Procedure for Earliness/Tardiness Job Shop Scheduling Problem”, In Proc. of the 26th Workshop of the UK Planning and Scheduling Special Interest Group, pp. 67–70.

Mattfeld, D. C. e Bierwirth, C. (2004) “An efficient genetic algorithm for job shop scheduling with tardiness objectives”, In European Journal of Operational Research, vol. 155, pp.616–630.

Sourd, F. e Kedad-Sidhoum, S. (2003) “The one machine problem with earliness and tardiness penalties”, In Journal of Scheduling, vol. 6, pp.533–49.

Zhang, C., Rao, Y. e Li, P. (2008) “An effective hybrid genetic algorithm for the job shop scheduling problem”, In The International Journal of Advanced Manufacturing Technology, vol. 39, pp.965–974.