Com as transformações advindas da 4º revolução industrial muitas empresas têm utilizado sistemas de manufatura flexíveis (FMS - flexible manufacturing system) visando reunir eficiência em grande escala nos sistemas de produção automatizados com flexibilidade dos processos manuais. Com a crescente utilização de tecnologias de automação assistida e robôs móveis autônomos (AMR - Autonomous Mobile Robot), ou por veículos guiados automatizados (AGV - Automated Guided Vehicle), surge a necessidade de utilizar métodos de otimização para uma melhor utilização dos AMRs, uma vez que se trata de recursos de alto investimento. Uma programação eficiente (scheduling - na literatura especializada) deverá determinar onde (em quais máquinas), por quem (quais AMRs) e quando as tarefas serão executadas em uma linha de produção. Neste contexto, este trabalho considera o problema de programação de tarefas (alimentação de peças em máquinas de uma linha de produção em um ambiente de manufatura flexível), de forma que as máquinas não interrompam o funcionamento devido à falta de peças, com o objetivo minimizar o tempo total da realização das tarefas pelos robôs. Apresenta-se um modelo de programação linear inteira, o qual é classificado como NP-Hard e propõe-se um algoritmo meta-heurístico baseado em buscas sistemáticas de descidas em diversas estruturas de vizinhanças definidas. O método de solução proposto leva em consideração as características e restrições operacionais das máquinas, do robô e define uma janela de tempo restrita para a realização das tarefas. Os resultados obtidos foram satisfatórios para os dados estudados ao se comparar com os resultados de outros métodos disponíveis na literatura.