Estudio sobre operaciones críticas en las tareas de programación en sistemas productivos de tipo job shop

Autor: Bordignon, Jonathan Farias, Santos, Luis Carlos Caparroz dos, Silva, Marilda Fátima de Souza da, Pereira, Fabio Henrique
Jazyk: portugalština
Rok vydání: 2022
Předmět:
Zdroj: Research, Society and Development; Vol. 11 No. 5; e17111528035
Research, Society and Development; Vol. 11 Núm. 5; e17111528035
Research, Society and Development; v. 11 n. 5; e17111528035
Research, Society and Development
Universidade Federal de Itajubá (UNIFEI)
instacron:UNIFEI
ISSN: 2525-3409
Popis: This work studies the classic problem of job shop scheduling for makespan minimizing. Due to the combinatorial nature and computational complexity of this problem, the use of metaheuristic techniques combined with local search methods is quite widespread as it allows satisfactory results in a viable computational time. In general, local search methods are based on empirical permutations of the operations that make up the critical path of a solution, the so-called critical operations, which demand the calculation of the critical path for each of the solutions generated in the search process. In addition to increasing the computational cost of local search, this approach promotes permutations of operations that do not result in any improvement in the solution. This work investigates the distribution of critical operations on the machines and the correlation between this distribution and problem characteristics. The objective is to estimate machines that concentrate critical operations and identify characteristics that contribute to the definition of local search methods that do not depend on the calculation of the critical path for each solution. Computational experiments with usual instances from literature show that there is a concentration of critical operations in some machines and, in some cases, a positive correlation between this concentration and the average processing times of the operations, which can provide subsidies for creating more efficient local search methods. Este trabajo estudia el problema de programación de la producción clásica en la tienda de empleo para minimizar a Makespan. Debido a la naturaleza combinativa y la complejidad computacional de este problema, el uso de técnicas metaheurísticas aliadas a los métodos de búsqueda locales está generalizada al permitir los resultados satisfactorios en un tiempo computacional viable. En general, los métodos de búsqueda locales se basan en permutaciones empíricas de operaciones que conforman la ruta crítica de una solución, llama a operaciones críticas, que exige el cálculo del camino crítico para cada una de las soluciones generadas en el proceso de búsqueda. Además de elevar el costo computacional de la búsqueda local, dicho enfoque promueve permutaciones de operaciones que no resultan en ninguna mejora en la solución. Este trabajo investiga la distribución de operaciones críticas sobre máquinas y correlación entre esta distribución y características estadísticas de los problemas. El objetivo es estimar las máquinas que concentren las operaciones críticas e identifican las características que pueden contribuir a la definición de métodos de búsqueda locales que no dependen del cálculo del camino crítico a cada solución. Los experimentos computacionales con instancias habituales de literatura muestran que hay una concentración de operaciones críticas en algunas máquinas y, en algunos casos, una correlación positiva significativa entre esta concentración y los tiempos de procesamiento de operaciones promedio, lo que puede proporcionar subsidios para crear métodos de búsqueda computacionalmente más eficientes. Este trabalho estuda o problema clássico de agendamento da produção em job shop para minimização do makespan. Devido à natureza combinatória e complexidade computacional desse problema, o uso de técnicas metaheurísticas aliadas a métodos de busca local é bastante difundido por possibilitar resultados satisfatórios em um tempo computacional viável. Em geral, os métodos de busca local se baseiam em permutações empíricas das operações que compõe o caminho crítico de uma solução, as chamadas operações críticas, o que demanda o cálculo do caminho crítico para cada uma das soluções geradas no processo de busca. Além de elevar o custo computacional da busca local, tal abordagem promove permutações de operações que não resultam em qualquer melhoria da solução. Este trabalho investiga a distribuição das operações críticas nas máquinas e a correlação entre essa distribuição e características estatísticas dos problemas. O objetivo é estimar máquinas que concentram operações críticas e identificar características que possam contribuir para definição de métodos de busca local que não dependam do cálculo do caminho crítico a cada solução. Experimentos computacionais com instâncias usuais da literatura mostram que há uma concentração de operações críticas em algumas máquinas e, em alguns casos, uma correlação positiva significativa entre essa concentração e os tempos médios de processamento das operações, o que pode fornecer subsídios para criação de métodos de busca local computacionalmente mais eficientes.
Databáze: OpenAIRE
Externí odkaz: