{"id":97319,"date":"2018-03-11T10:17:50","date_gmt":"2018-03-11T10:17:50","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/mejora-de-algoritmos-de-busqueda-heura%c2%adstica-mediante-poda-por-dominancia-aplicacion-a-problemas-de-scheduling\/"},"modified":"2018-03-11T10:17:50","modified_gmt":"2018-03-11T10:17:50","slug":"mejora-de-algoritmos-de-busqueda-heura%c2%adstica-mediante-poda-por-dominancia-aplicacion-a-problemas-de-scheduling","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/inteligencia-artificial\/mejora-de-algoritmos-de-busqueda-heura%c2%adstica-mediante-poda-por-dominancia-aplicacion-a-problemas-de-scheduling\/","title":{"rendered":"Mejora de algoritmos de b\u00fasqueda heur\u00edstica mediante poda por dominancia. aplicaci\u00f3n a problemas de scheduling"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Mar\u00eda Rita Sierra S\u00e1nchez <\/strong><\/h2>\n<p>Los problemas de scheduling aparecen con profusi\u00f3n en la vida real en numerosos entornos productivos y de servicios. Se trata de problemas que requieren organizar en el tiempo la ejecuci\u00f3n de tareas que compiten por el uso de un conjunto finito de recursos y que est\u00e1n sujetas a un conjunto de restricciones impuestas por factores como las caracter\u00edsticas f\u00edsicas del entorno, relaciones temporales o la normativa laboral. Adem\u00e1s se trata de optimizar uno o varios criterios que se representan mediante funciones objetivo y que est\u00e1n relacionados normalmente con el coste, el beneficio o el tiempo de ejecuci\u00f3n.  algunos ejemplos de problemas de esta naturaleza 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. El objetivo puede 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 tiempo preferente de los aviones o maximizar las condiciones de seguridad. -planificar las rutas de flotas de autobuses, donde se trata de optimizar la ocupaci\u00f3n de los veh\u00edculos y de ajustar los turnos de los conductores de acuerdo con la normativa laboral. -enrutamiento de paquetes de datos a trav\u00e9s 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.  dado que estos problemas son de naturaleza combinatoria, es decir que hay que elegir una entre un conjunto exponencialmente grande de combinaciones posibles, los problemas de scheduling precisan de algoritmos de b\u00fasqueda inteligentes para encontrar soluciones aceptables en un tiempo razonable. As\u00ed, en la literatura se pueden encontrar aproximaciones a los problemas de scheduling basadas en pr\u00e1cticamente todas las metaheur\u00edsticas conocidas y en particular en los algoritmos de b\u00fasqueda heur\u00edstica propios de \u00e1reas como la investigaci\u00f3n operativa y la inteligencia artificial. en esta tesis nos centramos en el problema job shop scheduling y en la t\u00e9cnica de b\u00fasqueda heur\u00edstica en espacios de estados. Nuestro objetivo es dise\u00f1ar estrategias que resulten eficaces y eficientes para diferentes funciones objetivo, tanto para encontrar soluciones exactas, cuando el tama\u00f1o del problema lo permita, como para obtener soluciones aproximadas para instancias mayores. 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. Las propiedades de esta versi\u00f3n del problema son muy bien conocidas y han permitido desarrollar m\u00e9todos exactos y aproximados muy eficientes que se basan en el concepto de camino cr\u00edtico. El inconveniente de estos m\u00e9todos es que no se generalizan de forma eficiente para otras funciones objetivo como el tiempo de flujo total o el tardiness.  la aportaci\u00f3n principal de esta tesis es la formalizaci\u00f3n de un m\u00e9todo de poda basado en relaciones de dominancia entre los estados del espacio de b\u00fasqueda que se puede aplicar en principio a todas las funciones objetivo convencionales. Aunque el m\u00e9todo no resulta competitivo con los m\u00e9todos basados en el camino cr\u00edtico cuando se trata de minimizar el makespan, s\u00ed lo es con los m\u00e9todos que no est\u00e1n basados en el camino cr\u00edtico y que son generalizables a otras funciones objetivo. Para funciones objetivo como el tiempo de flujo total, los resultados experimentales que hemos realizado sobre bancos de ejemplos est\u00e1ndar demuestran que el m\u00e9todo es competitivo con otros m\u00e9todos del estado del arte tanto para obtener soluciones \u00f3ptimas como sub-\u00f3ptimas.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Mejora de algoritmos de b\u00fasqueda heur\u00edstica mediante poda por dominancia. aplicaci\u00f3n a problemas de scheduling<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Mejora de algoritmos de b\u00fasqueda heur\u00edstica mediante poda por dominancia. aplicaci\u00f3n a problemas de scheduling <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Mar\u00eda Rita Sierra S\u00e1nchez <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Oviedo<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 20\/11\/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 Ramiro Varela Arias<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: federico Barber sanchis <\/li>\n<li>Miguel \u00e1ngel Salido gregorio (vocal)<\/li>\n<li>richard Jos\u00e9 Duro fernandez (vocal)<\/li>\n<li>Francisco Javier Larrosa bondia (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Mar\u00eda Rita Sierra S\u00e1nchez Los problemas de scheduling aparecen con profusi\u00f3n en la vida real en numerosos [&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,8846],"tags":[19162,97219,130587,199485,59420,65452],"class_list":["post-97319","post","type-post","status-publish","format-standard","hentry","category-inteligencia-artificial","category-oviedo","tag-federico-barber-sanchis","tag-francisco-javier-larrosa-bondia","tag-jose-ramiro-varela-arias","tag-maria-rita-sierra-sanchez","tag-miguel-angel-salido-gregorio","tag-richard-jose-duro-fernandez"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/97319","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=97319"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/97319\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=97319"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=97319"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=97319"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}