RUO Home

Repositorio Institucional de la Universidad de Oviedo

View Item 
  •   RUO Home
  • Producción Bibliográfica de UniOvi: RECOPILA
  • Tesis
  • View Item
  •   RUO Home
  • Producción Bibliográfica de UniOvi: RECOPILA
  • Tesis
  • View Item
    • español
    • English
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

All of RUOCommunities and CollectionsBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_issnAuthor profilesThis CollectionBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_issn

My Account

LoginRegister

Statistics

View Usage Statistics

RECENTLY ADDED

Last submissions
Repository
How to publish
Resources
FAQs
Las tesis leídas en la Universidad de Oviedo se pueden consultar en el Campus de El Milán previa solicitud por correo electrónico: buotesis@uniovi.es

Evolving priority rules for scheduling problems by means of hyper-heuristics

Other title:

Cálculo de reglas de prioridad para problemas de scheduling con hiperheurísticos

Author:
Gil Gala, Francisco JavierUniovi authority
Director:
Varela Arias, José RamiroUniovi authority; Sierra Sánchez, María RitaUniovi authority
Centro/Departamento/Otros:
Informática, Departamento deUniovi authority
Publication date:
2021-07-26
Descripción física:
179 p.
Abstract:

Los problemas de planificación o scheduling aparecen con profusión en numerosos campos de la industria y la gestión, destacando por su alta complejidad computacional (generalmente son NP-duros). Por este motivo, suelen requerir del uso de algoritmos y técnicas avanzadas de Inteligencia Artificial. En particular, los problemas de scheduling de una máquina han incrementado su popularidad durante las últimas décadas, debido a su propio interés y dificultad, así como por aparecer frecuentemente al descomponer otros problemas de scheduling más complejos. Esta tesis se centra en un problema de esta clase, en el que se deben planificar una serie de trabajos en una sola máquina, con el objetivo de minimizar la función de retardo total, denominada total tardiness. La característica particular de este problema es que la máquina puede procesar más de un trabajo a la vez, pero esta capacidad varía a lo largo del tiempo. Este problema se introdujo en [Computers & Industrial Engineering 85, 306-315, 2015], en el contexto de la planificación de los tiempos de carga de una gran flota de vehículos eléctricos, y se denota con (1;Cap(t)||Ti). Resolver el problema de planificación de carga de vehículos eléctricos (EVCSP) requiere resolver, a lo largo del tiempo, varias instancias del problema (1;Cap(t)||Ti). Debido a la intratabilidad computacional, y a los estrictos requisitos de tiempo real del EVCSP, la planificación en línea representa el único enfoque adecuado para abordar el problema. El problema (1;Cap(t)||Ti) puede resolverse empleando la regla de prioridad Apparent Tardiness Cost (ATC), comúnmente utilizada en el contexto de scheduling con objetivos de retardo o tardiness. Debido a su bajo coste computacional, este enfoque es muy adecuado para la planificación en línea: el trabajo con mayor prioridad, entre los disponibles en un momento dado, es el siguiente a planificar. Como en el caso de la regla ATC, las reglas de prioridad pueden ser definidas manualmente por expertos en el dominio del problema. Sin embargo, nuestra hipótesis es que los métodos automáticos pueden capturar algunas características del problema de scheduling que no son evidentes para los expertos humanos. El objetivo de esta tesis es el desarrollo automatizado de reglas de prioridad, adaptadas específicamente al problema (1;Cap(t)||Ti). Una forma natural de abordar esta tarea es mediante el uso de hiperheurísticos, ya que la búsqueda debe realizarse en un espacio de heurísticos, y no en un espacio de soluciones al problema de scheduling. Por lo tanto, dado que las reglas de prioridad son expresiones aritméticas, que pueden ser representadas naturalmente por árboles, comenzamos

Los problemas de planificación o scheduling aparecen con profusión en numerosos campos de la industria y la gestión, destacando por su alta complejidad computacional (generalmente son NP-duros). Por este motivo, suelen requerir del uso de algoritmos y técnicas avanzadas de Inteligencia Artificial. En particular, los problemas de scheduling de una máquina han incrementado su popularidad durante las últimas décadas, debido a su propio interés y dificultad, así como por aparecer frecuentemente al descomponer otros problemas de scheduling más complejos. Esta tesis se centra en un problema de esta clase, en el que se deben planificar una serie de trabajos en una sola máquina, con el objetivo de minimizar la función de retardo total, denominada total tardiness. La característica particular de este problema es que la máquina puede procesar más de un trabajo a la vez, pero esta capacidad varía a lo largo del tiempo. Este problema se introdujo en [Computers & Industrial Engineering 85, 306-315, 2015], en el contexto de la planificación de los tiempos de carga de una gran flota de vehículos eléctricos, y se denota con (1;Cap(t)||Ti). Resolver el problema de planificación de carga de vehículos eléctricos (EVCSP) requiere resolver, a lo largo del tiempo, varias instancias del problema (1;Cap(t)||Ti). Debido a la intratabilidad computacional, y a los estrictos requisitos de tiempo real del EVCSP, la planificación en línea representa el único enfoque adecuado para abordar el problema. El problema (1;Cap(t)||Ti) puede resolverse empleando la regla de prioridad Apparent Tardiness Cost (ATC), comúnmente utilizada en el contexto de scheduling con objetivos de retardo o tardiness. Debido a su bajo coste computacional, este enfoque es muy adecuado para la planificación en línea: el trabajo con mayor prioridad, entre los disponibles en un momento dado, es el siguiente a planificar. Como en el caso de la regla ATC, las reglas de prioridad pueden ser definidas manualmente por expertos en el dominio del problema. Sin embargo, nuestra hipótesis es que los métodos automáticos pueden capturar algunas características del problema de scheduling que no son evidentes para los expertos humanos. El objetivo de esta tesis es el desarrollo automatizado de reglas de prioridad, adaptadas específicamente al problema (1;Cap(t)||Ti). Una forma natural de abordar esta tarea es mediante el uso de hiperheurísticos, ya que la búsqueda debe realizarse en un espacio de heurísticos, y no en un espacio de soluciones al problema de scheduling. Por lo tanto, dado que las reglas de prioridad son expresiones aritméticas, que pueden ser representadas naturalmente por árboles, comenzamos

Description:

Tesis con mención internacional y por compendio de publicaciones.

URI:
http://hdl.handle.net/10651/61600
Local Notes:

DT(SE) 2021-125

Collections
  • Tesis [7669]
Files in this item
Thumbnail
untranslated
TD_FranciscoJavierGilGala.pdf (9.829Mb)
Embargado hasta:2031-07-26
Compartir
Exportar a Mendeley
Estadísticas de uso
Estadísticas de uso
Metadata
Show full item record
Página principal Uniovi

Biblioteca

Contacto

Facebook Universidad de OviedoTwitter Universidad de Oviedo
The content of the Repository, unless otherwise specified, is protected with a Creative Commons license: Attribution-Non Commercial-No Derivatives 4.0 Internacional
Creative Commons Image