Browsing by Author "Vera Villegas, Antony Hector"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Revisión de la literatura acerca del FSSP permutacional con criterio de minimización del makespan.
    (Universidad Católica San Pablo, 2020) Vera Villegas, Antony Hector; Cárdenas Medina, José Manuel
    El problema de asignación de tareas en talleres de flujo consiste en definir el orden de “n” trabajos que deben ser procesados por “m” máquinas, el objetivo más común de este problema es la reducción del tiempo de ejecución de todos los trabajos, técnicamente llamado makespan, mediante la optimización en la asignación del orden de trabajos. Su estudio se viene realizando desde hace más de 60 años, habiendo autores que dedican la mayor parte de su vida a este problema, las propuestas se hacen cada vez más y con más frecuencia en las últimas décadas y el foco de estudio se centra en la proposición de nuevos y mejores métodos heurísticos para este problema, haciendo que se viva en un ambiente de competencia y de mejora continua. En el presente trabajo buscamos hacer una revisión de la literatura más relevante de este problema, mostrando en orden cronológico los principales aportes hasta llegar al estado del arte, con el fin de asentar las bases para futuras investigaciones; teniendo un especial enfoque crítico en el mejor algoritmo actual para determinar sus fortalezas y debilidades que serán usadas para estudiar y proponer de manera teórica una idea que sirva para una posterior propuesta de mejora a los métodos que forman el estado del arte. El cual, con el incremento exponencial de la tecnología y el “apetito insaciable” de las empresas por mejorar sus procesos, está sirviendo de base para la creación de nuevos modelos con rendimientos de alto nivel en muchas ramas de la ingeniería industrial.
  • Thumbnail Image
    Item
    The reversibility property in a job-insertion tiebreaker for the permutational flow shop scheduling problem
    (Universidad Católica San Pablo, 2024) Vera Villegas, Antony Hector; Benavides Rojas, Alexander Javier
    The best performing approximate methods proposed for the permutational flow shop scheduling problem with makespan minimization are the well known NEH constructive heuristic and the iterated greedy algorithm. Both methods are based on the successive insertion (or reinsertion) of jobs into a partial schedule, evaluating the makespan of the resulting schedule for all insertion positions, and selecting the insertion position that presents the shortest makespan. Frequently, there are many tied insertion positions that produce such shortest makespan. Thus, a tiebreaker must be used to discern a selection among the tied insertion positions. Many tiebreakers have been proposed in the literature for this case. These tiebreakers improve the results produced by approximate methods when embedded into them. In this paper we propose two new tiebreakers that use a weighted and an unweighted approximation of the idle time increment produced by inserting the job into each tied insertion position. They were designed considering the reversibility property of the PFSSP. Our computational experiments show that the proposed tiebreakers outperform tiebreakers from the literature when evaluated within the NEH heuristic and within the iterated greedy algorithm. The iterated greedy algorithms with the proposed tiebreakers embedded are the best approximate methods so far for the permutational flow shop scheduling problem.