{"id":106304,"date":"2018-03-11T10:30:14","date_gmt":"2018-03-11T10:30:14","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/nuevos-algoritmos-para-el-problema-de-secuenciacion-en-maquinas-paralelas-no-relacionadas-y-generalizaciones\/"},"modified":"2018-03-11T10:30:14","modified_gmt":"2018-03-11T10:30:14","slug":"nuevos-algoritmos-para-el-problema-de-secuenciacion-en-maquinas-paralelas-no-relacionadas-y-generalizaciones","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/investigacion-operativa\/nuevos-algoritmos-para-el-problema-de-secuenciacion-en-maquinas-paralelas-no-relacionadas-y-generalizaciones\/","title":{"rendered":"Nuevos algoritmos para el problema de secuenciaci\u00f3n en m\u00e1quinas paralelas no relacionadas y generalizaciones"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Luis Fanjul Peyr\u00f3 <\/strong><\/h2>\n<p>Para iniciar esta tesis doctoral se busc\u00f3 un problema de producci\u00f3n sencillo pero de amplia aplicaci\u00f3n pr\u00e1ctica que permitiera adaptarlo para llegar a problemas m\u00e1s generales y de m\u00e1s amplia aplicaci\u00f3n. Por este motivo, nos centramos en las m\u00e1quinas paralelas, y dentro de ellas, en las no relacionadas dado que son una generalizaci\u00f3n de los casos de m\u00e1quinas id\u00e9nticas y de las uniformemente relacionadas. Escogimos el objetivo de minimizar el tiempo m\u00e1ximo de finalizaci\u00f3n o cm\u00e1x, uno de los m\u00e1s comunes de la literatura. Este problema tiene la facultad de que, a pesar de su car\u00e1cter te\u00f3rico, tiene una amplia aplicaci\u00f3n pr\u00e1ctica, como el caso de secuenciar las tareas de los hornos de cocci\u00f3n cer\u00e1micos. Por otra parte se quer\u00eda ampliar el problema para el caso en que no se usaran todas las m\u00e1quinas o no se hicieran todos los trabajos necesariamente. las metas perseguidas son el presentar unos algoritmos sencillos y potentes para la resoluci\u00f3n del problema r\/\/cm\u00e1x, capaces de constituirse en el estado del arte. Dado que los modernos ordenadores montan casi en su totalidad varios n\u00facleos en su cpu y los algoritmos se van adaptando a este hecho, tambi\u00e9n se ha buscado realizar una adaptaci\u00f3n de los algoritmos para su uso en paralelo. finalmente, se pone como meta el encontrar m\u00e9todos eficaces y sencillos para la resoluci\u00f3n de problemas de este tipo en donde no se emplearan todas las m\u00e1quinas o no se realizaran todos los trabajos. en la presente tesis doctoral se realiz\u00f3 un amplio estudio de la literatura existente respecto al problema de m\u00e1quinas paralelas no relacionadas y se extrajo el estado del arte, as\u00ed como un estudio del posible tipo de instancias a emplear, dado que no exist\u00eda una grupo de instancias tipo para este problema. se presentan cuatro algoritmos iniciales sencillos que mejoran los resultados del estado del arte en algunos casos y dan mejores resultados de media en el conjunto total de instancias tratadas. Dichos algoritmos se basan en m\u00e9todos iterativos en los que se realiza una b\u00fasqueda local de inserci\u00f3n seguida de una b\u00fasqueda local de intercambio hasta \u00f3ptimo local de ambas, seguidas de diversos m\u00e9todos de modificaci\u00f3n parcial de la soluci\u00f3n para volver de nuevo con esta soluci\u00f3n modificada a las b\u00fasquedas locales. se introducen m\u00e9todos que buscan disminuir el grado de aleatoriedad de los primeros algoritmos, donde se llega a desarrollar tres nuevos algoritmos que mejoran los anteriores y que destacan con mejores resultados que el estado del arte en pr\u00e1cticamente todos los casos. Un nuevo algoritmo h\u00edbrido donde se a\u00fanan todas las caracter\u00edsticas de los m\u00e9todos desarrollados hasta ese momento nos lleva a mejorar significativamente los resultados obtenidos. no obstante los buenos resultados, se proponen nuevos m\u00e9todos basados en una disminuci\u00f3n del n\u00famero de variables a tener en cuenta en la resoluci\u00f3n del problema que acaban derivando en cinco nuevos algoritmos que nos llevan a mejorar a\u00fan m\u00e1s los valores ya obtenidos por los anteriores m\u00e9todos propuestos. es de destacar que los algoritmos propuestos no solo obtienen buenos resultados, si no que van mejorando estos resultados a medida que se les da m\u00e1s tiempo de ejecuci\u00f3n. se realizan las modificaciones pertinentes a los mejores algoritmos desarrollados en aras de paralelizar parte de las tareas que realizan y esto nos permite compararlos con el estado del arte. Los resultados muestran como el mejor algoritmo desarrollado es capaz de superar al m\u00e9todo representativo del estado del arte tambi\u00e9n en el ambiente paralelo. finalmente, se presenta el problema de m\u00e1quinas opcionales y selecci\u00f3n de trabajos, realizando primeramente su formulaci\u00f3n matem\u00e1tica para posteriormente mostrar los m\u00e9todos m\u00e1s favorables para la soluci\u00f3n de este tipo de problemas, basados, en el caso de la selecci\u00f3n de m\u00e1quinas, en un elaboraci\u00f3n de un ranking de m\u00e1quinas, seguidos de una selecci\u00f3n iterativa de ellas y una resoluci\u00f3n final por distintos m\u00e9todos. por \u00faltimo hacemos una reflexi\u00f3n sobre todo lo estudiado y una discusi\u00f3n sobre las posibles l\u00edneas de investigaci\u00f3n que deja abiertas la presente tesis doctoral.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Nuevos algoritmos para el problema de secuenciaci\u00f3n en m\u00e1quinas paralelas no relacionadas y generalizaciones<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Nuevos algoritmos para el problema de secuenciaci\u00f3n en m\u00e1quinas paralelas no relacionadas y generalizaciones <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Luis Fanjul Peyr\u00f3 <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Polit\u00e9cnica de Valencia<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 14\/01\/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>Rub\u00e9n Ruiz Garc\u00eda<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: Ana isabel S\u00e1nchez gald\u00f3n <\/li>\n<li>Rafael Marti cunquero (vocal)<\/li>\n<li>paz P\u00e9rez gonz\u00e1lez (vocal)<\/li>\n<li>ram\u00f3n \u00e1lvarez-vald\u00e9s olagu\u00edbel (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Luis Fanjul Peyr\u00f3 Para iniciar esta tesis doctoral se busc\u00f3 un problema de producci\u00f3n sencillo pero de [&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":[6264,16820],"tags":[134768,214004,192895,36862,27418,75877],"class_list":["post-106304","post","type-post","status-publish","format-standard","hentry","category-investigacion-operativa","category-politecnica-de-valencia","tag-ana-isabel-sanchez-galdon","tag-luis-fanjul-peyro","tag-paz-perez-gonzalez","tag-rafael-marti-cunquero","tag-ramon-alvarez-valdes-olaguibel","tag-ruben-ruiz-garcia"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/106304","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=106304"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/106304\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=106304"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=106304"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=106304"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}