{"id":110227,"date":"2018-03-11T10:36:09","date_gmt":"2018-03-11T10:36:09","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/soluciones-metaheura%c2%adsticas-al-job-shop-scheduling-problem-with-sequence-dependent-setup-times\/"},"modified":"2018-03-11T10:36:09","modified_gmt":"2018-03-11T10:36:09","slug":"soluciones-metaheura%c2%adsticas-al-job-shop-scheduling-problem-with-sequence-dependent-setup-times","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/inteligencia-artificial\/soluciones-metaheura%c2%adsticas-al-job-shop-scheduling-problem-with-sequence-dependent-setup-times\/","title":{"rendered":"Soluciones metaheur\u00edsticas al \u00abjob-shop scheduling problem with sequence-dependent setup times\u00bb"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Miguel \u00e1ngel Gonz\u00e1lez Fern\u00e1ndez <\/strong><\/h2>\n<p>Los problemas de scheduling requieren organizar en el tiempo la ejecuci\u00f3n de tareas que comparten un conjunto finito de recursos, y que est\u00e1n sujetas a un conjunto de restricciones impuestas por diversos factores, como por ejemplo las caracter\u00edsticas f\u00edsicas del entorno, relaciones temporales o la normativa laboral. Este tipo de problemas aparecen con frecuencia en la vida real en numerosos entornos productivos y de servicios. El problema consiste en optimizar uno o varios criterios que se representan mediante funciones objetivo y que suelen estar relacionados con el coste o el tiempo total de ejecuci\u00f3n. Algunos ejemplos de problemas de scheduling son los siguientes:  fabricaci\u00f3n de obleas para circuitos semiconductores, donde cada oblea precisa de una serie de tareas como limpieza, oxidaci\u00f3n, metalizaci\u00f3n, etc. Los objetivos pueden ser maximizar la utilizaci\u00f3n de algunas m\u00e1quinas que son cuello de botella o minimizar el tiempo de ejecuci\u00f3n.  planificar el aterrizaje de un conjunto de aviones sujetos a restricciones temporales que dependen de las caracter\u00edsticas de los aviones. Los objetivos pueden ser minimizar la penalizaci\u00f3n por desv\u00edo con respecto al horario planeado para los aviones o maximizar las condiciones de seguridad.  enrutamiento de paquetes de datos a trav\u00e9s de l\u00edneas de comunicaci\u00f3n, donde se trata de maximizar el uso de la red y de minimizar los tiempos de llegada de los mensajes.  todos estos problemas son de naturaleza combinatoria, es decir que hay que elegir una entre un conjunto exponencialmente grande de combinaciones posibles, y por lo tanto los problemas de scheduling precisan de algoritmos de b\u00fasqueda inteligentes para encontrar soluciones aceptables en un tiempo razonable. En la literatura se pueden encontrar aproximaciones a los problemas de scheduling basadas en todas las metaheur\u00edsticas conocidas.  en esta tesis nos centramos en el problema job shop scheduling with sequence dependent setup times. Este problema es una generalizaci\u00f3n del problema job shop cl\u00e1sico que tiene m\u00e1s inter\u00e9s en muchas aplicaciones reales. Adem\u00e1s, es un problema mucho menos estudiado y su resoluci\u00f3n es m\u00e1s compleja, ya que los tiempos de setup cambian la naturaleza del problema y muchas de las propiedades formales demostradas para el job shop, dejan de cumplirse en presencia de tiempos de setup. Por este motivo, la adaptaci\u00f3n de las t\u00e9cnicas utilizadas para resolver el job shop muchas veces no ser\u00e1 trivial.  como t\u00e9cnicas de b\u00fasqueda utilizaremos los algoritmos gen\u00e9ticos y la b\u00fasqueda local. Es bien sabido que estos m\u00e9todos no necesariamente producen la soluci\u00f3n \u00f3ptima del problema, pero hay que tener en cuenta que cuando el espacio de b\u00fasqueda del problema es enorme, como ocurre en este caso, los m\u00e9todos exactos de resoluci\u00f3n suelen ser demasiado costosos, ya sea en tiempo de ejecuci\u00f3n o en recursos computacionales. El objetivo, por lo tanto, ser\u00e1 dise\u00f1ar estrategias eficaces para obtener buenas soluciones en un tiempo razonable. Para ello se deber\u00e1n estudiar aspectos como heur\u00edsticos, estructuras de vecindad, propiedades del camino cr\u00edtico, algoritmos de estimaci\u00f3n de vecinos, grafos disyuntivos, constructores de planificaciones, y en general encontrar la mejor configuraci\u00f3n para los m\u00e9todos utilizados.  en esta tesis estudiaremos diversas funciones objetivo. La funci\u00f3n objetivo a la que los investigadores han prestado mayor atenci\u00f3n es sin duda el makespan, o tiempo de finalizaci\u00f3n de la \u00faltima tarea. Pero otras funciones objetivo pueden tener mayor inter\u00e9s en problemas reales, en donde es posible que cada uno de los trabajos tenga un tiempo deseable de fin diferente, e incluso que algunos trabajos tengan una mayor prioridad que otros. Por este motivo, adem\u00e1s de la minimizaci\u00f3n del makespan trataremos la minimizaci\u00f3n de otras tres funciones objetivo: maximum lateness, weighted tardiness y total flow time.  las aportaciones principales de esta tesis ser\u00e1n el estudio de las diferencias entre las propiedades del job shop cl\u00e1sico y el job shop con tiempos de setup, la definici\u00f3n de un modelo de grafo disyuntivo para cada funci\u00f3n objetivo estudiada, el dise\u00f1o de una serie de estructuras de vecindad con sus respectivas condiciones de factibilidad y de no mejora, algoritmos de estimaci\u00f3n de vecinos para diferentes funciones objetivo y otras consideraciones sobre c\u00f3mo realizar una b\u00fasqueda local de la forma lo m\u00e1s eficiente posible, y por \u00faltimo, unos resultados experimentales que mostrar\u00e1n que la correcta combinaci\u00f3n de los m\u00e9todos propuestos es capaz de mejorar en muchos casos a los mejores resultados conocidos en la literatura.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Soluciones metaheur\u00edsticas al \u00abjob-shop scheduling problem with sequence-dependent setup times\u00bb<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Soluciones metaheur\u00edsticas al \u00abjob-shop scheduling problem with sequence-dependent setup times\u00bb <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Miguel \u00e1ngel Gonz\u00e1lez Fern\u00e1ndez <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Oviedo<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 14\/07\/2011<\/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>Mar\u00eda Camino Rodr\u00edguez Vela<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: Antonio Bahamonde rionda <\/li>\n<li>federico Barber sanchis (vocal)<\/li>\n<li>lorenzo Mandow andaluz (vocal)<\/li>\n<li>oscar Cord\u00f3n Garc\u00eda (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Miguel \u00e1ngel Gonz\u00e1lez Fern\u00e1ndez Los problemas de scheduling requieren organizar en el tiempo la ejecuci\u00f3n de tareas [&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":[2528,6264,8846],"tags":[10527,19162,102763,203236,220151,40068],"class_list":["post-110227","post","type-post","status-publish","format-standard","hentry","category-inteligencia-artificial","category-investigacion-operativa","category-oviedo","tag-antonio-bahamonde-rionda","tag-federico-barber-sanchis","tag-lorenzo-mandow-andaluz","tag-maria-camino-rodriguez-vela","tag-miguel-angel-gonzalez-fernandez","tag-oscar-cordon-garcia"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/110227","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=110227"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/110227\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=110227"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=110227"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=110227"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}