| Summary: | El objetivo principal de este trabajo de tesis
es ofrecer soluciones con un buen valor del makespan a dos problemas de secuenciación con poco esfuerzo computacional. El primer problema de secuenciación consiste en secuenciar tareas en máquinas paralelas no relacionadas con tiempos de preparación dependientes de la máquina y de la secuencia tal que se minimize el
makespan o tiempo de terminación de la última tarea que se procese. El segundo problema, además de lo anterior considera un esquema de tareas de mantenimiento
preventivo de las máquinas, por lo que se tienen periodos de tiempo en los que las máquinas no están disponibles para realizar el procesamiento de las tareas.
El método de estudio consiste en realizar un análisis de las técnicas de solución en problemas afines y considerar las características que deben ser tomadas en
cuenta para desarrollar una metodología de solución eficiente. Como resultado de lo anterior analizamos cada problema en dos pasos. Primero, formulamos un modelo
matemático para obtener soluciones óptimas, determinamos el alcance del modelo matemático en cuanto al tamaño de instancias que puede resolver, analizamos las soluciones de la relajación lineal del modelo, el tiempo de cómputo para obtenerlas dichas soluciones y derivamos un conjunto de desigualdades válidas para fortalecer el modelo. Segundo, proponemos algoritmos de solución para los casos en que el modelo es incapaz de obtener soluciones en un tiempo de cómputo razonable para la mayoría de las instancias. En dichos algoritmos se proponen dos nuevas estrategias, una para lidiar con la estructura mínmax de la función objetivo y una m´as para explotar las relaciones entre los tipos de decisión que surgen en cada problema.
|
|---|
