{"id":93390,"date":"2018-03-11T10:12:43","date_gmt":"2018-03-11T10:12:43","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/common-due-date-setting-in-permutation-flowshops-analysis-of-problems-and-solution-procedures\/"},"modified":"2018-03-11T10:12:43","modified_gmt":"2018-03-11T10:12:43","slug":"common-due-date-setting-in-permutation-flowshops-analysis-of-problems-and-solution-procedures","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/produccion\/common-due-date-setting-in-permutation-flowshops-analysis-of-problems-and-solution-procedures\/","title":{"rendered":"Common due date setting in permutation flowshops: analysis of problems and solution procedures"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Paz P\u00e9rez Gonz\u00e1lez <\/strong><\/h2>\n<p>Determinaci\u00f3n de una fecha de entrega com\u00fan en flujo regular: an\u00e1lisis de problemas y procedimientos de resoluci\u00f3n la determinaci\u00f3n de fechas de entrega es un problema emergente dentro de la planificaci\u00f3n de la producci\u00f3n. Esta tesis doctoral aborda dicho problema dentro del marco de la secuenciaci\u00f3n de trabajos en el entorno de fabricaci\u00f3n particular de flujo regular. Las fechas de entrega tienen gran influencia en la calidad del servicio ofrecido al cliente, siendo un aspecto clave la determinaci\u00f3n de las fecha de entrega de los pedidos de forma adecuada para mantener la credibilidad de una empresa productiva. el escenario considerado en este trabajo implica la llegada de nuevos trabajos, teniendo en cuenta la capacidad del sistema, con el objetivo de proporcionar una fecha de entrega razonable tanto desde el punto de vista del cliente como desde el punto de vista del sistema, es decir, que la fecha de entrega no sea tard\u00eda, y a su vez se pueda cumplir. Llevar a cabo este objetivo no es trivial. Est\u00e1 relacionado con el mecanismo de aceptaci\u00f3n de pedidos, as\u00ed como con la forma de determinar las fechas de entrega. Un m\u00e9todo adecuado que permita la secuenciaci\u00f3n de los trabajos y la determinaci\u00f3n de las fechas de entrega de forma cooperativa puede proporcionar la secuencia ideal en la que los trabajos puedan terminar exactamente en las fechas de entrega asignadas, garantizando la satisfacci\u00f3n del cliente sin ning\u00fan riesgo. Una vez que las fechas de entrega son aceptadas por el cliente y consideradas en firme, es posible llevar a cabo un nuevo proceso de secuenciaci\u00f3n, teniendo en cuenta que el sistema de fabricaci\u00f3n es din\u00e1mico (implicando cambios y nuevas condiciones), y asumiendo objetivos relacionados con el cumplimiento de las fechas de entrega establecidas previamente. Este trabajo presenta un nuevo marco para la determinaci\u00f3n de las fechas de entrega, teniendo en cuenta el estado del sistema, y basado en la llegada de nuevos pedidos. As\u00ed, dado un conjunto de nuevos trabajos, pertenecientes a un pedido, llegan al sistema para ser procesados, mientras un conjunto de antiguos trabajos, pertenecientes a un pedido anterior, est\u00e1n secuenciados y tienen una fecha de entrega com\u00fan ya asignada. El objetivo es minimizar el tiempo de terminaci\u00f3n o makespan de los trabajos nuevos, proporcionando as\u00ed una fecha de entrega com\u00fan para estos ajustada. Dependiendo de la gesti\u00f3n sobre los trabajos antiguos, el problema tendr\u00e1 unas determinadas restricciones. problemas identificados en el contexto explicado anteriormente, se han identificado algunos problemas de secuenciaci\u00f3n, en este caso en un entorno de flujo regular de permutaci\u00f3n, dependiendo de la consideraci\u00f3n de los trabajos antiguos. Estos problemas son: el problema cl\u00e1sico de flujo regular de permutaci\u00f3n con objetivo makespan (p0). Este problema corresponde al caso en el que no hay trabajos antiguos, ya sea porque no hay pedidos anteriores, o porque se ha esperado a la finalizaci\u00f3n de su proceso. problema de flujo regular de permutaci\u00f3n con restricci\u00f3n de disponibilidad al inicio del horizonte de planificaci\u00f3n (p1). En este caso, los trabajos antiguos est\u00e1n secuenciados y no se puede variar dicha secuencia, se dice que est\u00e1n congelados. As\u00ed, el problema de secuenciaci\u00f3n de los trabajos nuevos tiene una restricci\u00f3n de disponibilidad de las m\u00e1quinas al inicio del horizonte de planificaci\u00f3n, ya que est\u00e1n ocupadas con los trabajos antiguos. problemas de resecuenciaci\u00f3n. En este caso la secuencia formada por los trabajos antiguos puede ser modificada, es decir, los trabajos son resecuenciados junto con los trabajos nuevos. Varios problemas han sido identificados:  problema de resecuenciaci\u00f3n restringido (p2). Este problema considera la fecha de entrega com\u00fan de los trabajos antiguos como l\u00edmite, no pudiendo ser incumplida. problema de resecuenciaci\u00f3n sin restricci\u00f3n (p3). Este problema considera que la fecha de entrega com\u00fan de los trabajos antiguos puede ser incumplida, con la correspondiente penalizaci\u00f3n en la funci\u00f3n objetivo. finalmente, el problema de resecuenciaci\u00f3n con ventana de entrega com\u00fan, que considera un intervalo dentro del cual pueden terminar los trabajos antiguos sin penalizaci\u00f3n.  problema cl\u00e1sico de flujo regular de permutaci\u00f3n p0 es el problema cl\u00e1sico de flujo regular de permutaci\u00f3n con objetivo makespan. Este conocido problema ha sido estudiado durante los \u00faltimos 50 a\u00f1os (gupta and stafford, 2006). P0 es resoluble de forma \u00f3ptima en tiempo polinomial para el caso de dos m\u00e1quinas mediante el algoritmo de johnson, o para el caso de tres m\u00e1quinas bajo determinadas condiciones (johnson, 1954). Adem\u00e1s, el problema es np-completo en el sentido fuerte para m\u00e1s de dos m\u00e1quinas (garey et al., 1976). Existe una amplia literatura estudiando este problema (ver por ejemplo nawaz et al., 1983; framinan et al., 2004; ruiz and st\u00ed\u00bctzle, 2007; framinan et al., 2003; ruiz and maroto, 2005; rajendran and ziegler, 2005 y tasgetiren et al., 2007), por lo que no es discutido en este trabajo. problema de flujo regular de permutaci\u00f3n con restricci\u00f3n de disponibilidad al inicio del horizonte de planificaci\u00f3n la literatura sobre secuenciaci\u00f3n suele considerar que las m\u00e1quinas est\u00e1n disponibles durante el horizonte de planificaci\u00f3n (aggoune and portmann, 2006). Sin embargo, hay un gran n\u00famero de situaciones reales donde las m\u00e1quinas no est\u00e1n completamente disponibles, tales como roturas de m\u00e1quinas (indisponibilidad estoc\u00e1stica) (allaoui et al., 2006) o por tareas de mantenimiento (indisponibilidad determinista) (ruiz et al., 2007). En este trabajo se ha revisado la literatura sobre problemas en flujo regular con restricciones de disponibilidad, contrastando que el problema aqu\u00ed considerado no ha sido estudiado previamente. as\u00ed, p1 es un problema de flujo regular de permutaci\u00f3n con restricci\u00f3n de disponibilidad en las m\u00e1quinas, considerando los instantes de disponibilidad de \u00e9stas a partir de los cuales los nuevos trabajos pueden ser secuenciados. El objetivo es la minimizaci\u00f3n de los trabajos nuevos teniendo en cuenta los instantes de disponibilidad, determinados por los tiempos de terminaci\u00f3n en cada m\u00e1quina de los trabajos antiguos. El problema ha sido analizado en detalle. Se ha incluido un par\u00e1metro relacionado con la congesti\u00f3n del sistema, resultando que cuanto mayor es la congesti\u00f3n, m\u00e1s f\u00e1cil es encontrar buenas soluciones para el problema, siendo m\u00e1s f\u00e1cil que en el caso en el que no hay trabajos previos secuenciados, es decir, p1 es m\u00e1s sencillo que p0. Adem\u00e1s, se han tenido en cuenta diferentes formas de generar los tiempos de proceso, siendo m\u00e1s f\u00e1cil el problema para el caso en el que existe correlaci\u00f3n entre \u00e9stos (caso m\u00e1s realista que cuando dichos tiempos son generados de forma aleatoria). As\u00ed, considerando este estudio, se puede concluir que para situaciones m\u00e1s reales de los entornos, la secuenciaci\u00f3n desde el punto de vista considerado se vuelve m\u00e1s sencilla que en el caso cl\u00e1sico (en el que no se asume la indisponibilidad de las m\u00e1quinas). La simplicidad del problema p1 sugiere que el uso de heur\u00edsticas r\u00e1pidas puede proporcionar buenas soluciones en tiempo casi real. Por lo tanto, se han dise\u00f1ado un conjunto de heur\u00edsticas r\u00e1pidas llamadas heur\u00edsticas de secuencia inicial basadas en el per\u00edodo definido por la indisponibilidad de las m\u00e1quinas. Se han desarrollado tres tipos de algoritmos: ordenaci\u00f3n simple, ajuste simple, y ajuste m\u00faltiple. Todos han sido combinados con diferentes criterios e indicadores para ordenar los trabajos. Se ha desarrollado un an\u00e1lisis de los resultados proporcionados por las heur\u00edsticas al resolver un conjunto de problemas, revelando que los mejores resultados son los proporcionados por las heur\u00edsticas de ajuste simple y ajuste m\u00faltiple (sin diferencias estad\u00edstica entre ellos), independientemente del indicador. Adem\u00e1s, se han desarrollado un conjunto de heur\u00edsticas constructivas, basadas en la aplicaci\u00f3n de la aneht (adaptaci\u00f3n de la heur\u00edstica neht desarrollada por nawaz et al. (1983) para p0). Las heur\u00edsticas constructivas toman como secuencia inicial las soluciones proporcionadas por las heur\u00edsticas de secuencia inicial. Los resultados obtenidos son mejores que los de las heur\u00edsticas de secuencia inicial, independientemente de la secuencia inicial seleccionada. Sin embargo, las heur\u00edsticas constructivas no son tan r\u00e1pidas como las heur\u00edsticas de secuencia inicial.  problema de resecuenciaci\u00f3n restringido.  la resecuenciaci\u00f3n es la principal consecuencia de la incertidumbre en el \u00e1rea de la secuenciaci\u00f3n, cuando alg\u00fan imprevisto hace imposible seguir la secuencia original (wu et al., 1993). La resecuenciaci\u00f3n implica el ajuste del plan ya realizado (hall and potts, 2004; vieira et al., 2003), modificando la secuencia existente, o creando una nueva. entre los problemas de resecuenciaci\u00f3n identificados previamente p2, p3 y p4, este trabajo se centra en p2. Es un problema de flujo regular de permutaci\u00f3n con el objetivo de minimizar el makespan de los trabajos nuevos sujeto a la restricci\u00f3n que indica que la m\u00e1xima tardanza de los trabajos antiguos tiene que ser cero, ya que la fecha de entrega com\u00fan de \u00e9stos no puede ser incumplida. Para analizar el problema, se ha considerado un par\u00e1metro que controla la generaci\u00f3n de la fecha de entrega com\u00fan de los trabajos antiguos con respecto al tiempo de terminaci\u00f3n de dichos trabajos, es decir la holgura de la fecha de entrega. El problema es mucho m\u00e1s dif\u00edcil que p0 y p1, salvo el caso en el que la holgura es muy peque\u00f1a que es m\u00e1s f\u00e1cil que p0. Aunque p2 en general es m\u00e1s dif\u00edcil, proporciona mejores valores del makespan de los trabajos nuevos sin violar la fecha de entrega de los antiguos. El ajuste del par\u00e1metro nos ayuda a proporcionar fechas de entrega satisfactorias al cliente, es decir, que no sean demasiado holgadas, pero que faciliten la resecuenciaci\u00f3n para obtener buenos tiempos de terminaci\u00f3n de los trabajos que llegan con los nuevos pedidos. la dificultad del problema p2 implica la necesidad de aplicar sofisticados m\u00e9todos para su resoluci\u00f3n. Varias metaheur\u00edsticas han sido aplicadas al problema. Dos de ellas han sido extra\u00eddas de la revisi\u00f3n de problemas relacionados en la literatura, una basada en algoritmos gen\u00e9ticos desarrollada por ruiz and allahverdi (2009), y otra de b\u00fasqueda voraz iterativa (iterated greedy) desarrollada por ruiz and st\u00ed\u00bctzle (2007). Finalmente se ha propuesto una nueva metaheur\u00edstica basada en b\u00fasqueda del entorno variable (variable neighbourhood search), llamada refreshing vns. Esta heur\u00edstica considera la b\u00fasqueda en entornos generados por diferentes estructuras de vecinos. Para adaptarla a p2, que es un problema con restricciones que implica soluciones factibles  e infactibles, se han considerado diferentes estructuras de vecindad para los dos tipos de soluciones, de forma que el m\u00e9todo explore en entornos de soluciones buenas, con respecto a la funci\u00f3n objetivo, independientemente de su factibilidad. Se han implementado tres tipos de b\u00fasqueda local, una general, y dos que son espec\u00edficas al tipo de factibilidad de la soluci\u00f3n actual, una que intensifica la b\u00fasqueda de soluciones factibles, y otra que trata de reparar soluciones infactibles. Adem\u00e1s, una funci\u00f3n de escape aleatorio ayuda a salir de \u00f3ptimos locales. Los resultados obtenidos de la comparaci\u00f3n de las tres metaheur\u00edsticas revelan que el algoritmo gen\u00e9tico es muy competitivo, pero la vns propuesta proporciona mejores resultados. problemas de resecuenciaci\u00f3n sin restricci\u00f3n y con ventana de entrega los otros dos problemas de resecuenciaci\u00f3n identificados, adem\u00e1s del presentado anteriormente, p3 y p4, no han sido abordados en este trabajo, pero son una l\u00ednea de investigaci\u00f3n inmediata, con el objetivo de cerrar el c\u00edrculo abierto con los problemas ya estudiados en esta tesis. ambos son problemas de resecuenciaci\u00f3n en flujo regular con objetivo la minimizaci\u00f3n del makespan de los trabajos nuevos. P3 considera la fecha de entrega com\u00fan de los trabajos antiguos puede ser incumplida, con la correspondiente penalizaci\u00f3n en la funci\u00f3n objetivo. Por lo tanto es un problema de resecuenciaci\u00f3n sin restricci\u00f3n, en el que la funci\u00f3n objetivo puede ser una funci\u00f3n lineal que considere el makespan de los trabajos nuevos y la tardanza m\u00e1xima de los trabajos antiguos. P4 es un problema de resecuenciaci\u00f3n con ventana de entrega com\u00fan, ya que considera un intervalo dentro del cual pueden terminar los trabajos antiguos sin penalizaci\u00f3n, por lo que dada una fecha de entrega com\u00fan y un intervalo en el que los trabajos deben de concluir.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Common due date setting in permutation flowshops: analysis of problems and solution procedures<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Common due date setting in permutation flowshops: analysis of problems and solution procedures <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Paz P\u00e9rez Gonz\u00e1lez <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Sevilla<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 20\/05\/2009<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Direcci\u00f3n y tribunal<\/h3>\n<ul>\n<li><strong>Director de la tesis<\/strong>\n<ul>\n<li>Jos\u00e9 Manuel Frami\u00f1an Torres<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: rafael Ruiz usano <\/li>\n<li>rainer Leisten (vocal)<\/li>\n<li>abdelhakim Artiba lismma (vocal)<\/li>\n<li>adolfo Crespo m\u00e1rquez (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Paz P\u00e9rez Gonz\u00e1lez Determinaci\u00f3n de una fecha de entrega com\u00fan en flujo regular: an\u00e1lisis de problemas y [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[6525,16555,706,10715],"tags":[192896,38248,122793,192895,11307,50969],"class_list":["post-93390","post","type-post","status-publish","format-standard","hentry","category-organizacion-de-la-produccion","category-planificacion","category-produccion","category-sevilla","tag-abdelhakim-artiba-lismma","tag-adolfo-crespo-marquez","tag-jose-manuel-framinan-torres","tag-paz-perez-gonzalez","tag-rafael-ruiz-usano","tag-rainer-leisten"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/93390","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=93390"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/93390\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=93390"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=93390"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=93390"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}