Dissertations / Theses on the topic 'Problemas de Scheduling'

[EN] Many industrial problems can be modelled as a scheduling problem where some resources are assigned to tasks so as to minimize the completion time, to reduce the use of resources, idle time, etc. There are several scheduling problems which try to represent different kind of situations that can appear in real world problems. Job Shop Scheduling Problem (JSP) is the most used problem. In JSP there are different jobs, every job has different tasks and these tasks have to be executed by different machines. JSP can be extended to other problems in order to simulate more real problems. In this work we have used the problem job shop with operators JSO(n,p) where each task must also be assisted by one operator from a limited set of them. Additionally, we have extended the classical JSP to a job-shop scheduling problem where machines can consume different amounts of energy to process tasks at different rates (JSMS). In JSMS operation has to be executed by a machine that has the possibility to work at different speeds. Scheduling problems consider optimization indicators such as processing time, quality and cost. However, governments and companies are also interested in energy-consumption due to the rising demand and price of fuel, the reduction in energy commodity reserves and growing concern about global warming. In this thesis, we have developed new metaheuristic search techniques to model and solve the JSMS problem. Robustness is a common feature in real life problems. A system persists if it remains running and maintains his main features despite continuous perturbations, changes or incidences. We have developed a technique to solve the $JSO(n,p)$ problem with the aim of obtaining optimized and robust solutions. We have developed a dual model to relate optimality criteria with energy consumption and robustness/stability in the JSMS problem. This model is committed to protect dynamic tasks against further incidences in order to obtain robust and energy-aware solutions. The proposed dual model has been evaluated with a memetic algorithm to compare the behaviour against the original model. In the JSMS problem there are a relationship between Energy-efficiency, Robustness and Makespan. Therefore, the relationship between these three objectives is studied. Analytical formulas are proposed to analyse the relationship between these objectives. The results show the trade-off between makespan and robustness, and the direct relationship between robustness and energy-efficiency. To reduce the makespan and to process the tasks faster, energy consumption has to be increased. When the energy consumption is low it is because the machines are not working at highest speed. So, if an incidence appears, the speed of these machines can be increased in order to recover the time lost by the incidence. Hence robustness is directly related with energy consumption. Additionally, robustness is also directly related with makespan because, when makespan increases, there are more gaps in the solution, these incidences can be absorbed by these natural buffers. The combination of robustness and stability gives the proposal an added value due to since an incidence cannot be directly absorbed by the disrupted task and it can be repaired by involving only a small number of tasks. In this work we propose two different techniques to manage rescheduling over the JSMS problem. This work represents a breakthrough in the state of the art of scheduling problems and in particular the problem where energy consumption can be controlled by the rate of the machines.
[ES] Muchos de los problemas industriales se pueden modelar como un problema de scheduling donde algunos recursos son asignados a tareas a fin de minimizar el tiempo de finalización, para reducir el uso de los recursos, el tiempo de inactividad, etc. Job-Shop scheduling (JSP) es el problema más utilizado. En JSP hay diferentes trabajos, cada trabajo tiene diferentes tareas y estas tareas tienen que ser ejecutadas por diferentes máquinas. JSP puede ser extendido a otros problemas con el fin de simular una mayor cantidad de problemas reales. En este trabajo se ha utilizado el problema job shop scheduling con operadores JSO(n, p), donde cada tarea también debe ser asistida por un operador de un conjunto limitado de ellos. Además, hemos ampliado el clásico problema JSP a un problema donde las máquinas pueden consumir diferentes cantidades de energía al procesar tareas a diferentes velocidades (JSMS). En JSMS las operaciones tiene que ser ejecutadas por una máquina que tiene la posibilidad de trabajar a diferentes velocidades. Los problemas de scheduling consideran indicadores de optimización tales como: el procesamiento de tiempo, la calidad y el coste. Sin embargo, hoy en día los gobiernos y los empresarios están interesados también en el control del consumo de energía debido al aumento de la demanda y del precio de los combustibles, la reducción de las reservas de materias primas energéticas y la creciente preocupación por el calentamiento global. En esta tesis, hemos desarrollado nuevas técnicas de búsqueda metaheurística para modelar y resolver el problema JSMS. La robustez es una característica común en los problemas de la vida real. Un sistema persiste si permanece en funcionamiento y mantiene sus principales características a pesar de las perturbaciones continuas, cambios o incidencias. Hemos desarrollado una técnica para resolver el problema JSO(n, p) con el objetivo de obtener soluciones robustas y optimizadas. Hemos desarrollado un modelo dual para relacionar los criterios de optimalidad con el consumo de energía y la robustez/estabilidad en el problema JSMS. Este modelo se ha desarrollado para proteger a las tareas dinámicas contra incidencias, con el fin de obtener soluciones sólidas y que tengan en cuenta el consumo de la energía. El modelo dual propuesto ha sido evaluado con un algoritmo memético para comparar el comportamiento frente al modelo original. En el problema JSMS hay una relación entre la eficiencia energética, la robustez y el makespan. Por lo tanto, se estudia la relación entre estos tres objetivos. Se desarrollan fórmulas analíticas para representar la relación estimada entre estos objetivos. Los resultados muestran el equilibrio entre makespan y robustez, y la relación directa entre la robustez y eficiencia energética. Para reducir el makespan, el consumo de energía tiene que ser aumentado para poder procesar las tareas más rápido. Cuando el consumo de energía es bajo, debido a que las máquinas no están trabajando a la velocidad más alta, si una incidencia aparece, la velocidad de estas máquinas puede ser aumentada con el fin de recuperar el tiempo perdido por la incidencia. Por lo tanto la robustez está directamente relacionada con el consumo de energía. Además, la robustez también está directamente relacionada con el makespan porque, cuando el makespan aumenta hay más huecos en la solución, que en caso de surgir incidencias, estas pueden ser absorbidas por estos buffers naturales. La combinación de robustez y estabilidad da un valor añadido debido a que si una incidencia no puede ser absorbida directamente por la tarea interrumpida, esta puede ser reparada mediante la participación un pequeño número de tareas.En este trabajo se proponen dos técnicas diferentes para gestionar el rescheduling sobre el problema JSMS. Este trabajo representa un avance en el estado del arte en los problemas de scheduling y en el problema donde el consumo de energía p
[CAT] Molts dels problemes industrials es poden modelar com un problema de scheduling on alguns recursos són assignats a tasques a fi de minimitzar el temps de finalització, per a reduir l'ús dels recursos, el temps d'inactivitat, etc. Existeixen diversos tipus de problemes de scheduling que intenten representar diferents situacions que poden aparèixer en els problemes del món real. Job-Shop scheduling (JSP) és el problema més utilitzat. En JSP hi ha diferents treballs, cada treball té diferents tasques i aquestes tasques han de ser executades per diferents màquines. JSP pot ser estès a altres problemes amb la finalitat de simular una major quantitat de problemes reals. En aquest treball s'ha utilitzat el problema job shop scheduling amb operadors JSO(n, p), on cada tasca també ha de ser assistida per un operador d'un conjunt limitat d'ells. A més, hem ampliat el clàssic problema JSP a un problema on les màquines poden consumir diferents quantitats d'energia per a processar tasques a diferents velocitats (JSMS). Els problemes de scheduling consideren indicadors d'optimització tals com: el processament de temps, la qualitat i el cost. No obstant açò, avui en dia els governs i els empresaris estan interessats també amb el control del consum d'energia a causa de l'augment de la demanda i del preu dels combustibles, la reducció de les reserves de matèries primeres energètiques i la creixent preocupació per l'escalfament global. En aquesta tesi, hem desenvolupat noves tècniques de cerca metaheurística per a modelar i resoldre el problema JSMS. La robustesa és una característica comuna en els problemes de la vida real. Un sistema persisteix si continua en funcionament i manté les seues principals característiques malgrat les pertorbacions contínues, canvis o incidències. Hem desenvolupat una tècnica per a resoldre el problema JSO(n, p) amb l'objectiu d'obtenir solucions robustes i optimitzades. Hem desenvolupat un model dual per a relacionar els criteris de optimalidad amb el consum d'energia i la robustesa/estabilitat en el problema JSMS. Aquest model s'ha desenvolupat per a protegir a les tasques dinàmiques contra incidències, amb la finalitat d'obtenir solucions sòlides i que tinguen en compte el consum de l'energia. El model dual proposat ha sigut evaluat amb un algorisme memético per a comparar el comportament front un model original. En el problema JSMS hi ha una relació entre l'eficiència energètica, la robustesa i el makespan. Per tant, s'estudia la relació entre aquests tres objectius. Es desenvolupen fórmules analítiques per a representar la relació estimada entre aquests objectius. Els resultats mostren l'equilibri entre makespan i robustesa, i la relació directa entre la robustesa i l'eficiència energètica. Per a reduir el makespan, el consum d'energia ha de ser augmentat per a poder processar les tasques més ràpid. Quan el consum d'energia és baix, a causa que les màquines no estan treballant a la velocitat més alta, si una incidència apareix, la velocitat d'aquestes màquines pot ser augmentada amb la finalitat de recuperar el temps perdut per la incidència. Per tant la robustesa està directament relacionada amb el consum d'energia. A més, la robustesa també està directament relacionada amb el makespan perquè, quan el makespan augmenta hi ha més buits en la solució, que en cas de sorgir incidències, aquestes poden ser absorbides per els buffers naturals. La combinació de robustesa i estabilitat dóna un valor afegit a causa de que si una incidència no pot ser absorbida directament per la tasca interrompuda, aquesta pot ser reparada mitjançant la participació d'un xicotet nombre de tasques. En aquest treball es proposen dues tècniques diferents per a gestionar el rescheduling sobre el problema JSMS. Aquest treball representa un avanç en l'estat de l'art en els problemes de scheduling i, en particular, en el problema on el consum d'energia pot ser controlat per
Escamilla Fuster, J. (2016). Eficiencia Energética y Robustez en Problemas de Scheduling [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/64062
TESIS

Problemas em Scheduling estocástico do tipo flow-shop no-wait pertencentes à classe NP-completo são tratados neste trabalho em duas abordagens distintas. Na primeira, quando as realizações das variáveis aleatórias que descrevem os tempos de processamento das operações ocorrem "a priori", é apresentado um estudo do comportamento de heurísticas através de métodos estatísticos. Na segunda, quando as realizações das variáveis aleatórias ocorrem durante o processamento, é desenvolvido um estudo analítico da relação entre a probabilidade de um Schedule estocástico satisfazer a condição flow-shop no-wait e o intervalo de tempo decorrido entre duas tarefas adjacentes.

Doctor en Sistemas de Ingeniería en cotutela con Ecole Normale Supérieure
Convex optimization has been a powerful tool for designing algorithms. In practice is a widely used in areas such as operations research and machine learning, but also in many fundamental combinatorial problems they yield to the best know approximations algorithms providing unconditional guarantees over the solution quality. In the first part of this work we study the effect of constructing convex relaxations to a packing problem, based on applying lift & project methods. We exhibit a weakness of this relaxations when they are obtained from the natural formulations of this problem, by showing the impossibility of reducing the gap even when this relaxations are very large. We provide a way of combining symmetry breaking procedures and lift & project methods to obtain arbitrarily good gaps. In the second part of this thesis we study online selection problems, that is, elements arrive over time and we have to select some of them, irrevocably, in order to meet some combinatorial constraints, but also trying to maximize the quality of the selection. Usually this quality in measured in terms of weight, but we consider a stronger variant in which weights are not necessarily known because of information availability. Instead, as long as we can rank the elements, we can provide a general framework to obtain approximation algorithms with good competitive ratios in many contexts.

O ambiente competitivo no qual as empresas estão inseridas é caracterizado por mudanças frequentes na demanda de seus produtos e por uma necessidade em reduzir custos. Para obter sucesso frente à concorrência, se faz necessário alcançar resultados através da melhoria do processo produtivo, oferecendo respostas mais rápidas a variações na demanda e com uma utilização adequada dos recursos produtivos. Neste contexto, a utilização de softwares Advanced Planning and Scheduling com regra personalizada de programação possibilita melhoria no planejamento e programação da empresa no sentido dos objetivos citados. A partir disso, este trabalho propõe uma sistemática de desenvolvimento e implantação de regras de programação personalizadas. Após, é apresentada aplicação de um caso prático no qual foram detalhadas todas as etapas propostas na sistemática, desde o entendimento das necessidades da empresa até a avaliação dos resultados obtidos.
The competitive environment in which firms operate is characterized by frequent changes in product demand and a necessity to reduce costs. To succeed against the competition, it is necessary to gain competitive advantage by improving the production process, providing faster responses to changes in demand and proper use of productive resources. In this context, the use of Advanced Planning and Scheduling software with custom programming rule allows improved planning and programming company towards the objectives mentioned. This study proposes a systematic development and deployment of custom programming rules, next it is presented a case study which detail the stages proposed in the systematic, from the understanding of the business requirement until the evaluation of results.

Ingeniero Civil Matemático
El objetivo principal del presente trabajo de memoria de título es el cálculo de cotas para precio de la anarquía de algunos juegos asociados a problemas de scheduling. Se comienza realizando una revisión general de lo que son los problemas de scheduling, un algoritmo de aproximación y la relación que existe entre teoría de juegos y los problemas de scheduling. Ahí se identifica el cuociente de aproximación del algoritmo de Smith para problemas de scheduling, con el precio de la anarquía de un juego asociado. Se realiza también una revisión de los principales resultados conocidos útiles para el presente trabajo. Más adelante se calcula el precio de la anarquía para ciertos juegos de scheduling donde la función objetivo es la suma ponderada de los tiempos de completación. Se demuestra que en el caso de máquinas idénticas, el precio de la anarquía en estrategias mixtas es 3/2. Se demuestra también que en máquinas paralelas con velocidades, el precio de la anarquía es mayor o igual a 2. Por último, se prueba acá que en el caso en que todos los trabajos tienen el mismo tamaño, el precio de la anarquía del juego de scheduling en máquinas paralelas con velocidades y suma ponderada de los tiempos de completación como función objetivo es 1. Para seguir se estudia el juego asociado al problema de scheduling en el cual la función objetivo es la suma de los tiempos de completación, y las máquinas son todas excepto una idénticas entre sí, la máquina restante es de velocidad mayor a las demás, y las máquinas que son más lentas son una cantidad suficientemente grande. Para este juego de scheduling se demuestra que el precio de la anarquía es e/(e-1). Después se estudia el juego mencionado anteriormente en su caso más general, en el cual la cantidad de máquinas lentas no está restringida a ser suficientemente grande. Para este problema se demuestra que el precio de la anarquía está acotado superiormente por 5/3. Se muestra además un problema de programación lineal cuyo óptimo acota superiormente el precio de la anarquía del juego de scheduling de máquinas paralelas con velocidades y suma de los tiempos de completación como función objetivo. Finalmente, se plantea como conjetura que el precio de la anarquía del juego asociado al problema de scheduling más general antes mencionado es efectivamente e/(e-1), y se muestran pruebas computacionales que fueron realizadas, con las cuales se justifica el plantear esta conjetura.

Este trabalho tem como objetivo solucionar problemas complexos em diferentes segmentos da Engenharia de Produção e Transporte a partir da utilização de técnicas de otimização. São consideradas as áreas de sistemas de saúde, transportes e análise sensorial, envolvendo problemas de formação de grade de horários e análise de clusters. De forma específica, as abordagens objetivam: (i) em relação ao setor hospitalar, alocar especialidades cirúrgicas em uma grade de horários de um hospital de modo a minimizar a variância do tempo pós-operatório; (ii) quanto à análise sensorial, desenvolver um índice capaz de identificar painelistas que necessitam de treinamento utilizando conceitos de análise de clusters; (iii) no setor aeroportuário, identificar aeroportos com baixa capacidade preditiva de demanda e relacioná-los com suas características físicas, a partir da análise de clusters. Em todos os problemas abordados, as soluções envolvendo métodos de otimização se mostraram adequadas, com resultados satisfatórios.
This study aims to solve complex problems in different segments of Production Engineering and Transportation using optimization techniques. Different areas are considered, such as the areas of health systems, transport and sensory analysis, involving the timetable scheduling problem and cluster analysis. Specifically, this works aims to: (i) in relation to the hospital sector, allocate surgical specialties in a timetable in order to minimize the variance of postoperative time; (ii) for the sensory analysis, develop an index able to identify panelists who require training, using concepts of cluster analysis; (iii) in the airport sector, identify airports with low predictive capacity of demand and relate them to their physical characteristics, using cluster analysis. In all addressed problems, solutions involving optimization methods were adequate, with satisfactory results.

Los problemas de scheduling aparecen con profusión en la vida real en numerosos entornos productivos y de servicios. Se trata de problemas que requieren organizar en el tiempo la ejecución de tareas que compiten por el uso de un conjunto finito de recursos y que están sujetas a un conjunto de restricciones impuestas por factores como las características físicas del entorno, relaciones temporales o la normativa laboral. Además se trata de optimizar uno o varios criterios que se representan mediante funciones objetivo y que están relacionados normalmente con el coste, el beneficio o el tiempo de ejecución.Algunos ejemplos de problemas de esta naturaleza son los siguientes:· Fabricación de obleas para circuitos semiconductores, donde cada oblea precisa de una serie de tareas como limpieza, oxidación, metalización, etc. El objetivo puede maximizar la utilización de algunas máquinas que son cuello de botella o minimizar el tiempo de ejecución.· Planificar el aterrizaje de un conjunto de aviones sujetos a restricciones temporales que dependen de las características de los aviones. Los objetivos pueden ser minimizar la penalización por desvío 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ón de los vehículos y de ajustar los turnos de los conductores de acuerdo con la normativa laboral.· Enrutamiento de paquetes de datos a través líneas de comunicación, 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úsqueda inteligentes para encontrar soluciones aceptables en un tiempo razonable. Así, en la literatura se pueden encontrar aproximaciones a los problemas de scheduling basadas en prácticamente todas las metaheurísticas conocidas y en particular en los algoritmos de búsqueda heurística propios de áreas como la Investigación Operativa y la Inteligencia Artificial.En esta tesis nos centramos en el problema Job Shop Scheduling y en la técnica de búsqueda heurística en espacios de estados. Nuestro objetivo es diseñar estrategias que resulten eficaces y eficientes para diferentes funciones objetivo, tanto para encontrar soluciones exactas, cuando el tamaño del problema lo permita, como para obtener soluciones aproximadas para instancias mayores. La función objetivo a la que los investigadores han prestado mayor atención es sin duda el makespan, o tiempo de finalización de la última tarea. Las propiedades de esta versión del problema son muy bien conocidas y han permitido desarrollar métodos exactos y aproximados muy eficientes que se basan en el concepto de camino crítico. El inconveniente de estos métodos es que no se generalizan de forma eficiente para otras funciones objetivo como el tiempo de flujo total o el tardiness.La aportación principal de esta tesis es la formalización de un método de poda basado en relaciones de dominancia entre los estados del espacio de búsqueda que se puede aplicar en principio a todas las funciones objetivo convencionales. Aunque el método no resulta competitivo con los métodos basados en el camino crítico cuando se trata de minimizar el makespan, sí lo es con los métodos que no están basados en el camino crítico 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ándar demuestran que el método es competitivo con otros métodos del estado del arte tanto para obtener soluciones óptimas como sub-óptimas.

Problemas de sequenciamento são muito comuns, eles existem sempre que há uma escolha sobre a ordem em que várias tarefas podem ser realizadas. Seja o negócio uma companhia aérea, um hotel, um fabricante de computadores ou uma universidade, esses problemas fazem parte do cotidiano. A aplicação das técnicas de sequenciamento permite, por exemplo, a redução dos custos e o aumento na agilidade da cadeia de suprimentos, afetando as operações no inicio e no fim da cadeia de suprimentos pelo mundo inteiro. Este trabalho parte da intenção de abordar os princípios e as técnicas de Scheduling, com a finalidade de propor um modelo de sequenciamento para a solução de um problema em sistemas produtivos do tipo job shop com n tarefas e m máquinas, considerando os tempos de setup dependentes da sequência e tendo como horizonte de planejamento o curto prazo. O objetivo é o de minimizar a perda dos tempos não produtivos. Neste contexto, a pesquisa apresenta um enfoque tanto exploratório, quanto aplicado. Pode ser considerado exploratório, uma vez que a revisão da literatura é referência central para o desenvolvimento do modelo matemático. É aplicado considerando-se o desenvolvimento do modelo e avaliação de sua aplicabilidade. Sendo assim, a partir da definição do problema e desenvolvimento do modelo por meio do uso de técnicas matemáticas e abordagens da pesquisa operacional constatou-se que as conclusões tiradas podem inferir decisões para o problema real. Sendo que, as considerações aqui feitas têm por finalidade relatar os fatos constatados nos experimentos realizados, visando contribuir com futuras pesquisas na área.
Sequencing problems are very common, they happen every time there is a choice regarding the order in which several tasks can be performed. The business can be an airline, a hotel, a computer manufacturer or a university; these issues are part of their routine. The application of the sequencing techniques allows, for example, reducing the costs and fastening the supply chain all over the world. This work has an approach to Scheduling principles and techniques, with the objective of proposing a sequencing model for the solution of a problem in productive systems such as job shop with n tasks and m machines, considering setup times dependent on the sequence and adopting a short term planning. The goal is to minimize the waste of unproductive time. In this context, the research presents an approach both exploratory and applied. It can be considered exploratory, once that the literature review is a main reference to the development of a mathematical model. It is applied when we consider the development of the model and evaluation of its applicability. Thus, from the problem definition and the model development by the use of mathematical techniques and approaches of the operational research, we found that the conclusions drawn from the model might infer decisions for a real problem. The considerations shown here aim to report the facts given in the conducted experiments, intending to contribute to future researches in the area.

Orientador: Eduardo Candido Xavier
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-18T10:12:53Z (GMT). No. of bitstreams: 1 Peixoto_RobsonRobertoSouza_M.pdf: 1268588 bytes, checksum: ff8a093aa133696dcd5bbe31bc4d6e78 (MD5) Previous issue date: 2011
Resumo: Nesta dissertação estudamos algoritmos para resolver problemas de escalonamento de tarefas em grades computacionais. Dado um conjunto de tarefas submetidas a uma grade computacional, deve-se definir em quais recursos essas tarefas serão executadas. Algoritmos de escalonamento são empregados com o objetivo de minimizar o tempo necessário para executar todas as tarefas (makespan) que foram submetidas. Nosso foco é estudar os atuais algoritmos de escalonamento usados em grades computacionais e comparar estes algoritmos. Nesta dissertação apresentamos algoritmos onlines, aproximados e heurísticas para o problema. Como resultados novos, provamos fatores de aproximação para o algoritmo RR quando utilizado para resolver os problemas R; sit|Tj|Cmax, R; sit|Tj|TPCC, R; sit|Tj = L| Cmax e R; sit|Tj = L|TPCC é justo. Por fim, definimos uma interface que adiciona replicação de tarefas a qualquer algoritmo de escalonamento, onde nós mostramos a aproximação desta interface, e apresentamos uma comparação via simulação dos algoritmos sem e com replicação. Nossas simulações mostram que, com a utilização de replicação, houve a redução no makespan de até 80% para o algoritmo Min-min. Nas nossas análises também fazemos uso da métrica RTPCC que calcula exatamente a quantidade de instruções que foram usadas para executar todas as tarefas
Abstract: In this dissertation, we studied algorithms to solve task scheduling problems in computational grids. Given a task set that was submitted to a computational grid, the problem is to define in which resources these tasks will be executed and the order they will be executed. Scheduling algorithms are used in order to minimize the time required to execute all tasks (makespan). We studied the most recent scheduling algorithms proposed to be used in computational grids, and then compare them using simulations. In this dissertation we also present approximate algorithms and new heuristics for the problem. As new results, we proved approximation factors to the RR algorithm when applied to solve the problems R; sit|Tj|Cmax, R; sit|Tj|TPCC, R; sit|Tj = L| Cmax and R; sit|Tj = L|TPCC. Finally, we defined an interface that adds task replication capability to any scheduling algorithm. We then show approximation results for algorithms using this interface, and present a comparison of well know algorithms with and without replication. This comparison is done via simulation. Our simulations show that, with replication, there was up to 80% of reduction in the makespan to some algorithms like the Min-min
Mestrado
Teoria da Computação
Mestre em Ciência da Computação

Esta dissertação de mestrado apresenta um estudo sobre problemas de escalonamento de tarefas com atrasos de comunicação. Mais precisamente, são abordados problemas de escalonar um conjunto de tarefas em um conjunto de máquinas paralelas de número limitado ou não, e tarefas de tempo de processamento unitário, sujeitas a relações de precedência, e com atrasos de comunicação estabelecidos para cada par de tarefas precedentes, assumindo valores extremos, ou seja, podendo ser desprezíveis ou infinitamente grandes, isto com o objetivo de minimizaro o tempo em que a última tarefa escalonada termina seu processamento - minimização do makespan. Sendo assim, dois problemas são demostrados serem da classe NP-difícil. Para o primeiro, a quantidade de processadores é indicada a cada instância, sendo este resultado válido ainda que as relações de precedência formem um conjunto de cadeias (P|chains; cij ∈ {0, ∞}; pj = 1|Cmax). O segundo problema admite relações de precedência arbitrárias e é válido para qualquer quantidade fixa de processadores diferente de um (P2|prec;cij ∈ {0, ∞}; pj = 1|Cmax). Por outro lado, neste trabalho, dois outros problemas são demonstrados serem solúveis em tempo polinomial, ou seja, estarem na classe P, ambos quando uma quantidade ilimitada de processadores está disponível. É visto que, se a ordem de precedência das tarefas é limitada a uma árvore descendente, o problema é polinomial (P∞|tree; cij ∈ {0, ∞}; pj = 1|Cmax). O outro caso polinomial demonstrado é válido quando é permitido processar a mesma tarefa em mais de um processador (P∞|prec; cij ∈ {0, ∞}; pj = 1|Cmax). Para ambos os casos são apresentados os algoritmos polinomiais. Finalmente, são apresentados resultados para o problema de escalonar tarefas particionadas em conjuntos para os quais todas as tarefas devem ser processadas no mesmo processador. O problema é NP-difícil quando a quantidade de processadores é determinada a cada instância. Esse resultado é válido ainda que a precedência seja restrita a duas cadeias. O problema se torna polinomial quando o conjunto de partições é limitado por constante e as cadeias são restritas em uma das duas formas: pela quantidade delas ou pela quantidade de tarefas em cada uma delas. Como trabalho futuro, este estudo deixa em aberto a NP-Completude do problema de escalonar sob tais atrasos de comunicação de valores extremos, para uma quantidade fixa de processadores, quando a ordem de precedência é de alguma forma restrita, por exemplo, uma árvore descendente (Pm|out-tree;cij ∈ {0, ∞}; pj = 1|Cmax).
This Master’s Thesis presents a study on scheduling problems subject to communication delays. More precisely, this work involves job scheduling problems with a number of parallel machines, limited or not, and where the tasks (or jobs) have unit execution time, and are subject to some precedence relation. Communication delays are imposed at each pair of preceding tasks, taking extreme values, which may be negligible or infinitely large. The objective is minimize the completion time of the latest job to be processed, that is, to get the minimum makespan. Thus, NP-hard results are demonstrated for two cases. For the first, when the number of processors is indicated in the instance of the problem, and this result holds even when the precedence relation is restricted to a set of chains (P|chains; cij ∈ {0, ∞}; pj = 1|Cmax). The second results is valid when arbitrary precedence relations are allowed, and any fixed number of processors (greater than one) is available (P2|prec;cij ∈ {0, ∞}; pj = 1|Cmax). Two other problems are demonstrated to have polynomial time solutions, both when an unlimited number of processors are available. The first result imposes the precedence relation to be an out-tree (P∞|tree; cij ∈ {0, ∞}; pj = 1|Cmax). The second result is valid when the execution of the same job on multiples processors are allowed (P∞|prec; cij ∈ {0, ∞}; pj = 1|Cmax). For both cases, polynomial algorithms are presented. Finally, results are presented for the problem of job scheduling that are partitioned in sets which must be executed on the same processors. The problem is demonstrated to be NP-hard even if the precedence relation consists of two chains. Also, it is shown that the problem becomes solvable in polynomial time if the number of partitions is limited by a constant and the chains are restricted by a constant on either their number, or the number of tasks that each chain may have. As future work, this study leaves open whether is NP-hard the case to schedule tasks subject to such communication delays with extreme values, when a fixed number of processors is available, and the precedence relations are some how restricted, for example, by an out-tree (Pm|out-tree;cij ∈ {0, ∞}; pj = 1|Cmax).

Orientador: Vinicius Amaral Armentano
Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação
Made available in DSpace on 2018-08-10T19:15:18Z (GMT). No. of bitstreams: 1 FrancaFilho_MoacirFelizardode_D.pdf: 1342634 bytes, checksum: 4855202b36314e8c55f20746c709054e (MD5) Previous issue date: 2007
Resumo: Este trabalho é dedicado à programação de tarefas em máquinas paralelas. Dois ambientes são considerados. No primeiro, as máquinas são idênticas e o objetivo é a minimização da soma ponderada de custos de atraso. Todas as tarefas estão disponíveis para processamento no início do horizonte de programação e a cada uma são associadas uma data de entrega e uma penalização por atraso específicas. No segundo, as máquinas são não relacionadas e o objetivo é a minimização da soma ponderada de custos de avanço e de atraso. Instantes de liberação, datas de entrega, penalizações por avanço e por atraso são específicos para cada tarefa. Em ambos, as transições entre tarefas requerem tempos de preparação dependentes da seqüência de processamento. Os problemas são resolvidos por meio de GRASP e Busca Tabu. Memória de longo prazo é empregada para melhorar o desempenho das duas metaheurísticas. No GRASP, soluções de elite influenciam a fase construtiva. Na Busca Tabu, estratégias de diversificação e de intensificação fazem uso direto das soluções de elite e também de freqüências de residência. Como pós-otimização, nas duas metaheurísticas, realizam-se religações de caminhos entre as soluções de elite
Abstract: This work is dedicated to the scheduling of a set of jobs in parallel machines. Two scenarios are considered. In the first one, the machines are identical and the objective is the minimization of the weighted sum of tardiness costs. All jobs are ready for processing at the beginning of the scheduling horizon and to each one is associated a due date and a tardiness penalty. In the second scenario, the machines are non-related and the objective is the minimization of the weighted sum of earliness and tardiness costs. Ready times, due dates, earliness and tardiness penalties are specifics to each job. In both problems, the transitions between jobs require sequence dependent setup times. The problems are solved using GRASP and Tabu Search. Long term memory is applied to improve the performance of the metaheuristics. A set of elite solutions are used to influence the constructive phase in GRASP. In Tabu Search, diversification and intensification strategies make direct use of the elite solutions, as well of residence frequences. Path relinking between the elite solutions is used as a post-optimization approach
Doutorado
Automação
Doutor em Engenharia Elétrica

Made available in DSpace on 2016-06-02T19:50:09Z (GMT). No. of bitstreams: 1 3195.pdf: 2024810 bytes, checksum: 9ca884455df82d8694112f060501c5fe (MD5) Previous issue date: 2010-08-25
Althought the scheduling-related literature has a high level of diversity, just a small group have been considering the possibility of outsource a set of tasks. During a literature review, only two papers related to this theme were found, both dealing on scheduling projects with outsource possibilities on single-machine environments. Along with this scenario, it was possible to stablish the ACO (Ant Colony Optimization) algorithm as a promissing tecnique to solve combinatorial problems, including scheduling problems. This thesis approaches two scheduling problems with outsourcing allowed: (i) a scheduling problem in single machine manufacturing environment and (ii) a scheduling problem in a flowshop environment. For each problem, a new ACO algorithm is proposed and implemented. To verify the quality of the results, are also proposed and implemented: (i) a mathemetical programming model for the single machine environment problem; (ii) a branch and bound algorithm for the single machine environment problem and (iii) a a mathemetical programming model for the flowshop environment problem. The results shown that both ACO algorithms generate close-to-optimal results in a shorter computational time. In the case of the single machine environment problem, the presented results are best than the results related on the literature.
Embora a literatura de scheduling seja vasta, poucas pesquisas até o momento levam em consideração a possibilidade de terceirização de tarefas. Dentre a literatura pesquisada, apenas dois trabalhos trataram deste problema multicritério, ambos para ambientes de máquina única. Juntamente com isso, uma análise preliminar da literatura p ode estabelecer o algoritmo ACO (do inglês Ant Colony Optimization - Otimização por Colônia de Formigas) como uma estratégia promissora para a solução de problemas combinatórios, incluindo problemas de scheduling. Neste cenário, a presente tese de doutoramento trata de dois problemas de scheduling com possibilidade de terceirização: (i) um problema de scheduling em ambiente de máquina única, já proposto na literatura e (ii) problema inédito de scheduling em ambientes flowshop.Em ambos os casos, são propostos algoritmos ACO inéditos (um para o problema de scheduling em ambientes de máquina única e um para o problema de scheduling em ambientes flowshop), que são comparados com valores ótimos obtidos através de métodos exatos. Para permitir essa comparação, são propostos três métodos exatos: (i) Um modelo de programação matemática para o problema que trata do ambiente de máquina única; (ii) Um algoritmo branch and bound para o mesmo problema e (iii) Um modelo de programação matemática para o problema que trata do ambiente flowshop. Os resultados obtidos no trabalho mostraram que ambos os algoritmos ACO propostos conseguiram respostas próximas ao ótimo. Quando se tratando de problemas de maiores dimensões, o tempo computacional necessário para a execução do algoritmo foi muito menor que o tempo computacional requerido pelos métodos exatos. No caso do problema de scheduling em ambientes de máquina única, ainda pode-se ressaltar que a qualidade dos resultados (em termos de resultados e tempos computacionais) foram melhores que os relatados na literatura pesquisada.

Mestrado em Decisão Económica e Empresarial
O tema deste Trabalho Final de Mestrado (TFM) centra-se na otimização de um escalonamento de pacientes de radioterapia, no contexto do Hospital da Luz, em Lisboa. Este TFM foi desenvolvido sob a forma de um projeto, tendo como principal objetivo maximizar a oferta de tratamentos por dia, minimizando o tempo de inatividade do serviço no seu horário de funcionamento diário. Assim, a fase inicial do projeto consistiu em compreender como funcionava o serviço de radioterapia e aprender algumas noções acerca dos tratamentos que podem ser feitos. Posteriormente, procedeu-se à recolha de dados, que correspondem aos tempos específicos de tratamento de cada paciente, tendo em consideração o tumor a ser tratado e a técnica utilizada. Este estudo foi elaborado tendo como base um escalonamento inicial correspondente aos pacientes em tratamento. Esta afetação é revista semanalmente por forma a planear a semana seguinte. Assim, conhecidos os pacientes que finalizam e os que iniciam tratamento na semana seguinte, pretende-se afetar os vários pacientes às vagas disponíveis. O problema identificado e formulado foi resolvido com recurso ao Solver do Excel. A solução obtida é posteriormente escrita numa folha de Excel com recurso a um programa desenvolvido em VBA.
This Masters' Final Work (MFW) is focused on optimizing a schedule for radiotherapy patients in the context of Hospital da Luz, in Lisbon. My MFW is considered as a project, with the main objective of maximizing the number of treatments per day, while minimizing service idle time within its daily workload. Thus, the initial phase of the project was to understand how the radiotherapy service works and learn about treatments that can be done. Then, it was proceeded to the collection of data, which correspond to specific time of treatment of each patient, taking into account the tumor to be treated and the technique used. This study was based on an initial schedule according to the patients under treatment. The allocation is reviewed on a weekly basis in order to plan the next week. Thus, knowing the patients who complete and those who start treatment in the following week, the aim is to affect the new patients to available places, as much as possible. The identified and formulated problem was solved via Excel Solver. The solution obtained is subsequently written in an Excel spreadsheet using a program developed in VBA.

Made available in DSpace on 2016-06-02T19:52:13Z (GMT). No. of bitstreams: 1 DissJMRB.pdf: 944400 bytes, checksum: b37a0f175baab577681e6785f305edee (MD5) Previous issue date: 2005-06-23
This project consists in the refinement of the tabu search adaptive approach HTSA (PUREZA, 1996) and the analysis of its performance when applied to the classical Vehicle Routing Problem and to the Vehicle Routing Problem with Time Windows. HTSA promotes the integration of intensification and diversification strategies through the systematic variation of the values of selected tabu parameters, mostly based on the analysis of search trajectory patterns. The development of new implementations based on tabu search (GLOVER, 1989; GLOVER & LAGUNA, 1997) is an interesting avenue of research since tabu search has offered new marks on solution quality in routing problems, usually outperforming other methods. The results obtained with the application of HTSA approach to a set of classical routing instances and to a set of routing with times windows instances indicate quality solutions within reasonable computational times when compared to the results provided by competitive methods in the literature.
O corrente projeto tem como objetivo o refinamento da abordagem adaptativa de busca tabu HTSA (PUREZA, 1996) e a verificação de seu desempenho quando aplicada ao Problema de Roteirização de Veículos clássico e ao Problema de Roteirização com Janelas de Tempo. A abordagem HTSA tem como objetivo a integração de estratégias de intensificação e diversificação, consistindo na variação sistemática de valores de parâmetros tabu selecionados e apoiada principalmente na análise de padrões da trajetória da busca. O desenvolvimento de novas abordagens baseadas na meta-heurística busca tabu (GLOVER, 1989; GLOVER & LAGUNA, 1997) é uma linha de pesquisa interessante uma vez que a busca tabu tem oferecido novas marcas em qualidade da solução em problemas de Roteirização de veículos e suas variantes, geralmente superando outros métodos. Os resultados obtidos com a aplicação da abordagem HTSA a instâncias de roteirização de veículos clássicas e com janela de tempo indicam soluções de qualidade em tempos computacionais razoáveis quando comparadas aos resultados de métodos competitivos da literatura.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
The evolution of computer hardware as well as new applications of mathematical programming techniques, efficiently implemented in many commercial solvers, has given rise to new algorithms called hybrid metaheuristic, which have been applied to solve combinatorial problems. This work presents several approaches which try to deal with the hybridization of local search based metaheuristics with exact algorithms to solve two problems of combinatorial optimization. More specifically, the first problem, capacitated p-median problem, the proposed approach considers heuristic elimination of variable of the original mathematical model, that produce solutions of very good quality in a short amount of time, and a combination with an iterative procedure in which only a certain subset of points is considered. As regards the second problem, unrelated parallel machine scheduling with sequence and machine dependent setup time problem of minimizing makespan, is proposed a mathematical model to search the neighborhood of a solution and identify movement sequences to minimize the objective function. In both cases, mathematical models are solved using a commercial solver. Extensive computational experiments are carried out to demonstrate the good performance of the proposed approaches.
A recente evolução dos computadores como também dos métodos exatos oriundos da programação matemática, muitos destes eficientemente implementados em otimizadores comerciais, propiciou o surgimento de novos algoritmos, denominados metaheurísticas híbridas, que têm sido aplicados para resolução de problemas combinatoriais. Este trabalho apresenta abordagens que hibridizam metaheurísticas baseadas em busca local com algoritmos exatos de programação matemática para resolver dois problemas de otimização combinatória. Mais especificamente, para o primeiro problema, o problema das p-medianas capacitado, a proposta considera a eliminação heurística de variáveis do modelo matemático, que permite a obtenção de soluções de boa qualidade em um curto tempo computacional, e a combinação com um procedimento iterativo no qual apenas um determinado subconjunto de pontos é considerado. No que se refere ao segundo problema, programação de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência e da máquina com objetivo de minimizar o tempo de processamento total da máquina com maior carga entre todas (makespan), propõe-se um modelo matemático para varrer a vizinhança de uma solução e identificar sequências de movimentos de tarefas que podem ser aplicadas na respectiva solução de modo a minimizar a função objetivo. Nos dois casos os modelos matemáticos são resolvidos utilizando um otimizador comercial. Extensivos testes computacionais são realizados para demonstrar o bom desempenho das abordagens propostas.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2018-05-25T13:02:54Z No. of bitstreams: 1 guilhermedesouzaferreira.pdf: 1163831 bytes, checksum: ec0bec904b2e6110d9b9e4934727f35d (MD5)
Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-06-14T11:52:03Z (GMT) No. of bitstreams: 1 guilhermedesouzaferreira.pdf: 1163831 bytes, checksum: ec0bec904b2e6110d9b9e4934727f35d (MD5)
Made available in DSpace on 2018-06-14T11:52:03Z (GMT). No. of bitstreams: 1 guilhermedesouzaferreira.pdf: 1163831 bytes, checksum: ec0bec904b2e6110d9b9e4934727f35d (MD5) Previous issue date: 2018-02-22
CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
O escalonamento de tarefas é um problema de otimização combinatória no qual tenta-se sequenciar da melhor maneira os trabalhos a serem realizados em processos de produção. O intuito neste caso é atingir os objetivos de desempenho estipulados pelo tomador de decisão, tais como, minimizar o makespan e minimizar o atraso total. O Problema de Sequencia-mento do tipo Job-Shop Flexível (FJSP) pertence a essa categoria, e caracteriza-se pela possibilidade de haver rotas tecnológicas diferentes para as tarefas e cada estágio poder ser composto por mais de uma máquina. Esse é o núcleo da tecnologia do gerenciamento de produção, pois sequenciamentos melhores podem encurtar o tempo de manufatura, reduzir os níveis de estoque, possibilitar a entrega de encomendas no tempo correto e aumentar a credibilidade dos processos e da empresa. Métodos exatos, que são computacionalmente custosos, são geralmente aplicados nos problemas de sequenciamento menores, portanto quando os problemas aumentam em tamanho, os métodos heurísticos e metaheurísticos começaram a ser aplicados. As metaheurísticas são importantes para solucionar FJSPs porque são mais rápidas do que os métodos exatos. Dentre elas, os Algoritmos Genéti-cos (AGs) estão entre as técnicas mais utilizadas para solucionar FJSPs e, atualmente, modelos híbridos vem sendo explorados, combinando AGs com técnicas de busca local e heurísticas para inicializar a população. No entanto, a escolha adequada dos parâmetros dos AGs é um trabalho difícil, recaindo num outro problema de otimização. Os Algoritmos Genéticos Adaptativos (AGAs) foram introduzidos para lidar com essa adversidade, uma vez que podem ajustar os parâmetros dos AGs durante o processo de busca. Portanto, o objetivo da presente dissertação é analisar diferentes técnicas adaptativas desenvolvidas para AGAs, com o intuito de reduzir o tempo de configuração dos AGs quando aplicados a FJSPs. Além disso, serão propostas alterações para as técnicas de atribuição de crédito e de seleção de operadores. Os estudos foram realizados em instâncias de diferentes tamanhos e os AGAs são comparados com AGs tradicionais. Duas diferentes análises foram realizadas baseadas em cenários no qual o tomador de decisão tem pouco tempo para configurar os algoritmos. Na Análise I, os AGAs tiveram desempenho semelhante aos AGs tradicionais, mas são interessantes por possuírem um menor número de parâmetros e, consequentemente, um menor tempo de configuração. Na Análise II, os AGAs geraram melhores resultados do que aqueles obtidos pelos AGs, o que os tornam apropriados para o caso em que há incerteza no processo produtivo e menor tempo de configuração.
Scheduling is a combinatorial optimization problem, in which one tries ordering the tasks to be performed in the processing units. The objective is to achieve the best values with respect to the performance indicators chosen by the decision-maker, such as, minimize the makespan and minimize the total lateness. The Flexible Job-Shop Scheduling Problem (FJSP) belongs to this category, and its characteristics are the different technological routes for the tasks and that each stage may consist of more than one machine. This is the technological core of the production management, as better schedules may reduce the manufacturing time, reduce the inventory, deliver the order in the right time, and raise the reliability of the process and the company. Exact methods, as they are computationally expensive, are usually employed for small scheduling problems, then heuristic and metaheuristic methods become interesting techniques for this type of problem. Metaheuristics are important to solve FJSPs as they are faster than the exact methods, and among then, Genetic Algorithms (GAs) are one of the most used techniques to solve FJSPs and, currently, they have been hybridized with local search and heuristics to initialize their population. However, to set up GAs is a hard-work and often generates another optimization problem. Adaptive Genetic Algorithms (AGAs) were introduced to work around this problem as they adapt the parameters of the GAs during the search process. Therefore, the objective of this dissertation is to analyze different adaptive techniques developed for AGAs with the purpose of reducing the setup time of GAs when they are applied to FJSPs. In addition, modifications will be proposed for the operator selection techniques and for credit assignment schemes. The studies were performed in instances of different sizes, and the AGAs are compared with traditional GAs. Two different analyzes were performed based on scenarios in which the decision maker does not has to much time to configure the algorithms. In Analysis I, some AGAs performed similarly to the traditional GAs, but they are more interesting as they have a smaller number of parameters, thus a shorter configuration time. In Analysis II, some AGAsgeneratedbetterresultsthanthoseobtainedbyGAs, whichmakesthemappropriate for the case when there is uncertainty in the production process and the decision maker does not have too much time to configure the algorithm.

Orientador: Prof. Dr. Cláudio Nogueira de Meneses
Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2016.
A confecção da escala de trabalho, ou escala de folga, para os profssionais de enfermagem, conhecido pela comunidade academica como Nurse Scheduling Problem (NSP) ou Nurse Rostering Problem (NRP), é um problema administrativo, que precisa ser resolvido frequentemente nas instituições de saúde (Unidade Basica de Saude (UBS), Unidade de Pronto Atendimento (UPA), hospitais, clínicas etc.) onde esses profssionais atuam. Ela é uma tarefa relativamente complexa, realizada frequentemente de maneira manual, que consome muito tempo dos profssionais que a executam e nem sempre produzindo um resultado com a qualidade desejada. Nesta dissertação, este problema é apresentado considerando as leis trabalhistas brasileiras, resoluções dos conselhos federais e regionais de enfermagem, convenções coletivas de trabalho dos sindicatos de classe e políticas dos centros de saúde para os profissionais de enfermagem. Para tentar resolver esse difícil problema de otimização, propomos um modelo em programação linear inteira, observando as restrições (fortes e fracas) impostas pelas diversas entidades reguladoras da atividade desses profissionais. Com esse modelo e a utilização de um software disponívell no mercado foi possível resolver (em poucos segundos) de maneira ótima, algumas instâncias reais do problema. Esta dissertação demonstra a capacidade de se resolver instâncias reais desse problema para a realidade das instituições de saúde brasileiras e, em especifico da Regi~ ao do Grande ABC em São Paulo, que abrange os municípios de Santo André, São Bernado do Campo, São Caetano do Sul, Diadema, Maua, Ribeirão Pires e Rio Grande da Serra (ABCDMRR), utilizando esse modelo matemático proporcionando soluções com qualidades iguais ou superiores àquelas obtidas por meio de escalas manuais.
The work or rest time table to the health professionals, known by the academic comunity as the NSP or NRP, is an administrative problem that needs to be solved often in health institutions (hospitals, clinics, emergency hospitals etc.) where these professionals work. It is a complex task, often carried out in a manual way, time-consuming by professionals that perform it and does not always produce a result with the desired quality. In this work, this problem is presented considering the Brazilian labor laws, resolutions of federal and regional councils of nursing, collective labor agreements of trade unions and health centers policies for nursing professionals. To try to resolve this dificult optimization problem, we propose in this work a model in Integer Linear programming, observing the restrictions (hard and soft) imposed by the various regulators of the activity of these professionals. This model is solved by IBM ILOG CPLEX solver which, if any, an optimal solution to the problem. This work demonstrates the ability to solve real instances of this problem to the reality of Brazilian health institutions, and in particular the Região do Grande ABC in São Paulo, covering the cities of Santo André, São Bernado do Campo, São Caetano do Sul, Diadema, Mauá, Ribeirão Pires and Rio Grande da Serra (ABCDMRR), using this mathematical model and solving arrangement in a reasonable time and with quality equal or superior to that obtained with manual scales.

Submitted by Maike Costa (maiksebas@gmail.com) on 2016-04-27T14:06:26Z No. of bitstreams: 1 arquivo total.pdf: 1831708 bytes, checksum: edf5d3b8c2b5483f249063f565ba3024 (MD5)
Made available in DSpace on 2016-04-27T14:06:26Z (GMT). No. of bitstreams: 1 arquivo total.pdf: 1831708 bytes, checksum: edf5d3b8c2b5483f249063f565ba3024 (MD5) Previous issue date: 2015-04-14
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES
This work proposes a uni ed heuristic algorithm for a large class of earlinesstardiness (E-T) scheduling problems. We consider single/parallel machine E-T problems that may or may not consider some additional features such as idle time, setup times and release dates. In addition, we also consider those problems whose objective is to minimize either the total (average) weighted completion time or the total (average) weighted ow time, which arise as particular cases when the due dates of all jobs are either set to zero or to their associated release dates, respectively. The developed local search based metaheuristic framework is quite simple, but at the same time relies on sophisticated procedures for e ciently performing local search according to the characteristics of the problem. The algorithm was tested in hundreds of instances of several E-T problems and particular cases. The results obtained show that our general heuristic is capable of producing high quality solutions when compared to the best ones available in the literature that were obtained by speci c methods. Moreover, the algorithm was tested on a new set of instances proposed for the most general case (Rjrj ; sk ij jPw0j Ej + wjTj) of the class of problems considered, in order to validate the method.
Esta disserta c~ao prop~oe uma heur stica uni cada para uma classe de problemas de sequenciamento da produ c~ao com penalidades por antecipa c~ao e atraso. S~ao considerados problemas que envolvem uma ou m ultiplas m aquinas e que podem, ou n~ao, considerar algumas particularidades, tais como: a inser c~ao de tempos ociosos entre as tarefas, tempos de setup e datas de libera c~ao distintas. Al em desses problemas, tamb em s~ao considerados os em que a fun c~ao objetivo e de minimizar tanto o a soma (ponderada) dos tempos de t ermino das tarefas, quanto a soma (ponderada) dos tempos de uxo das tarefas, que surgem como casos particulares quando as datas de entrega de todas as tarefas s~ao de nidas com zero ou iguais a suas respectivas datas de libera c~ao, respectivamente. A meta-heur stica baseada em busca local proposta e simples, mas cont em procedimentos so sticados que possibilitam uma execu c~ao e ciente da busca local, de acordo com as caracter sticas do problema. O algoritmo foi testado em centenas de inst^ancias de problemas envolvendo penalidades por antecipa c~ao e atraso e em casos particulares. Os resultados obtidos mostram que a heur stica proposta e capaz de produzir solu c~oes de alta qualidade quando comparadas com os melhores dispon veis na literatura, os quais foram obtidos por m etodos espec cos. Al em disso, o algoritmo foi testado em um novo conjunto de inst^ancias propostas para caso mais geral (Rjrj ; sk ij jPw0j Ej +wjTj) da classe de problemas considerados, com o intuito de validar o m etodo.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
Problems of scheduling on batch processing machines to minimize makespan are widely exploited by academic literature, mainly motivated by reliability testing in the semiconductor industry. These problems consist in grouping jobs as a batch and scheduling the processing in single or parallel machines. The jobs have non-identical processing times and non-identical sizes and the total size of the batch cannot exceed the machine capacity. The processing time of a batch is given by the longest processing time of any job in the batch. Jobs with nonidentical release times can also be considered, and in this case a batch can only be processed after the job with the longest release time in the batch is available. We consider four different problems of scheduling on batch processing machines with non-identical job size and different characteristics: single batch processing machine (1|sj,B|Cmax), single batch processing machine with non-identical job release times (1|rj,sj,B|Cmax), identical parallel batch processing machines (Pm|sj,B|Cmax), and identical parallel batch processing machines with non-identical job release times (Pm|rj,sj,B|Cmax). New mathematical models are proposed with formulations that exploit characteristics of each problem. The mathematical models are solved using CPLEX and the computational results show that the proposed models performed better than other models from literature. The new models for 1|sj,B|Cmax and 1|rj,sj,B|Cmax are compared with previously published meta-heuristics and the results show that the models provide better solutions than meta-heuristics methods with competitive computational times.
Problemas de minimização do makespan no dimensionamento e programação de bateladas em máquinas de processamento são extensamente explorados pela literatura acadêmica, motivados principalmente por testes de confiabilidade na indústria de semicondutores. Estes problemas consistem em agrupar tarefas em bateladas e programar o processamento em uma ou mais máquinas em paralelo. As tarefas possuem tempos de processamento e tamanhos não idênticos e o tamanho total da batelada não pode exceder a capacidade da máquina. Para cada batelada é definido um tempo de processamento que será igual ao maior tempo de processamento das tarefas que foram alocadas a ela. As tarefas podem considerar também tarefas com tempos de liberação não idênticos, neste caso as bateladas só poderão ser processadas depois que a tarefa com o maior tempo de liberação for disponibilizada. Este trabalho aborda quatro diferentes problemas de dimensionamento e programação de bateladas com tarefas de tamanhos não idênticos, que consideram diferentes características: máquina de processamento única (1|sj,B|Cmax), máquina de processamento única e tarefas com tempos de liberação não idênticos (1|rj,sj,B|Cmax), máquinas de processamento paralelas idênticas (Pm|sj,B|Cmax) e máquinas de processamento paralelas idênticas e tarefas com tempos de liberação não idênticos (Pm|rj,sj,B|Cmax). São propostos novos modelos matemáticos com formulações que exploram características de cada problema. Os modelos matemáticos são resolvidos utilizando CPLEX e os resultados computacionais comprovam que os modelos propostos possuem um desempenho melhor do que outros modelos da literatura. Os modelos propostos para 1|sj,B|Cmax e 1|rj,sj,B|Cmax são comparados com meta-heurísticas previamente publicadas e os resultados mostram que os novos modelos oferecem soluções melhores com tempos computacionais competitivos.

O Problema de Escalonamento de Médicos (Physician Scheduling Problem) consiste em atribuir tarefas a médicos num horizonte de planejamento respeitando regras laborais, contratuais e de preferências pessoais de modo a satisfazer a demanda de serviços de um hospital. O problema lida majoritariamente com o objetivo de maximizar o atendimento dos requisitos de preferência pessoal, respeitando as restrições laborais e organizacionais. Sobre esta classe de problemas, vários métodos de resolução e suas variantes têm sido propostos na literatura. Ademais, mais características têm sido agregadas ao problema, tornando-o mais complexo e deste modo fazendo-se mais necessária a aplicação de métodos mais elaborados para a sua resolução. Neste trabalho são estudados, reformulados e propostos métodos de resolução baseados em programação matemática para tratar o problema de escalonamento acíclico de médicos em departamento de emergência de hospitais. O primeiro modelo tem como objetivo a minimização da soma ponderada dos desvios das restrições de distribuição. O segundo modelo tem como objetivo, a minimização do máximo dos desvios obtidos nas restrições de distribuição, a fim de se obter escalas mais equilibradas entre os médicos. Foram também propostas heurísticas baseadas na formulação matemática cujos resultados não foram competitivos com as dos modelos. Os modelos foram testados sobre um conjunto de instâncias fictícias resultantes de uma mescla entre instâncias benchmark e características do problema. Os resultados computacionais demonstram que formulação ponderada obteve solução ótima para grande parte das instâncias, embora os limitantes inferiores tenham sido majoritariamente fracos. Em relação ao segundo modelo, soluções ótimas não foram obtidas e os limitantes inferiores foram igualmente fracos. Relativamente a qualidade das escalas, o segundo modelo teve melhor comportamento comparando ao modelo de somas ponderadas. Dada a qualidade das soluções, nota-se a viabilidade da solução baseada em técnicas de otimização em detrimento da manual, pois esta ainda é mais suscetível de erros e acarreta um alto tempo para obtenção de solução.
The Physician Scheduling Problem consists in task assignment to physicians in a planning horizon considering a set of organizational rules, work regulations and individual preferences in order to satisfy an hospital wards work demand. The aim is to find a schedule which maximizes the satisfaction of individual preferences requirements while meeting work regulations and organizational rules. A plethora of solution methods and its variants have been proposed in the literature to solve this class of problem. Moreover, more features have been aggregated to the problem turning it into a more complex and thus estimulating the application of more elaborated methods to its decision. In this work we study, reshape and propose decision methods based in mathematical programming to handle non-ciclic physician scheduling problem in emergency wards. The first formulation targets the minimization of the weighted sum of distribution constraints deviations. The second formulation targets the minimization of the maximum deviations obtained at the distribution constraints aiming more balanced schedules between the physicians. Mathematical formulation heuristics were also proposed and the findings were not satisfactory as they were not competitive with the model. Experiments with our models were performed over a set of dummy instances, as result a of a mixture of benchmark instances and the considered problems features. From our experiments we have found that optimal solutions were obtained through the weighted sum model, despite the poor lower bounds. On the other hand, for the second model, no optimal solution was found and poor lower bounds were similarly obtained. Regarding to the schedules quality, the min-max model had a better performance comparing to the weighted sum model. Given the solutions quality we can assume that optimization based techniques are sustainable comparing to manual, because the latter is prone to errors and omissions and also critical in terms of solutions achievement time.

The group scheduling problem commonly arises in cellular manufacturing systems, where parts are grouped into part families. It is characterized by a sequencing task on two levels: on the one hand, a sequence of jobs within each part family has to be identified while, on the other hand, a family sequence has to be determined. In order to solve this NP-hard problem usually heuristic solution approaches are used. In this thesis different aspects of group scheduling are discussed and problem specific heuristics are developed to solve group scheduling problems efficiently. Thereby, particularly characteristic properties of flowshop group scheduling problems, such as the structure of a group schedule or missing operations, are identified and exploited. In a simulation study for job shop manufacturing cells several novel dispatching rules are analyzed. Furthermore, a comprehensive review of the existing group scheduling literature is presented, identifying fruitful directions for future research.

Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-08-30T12:26:40Z No. of bitstreams: 1 DissMSV.pdf: 2771156 bytes, checksum: add74067c9db203edececa7202e83a52 (MD5)
Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-09-20T14:06:15Z (GMT) No. of bitstreams: 1 DissMSV.pdf: 2771156 bytes, checksum: add74067c9db203edececa7202e83a52 (MD5)
Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-09-20T14:06:22Z (GMT) No. of bitstreams: 1 DissMSV.pdf: 2771156 bytes, checksum: add74067c9db203edececa7202e83a52 (MD5)
Made available in DSpace on 2017-09-20T14:11:11Z (GMT). No. of bitstreams: 1 DissMSV.pdf: 2771156 bytes, checksum: add74067c9db203edececa7202e83a52 (MD5) Previous issue date: 2016-08-29
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
In recent years, several studies have been carried out to minimize the production time (makespan) in a production schedule of a scenario that represents a manufacturing system. The problem of production scheduling is classified as a combinatorial problem belongs to the NP-hard class of computational problems. Furthermore, in a real world production system, there are many unexpected events (eg, review of production, entry of new products, breaking machines, etc.). To deal with the interruptions of the initial programming, we need to change any settings, which is called reactive production schedule or, simply, reactive scheduling. As a problem of combinatorial features, meta-heuristics is widely used in its resolution. This paper proposes a method that uses an evolutionary meta-heuristic Genetic Algorithm in conjunction with an operator called “Transgenics”, which allows to manipulate the genetic material of individuals adding features which are believed to be important, with the proposal to direct some population of individuals to a more favorable solution to the problem without removing the diversity of the population with a lower cost of time. The objective of this study is to use the Genetic Algorithm with transgenics operator obtain a reactive programming acceptable response time to minimize the makespan value. The objective of this study is to use the Genetic Algorithm with transgenics Operator obtain a reactive programming acceptable response time to minimize the makespan value. Experimental results show the proposed algorithm is able to bring better results than the makespan algorithm and compared in a shorter processing time due to the search direction which provides transgenic operator.
Nos últimos anos, várias pesquisas vêm sendo realizadas a fim de minimizar o tempo total de produção (makespan) em uma programação da produção de algum cenário que representa um sistema de manufatura. O problema da programação da produção é classificado como sendo um problema combinatório pertencente à classe NP-Hard dos problemas computacionais. Além disso, em um sistema de produção real, há muitos eventos inesperados (por exemplo, a revisão da produção, chegada de novos produtos, quebra máquinas, etc.). Para lidar com as interrupções da programação inicial, é preciso realizar outra programação, a qual é denominada de programação reativa da produção. Sendo um problema de recursos combinatórios, é amplamente utilizado metaheurísticas em sua resolução. Neste trabalho é proposto um método que faz uso de uma metaheurística evolutiva Algoritmo Genético em conjunto com um operador intitulado Operador de Transgenia, no qual possibilita manipular o material genético dos indivíduos acrescentando características das quais se acredita serem importantes, com a proposta de direcionar alguns indivíduos da população para uma solução mais favorável para o problema sem tirar a diversidade da população com um custo menor de tempo. O Objetivo deste trabalho é utilizando o Algoritmo Genético com Operador de Transgenia obter uma programação reativa em tempo de resposta aceitável, visando minimizar o valor de makespan. Resultados experimentais mostraram que algoritmo proposto foi capaz de trazer resultados de makespan melhores que os algoritmos comparados e em um menor tempo de processamento, devido ao direcionamento na busca que operador de transgenia proporciona.

Mestrado em Decisão Económica e Empresarial
No processo produtivo de uma indústria de fitofarmacêuticos deparamo-nos com problemas no sequenciamento e afetação de tarefas necessárias a encomendas. Este estudo destina-se à fábrica da maior multinacional portuguesa no ramo dos agro-químicos. A SAPEC Agro aposta numa estratégia vencedora no negócio agrícola e, neste ramo, a competição não é entre empresas, mas sim entre as cadeias de abastecimento. Com o crescimento da empresa e a sua internacionalização, inserida num ambiente altamente competitivo, torna-se fundamental automatizar o processo de planeamento da produção, que até aos dias de hoje tem sido feito por um engenheiro industrial. O presente estudo tem como objetivo encontrar um sequenciamento de tarefas (scheduling), ou seja, determinar uma afetação ótima das tarefas às máquinas, minimizando o tempo de execução total (makespan). Este tipo de problema é um clássico da literatura e é conhecido como um problema de job-shop scheduling com uma sequência dependente de tempos de setup (JSP-SDST). Um JSP-SDST apresenta, uma complexidade NP-difícil. Sendo um problema de difícil otimização, constituiu, assim, um desfio nas áreas da Investigação Operacional e Ciência da Computação. A abordagem escolhida passou primeiramente por definir o espaço de soluções admissíveis (S.A.) e neste encontrar uma solução ótima (sob determinadas condições), através do algoritmo Branch-and-Bound, recorrendo-se particularmente ao tipo de pesquisa Depth First Search (B&B-DFS) no espaço das soluções admissíveis. Neste estudo são apresentados outros tipos de pesquisa, também baseados em B&B, por forma a avaliá-los. Foi desenvolvida uma interface gráfica centrada no utilizador para que este possa usufruir do presente estudo, sem ter de lidar com a complexidade envolvida. A interface gráfica implementada é viável e, em articulação com os procedimentos de otimização escolhidos, constitui uma mais-valia para a organização, esperando-se que possa vir a ser instrumento de trabalho futuro.
The production process in the plant protection industry, as in many other industries, faces very often problems on how to schedule tasks that need to be completed in order to respond to a given set of orders. This study is made for the largest Portuguese multinational company in the agro-chemicals business, SAPEC Agro. SAPEC Agro relies on a winning strategy on this business, a business where competition is made between supply chains instead of companies. To follow the company’s growth and its continuous internationalization process, inserted in a highly competitive environment, this project aims to maximize the automation and optimize the production planning, which is now made by an Industrial Engineer. This study’s main goal is to develop an algorithm that will be able to find the optimal solution (under certain constraints) for the scheduling of tasks in the production process. That means determining the best possible sequence of tasks to each machine in order to minimize the total makespan. This type of problem is classic in the literature, and it is known as a Job-Shop Scheduling Problem with Sequence Dependent Setup Times (JSP-SDST). The resolution of the JSP-SDST is difficult, as in terms of computational complexity it is considered an NP-Hard problem, thus being a challenge in the areas of Operations Research and Computer Science. As the problem is applied in an industrial environment, the scheduling is useful if the algorithms respond in a reasonable amount of time, allowing the production managers to get real-time support when decisions need to be taken. The chosen approach was first to define an admissible solution space (some constraints to the allocations were applied), and then to find the optimum through a Branch-and-Bound method which uses a Depth-First-Search as method of search in the solution space. Other search methods and heuristics, also based on Branch-and-Bound are applied as well, in order to meet the time complexity constraints. A graphical interface is developed allowing its use even by those unfamiliar with the complexity of the problem. Users need just to include the inputs (orders and quantities of each product) and the program generates a schedule for the input orders. This work’s main goal is the development of a program that would be useful and would add value to the organization in study, the SAPEC Agro.

Submitted by Elton Lever (elton@icomp.ufam.edu.br) on 2018-08-23T20:26:01Z No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5)
Approved for entry into archive by Secretaria PPGI (secretariappgi@icomp.ufam.edu.br) on 2018-08-23T20:35:20Z (GMT) No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5)
Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-08-24T13:35:27Z (GMT) No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5)
Made available in DSpace on 2018-08-24T13:35:28Z (GMT). No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) Previous issue date: 2017-06-22
CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
This dissertation addresses the class of job scheduling problems with precedence constraints and unit execution times, in identical parallel processors. Such a class of problems is of great importance in computational complexity theory, since small varia- tions in the conditions involved in scheduling make an easy problem very difficult. Two major problems involve the condition of the number of processors, where, if the number of processors is variable, given as input, such problem is proved to be NP-complete, but if the number of processors is fixed, the problem is still open. In this context, the focus of the research involves the problem already proven to be NP-complete, where for which we investigated the main approximation algorithms in the literature and their proofs of approximation ratio of the optimal, such as of the Garey & Jonhson’s 2-approximation algorithm, of the Hu, of the Coffman & Graham, and of the Gangal & Ranade with 2 − (7/(3P + 1)), the best approximation ratio in the literature. The approximation ratio proofs of such algorithms were detailed. As the main contribution of this research, were proved the optimality for specific classes of acyclic directed graphs involving trees (prece- dence trees, such as in-tree and out-tree) for the best approximation algorithms literature.
Esta dissertação aborda a classe de problemas de escalonamento de tarefas com restrições de precedências e tempos unitários em processadores paralelos idênticos. Tal classe de problemas tem uma grande importância em teoria da complexidade computacional, uma vez que pequenas variações nas condições envolvidas no esca- lonamento, fazem com que um problema fácil se torne muito difícil. Dois grandes problemas envolvem a condição do número de processadores, onde, se o número de processadores for variável, dado como entrada, tal problema é provado ser NP-completo, mas, se o número de processadores for fixo, o problema ainda está em aberto. Neste contexto, o foco da pesquisa envolve o problema já provado ser NP-completo, onde para qual se investigou os principais algoritmos aproximativos existentes na literatura e suas provas de razão de aproximação do ótimo, tais como o algoritmo 2-aproximativo de Garey & Jonhson e as melhorias de Hu, Coffman & Graham e de Gangal & Ranade (GR) com 2 −(7/(3P+1)), o de melhor razão de aproximação da literatura. As provas de razão de aproximação de tais algoritmos foram detalhadas. Como principal contribuição da pesquisa, foram determinados casos especiais ótimos, para classes específicas de grafos direcionados acíclicos que envolvem arborescências (árvores de precedência, como in-tree e out-tree) para o melhor algoritmos aproximativo da literatura.
Compreender o que querem em alguns momentos.

Existem vários problemas clássicos na área de pesquisa operacional que trabalham com o tema vinculado à designação de veículos em um sistema logístico, entre eles o Problema de Escalonamento de Veículos com Múltiplas Garagens (MDVSP). Esses modelos são largamente utilizados e representam uma das etapas essenciais para o planejamento de trânsito em massa (HAGHANI e BANIHASHEMI, 2002). Tratando-se de sistemas logísticos reais, dificilmente encontra-se um ambiente onde os veículos devem partir e chegar a uma única garagem, por isso torna-se necessário o planejamento das seqüências de viagens de modo a reduzir os custos de deslocamentos com o aproveitamento das múltiplas garagens distribuídas geograficamente. Infelizmente, considerando a complexidade exponencial do MDVSP, muitas vezes sua aplicação torna-se inviável na solução de problemas reais. Por essa razão, poucos trabalhos abordam o MDVSP de modo a conseguir solucionar o problema para uma grande quantidade de viagens e garagens. A maioria das pesquisas trabalha com instâncias inferiores a 500 viagens e quatro garagens, mostrando-se pouco aplicáveis. Esse estudo refere-se a um trabalho de pesquisa operacional que aborda soluções de problemas de escalonamento de veículos com múltiplas garagens (MDVSP) considerando sua aplicabilidade em sistemas reais. Tendo em vista a complexidade exponencial do MDVSP, nesse estudo optou-se por tratar o problema através de uma abordagem baseada na redução do espaço de estados e na utilização de heurísticas. Durante essa pesquisa três procedimentos de redução do espaço de estados foram adotados. Os resultados apontam que é possível reduzir em até 98% o número de variáveis nesses problemas sem comprometer uma solução satisfatória ou ótima. Além dos procedimentos de redução do espaço de estados, foi desenvolvido um procedimento de buscar a solução do MDVSP. Através desse último procedimento foi possível resolver o MDVSP com até 3000 viagens e oito garagens. Sendo assim, nesse estudo desenvolveram-se modelos que servem para o planejamento de um sistema logístico através da aplicação de cenários, com vistas a permitir a geração e análise de alternativas de escalonamento. Objetivou-se com isso, fornecer ao sistema logístico um modelo amplo que permita a escolha da ação mais conveniente e eficiente a ser tomada em modelos compostos por diversas garagens.
There are many classics problems in operations research concerning optimal assignment vehicles in logistical system. The multiple depot vehicle scheduling problem (MDVSP) is one of them. This problem is largely used to represent and solve mass transit planning (HAGHANI e BANIHASHEMI, 2002). Considering a real logistical system, it is very difficult to find out a situation where the vehicles must leave and come to only one depot. In general, the shipping company has several depots located at different sites in a network. In this way, it is strongly necessary to reduce cost through the planning of sequence trips taking into account multiple depots geographically distributed. Unfortunately, the exponential complexity of the MDVSP reduces, in the most cases, the applicability of this problem in the real world. For this reason, few researchers address the MDVSP to solve real world problems considering a large number of trips and depots. The majority of the research dealing with the MDVSP works with instances lower than 500 trips and four depots, what can be considered a major constraint for its practical use. The main objective of this work is to solve the MDVSP for very large instances. A state space reduction approach combined with heuristic procedures are developed to obtain a realistic way of solving this complex problem. In this research, three state space reduction procedures were developed. The results appointed that is possible to reduce until 98% of variables in the MDVSP without jeopardizing an optimal solution. Furthermore, heuristic procedures were developed to obtain solutions without relaxing any realworld constraint of the problem. The solution procedure developed was compared with wellknown available instances. The method is able to solve the MDVSP with 3000 trips and eight depots in less than 11 minutes. Although the solution process does not obtain the best solution in all tested instances, it is by far the quickest.

Made available in DSpace on 2015-04-11T14:02:41Z (GMT). No. of bitstreams: 1 rainer.pdf: 3537323 bytes, checksum: 46bd81628ce774393ea9334f7287a55f (MD5) Previous issue date: 2013-03-27
CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
This dissertation presents a study on scheduling problems with earliness and tardiness penalties on identical parallel machines, considering independent and weighted jobs with arbitrary processing times. An analysis of the major mathematical formulations in integer programming is given, and presented the main results from the literature. An integer mathematical formulation based on network flow model was also proposed for the problem, which can be applied on single and parallel machines without idle time. Exact methods of implicit enumeration were studied and applied for the problem through the integer linear programming solver CPLEX and the UFFLP library and, mainly, algorithmic strategies of global optimization based on local search heuristic and path-relinking technique were developed. The computational experiments shows that the proposed algorithmic strategies are competitive in relation to existing results from the literature for single-machine scheduling, involving instances based on OR-Library benchmark for 40, 50, 100, 150, 200 and 300 jobs, where all the optimal values were found, and, mainly, being the best algorithmic strategy for multiprocessor environments, involving 2, 4 and 10 identical parallel machines.
Esta dissertação apresenta um estudo sobre problemas de escalonamento com penalidades de antecipação e atraso em máquinas paralelas, considerando tarefas independentes, ponderadas e de tempos de execução arbitrários. Uma análise sobre as principais formulações matemáticas em programação inteira é dada, bem como apresentados os principais resultados da literatura. Uma formulação matemática de programação inteira baseada no modelo de fluxo em redes também foi proposta para o problema, que pode ser aplicada em ambientes mono e multiprocessado sem tempo ocioso. Métodos de enumeração implícita foram estudados e aplicados aos problemas em questão através do resolvedor de programação linear inteira CPLEX e da biblioteca UFFLP, principalmente, estratégias algorítmicas aproximadas de otimização global baseadas em heurísticas de busca local e técnica de reconexão de caminhos foram desenvolvidas. Os experimentos computacionais mostram que as estratégias propostas são competitivas em relação aos resultados existentes na literatura para ambientes de escalonamento monoprocessados, envolvendo instâncias baseadas no benchmark da OR-Library para 40, 50, 100, 150, 200 e 300 tarefas, onde todos os ótimos foram encontrados, e, principalmente, sendo a melhor estratégia apresentada para ambientes multiprocessados, envolvendo 2, 4 e 10 máquinas paralelas idênticas.

This thesis is concerned with the Resident Scheduling Problem (RSP) in which a good schedule is desired that will meet both departmental requirements and residents' preferences. Three scenarios that represent most situations and account for various departmental requirements and needs are described. Although similar scheduling problems are considered in the literature, no analysis exists that adequately deals with this specific problem. The problem is modeled as a mixed-integer program (MIP) and heuristic solution procedures are developed for the different identified scheduling scenarios. These procedures exploit the network structure of the problem which is an important feature that enhances problem solvability. For the sake of comparison, the problem is also solved exactly via the CPLEX-MIP package. The contribution of this work is important since many hospitals are still utilizing manual techniques in preparing their own schedules, expending considerable effort and time with less scheduling flexibility.
Master of Science

A column generation based approach is proposed to solve scheduling problems for fractional airlines efficiently and return near optimal schedules. Crew tours are building blocks of our approach, and our approach is focused on exploring more feasible tours than other approaches. In particular, all elements of a crew tour are optimized during the preparation and tour generation procedures. Moreover, time windows of customer-requested flights are handled exactly, and generalized to time window and crew time window of duties and tours. Furthermore, time windows of tours are contained in the MIP formulation to ensure more feasible connections between tours. In the pricing subproblem, an efficient constrained shortest path algorithm is proposed, which is necessary for our model and also provides extensibility for incorporating more complex constraints in the future. Computational results of our model show very small optimality gaps and consistent improvements over the model used in practice. Moreover, restricted versions of our model that have fast running time are provided, thus very desired in the case that running time has more priority than solution quality. In order to understand the demand, data mining of demand data is presented and analyzed. Moreover, a recovery model is proposed to deal with unscheduled maintenance in practice, by reserving airplanes and crews in the model. Computational experiments show the advantage of the recovery model, in the case of simulated unscheduled maintenance and comparing to models without recovery considerations.

Submitted by Victor Mario Noble Ramos (vicmanr90@gmail.com) on 2017-12-01T18:27:41Z No. of bitstreams: 2 TextoFinalDissertationVicman-PosDefesa.pdf: 37720288 bytes, checksum: e8e3336733bc8151bd42eab9118f2b2a (MD5) CartaTextoFinal.pdf: 241030 bytes, checksum: 8c46be374e02fb08ecd2b0f6ac30a27b (MD5)
Approved for entry into archive by Milena Rubi ( ri.bso@ufscar.br) on 2017-12-04T12:40:00Z (GMT) No. of bitstreams: 2 TextoFinalDissertationVicman-PosDefesa.pdf: 37720288 bytes, checksum: e8e3336733bc8151bd42eab9118f2b2a (MD5) CartaTextoFinal.pdf: 241030 bytes, checksum: 8c46be374e02fb08ecd2b0f6ac30a27b (MD5)
Approved for entry into archive by Milena Rubi ( ri.bso@ufscar.br) on 2017-12-04T12:40:12Z (GMT) No. of bitstreams: 2 TextoFinalDissertationVicman-PosDefesa.pdf: 37720288 bytes, checksum: e8e3336733bc8151bd42eab9118f2b2a (MD5) CartaTextoFinal.pdf: 241030 bytes, checksum: 8c46be374e02fb08ecd2b0f6ac30a27b (MD5)
Made available in DSpace on 2017-12-04T12:40:54Z (GMT). No. of bitstreams: 2 TextoFinalDissertationVicman-PosDefesa.pdf: 37720288 bytes, checksum: e8e3336733bc8151bd42eab9118f2b2a (MD5) CartaTextoFinal.pdf: 241030 bytes, checksum: 8c46be374e02fb08ecd2b0f6ac30a27b (MD5) Previous issue date: 2017-11-24
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
This dissertation adresses the general integrated lot sizing and scheduling problem for non-alcoholic beverage production with synchronization between stages and operating time windows for scheduling preventive maintenances. The problem is characterized by having two interdependent synchronized stages. In the first stage, machines (tanks) can supply several filling lines at the same time in the second stage, where the final items are packed. Production sequence-dependent times and costs exist. The review of the related literature indicates that existing models refer, generally, to particular cases of the general problem adressed here, the most common cases are the dedication of tanks to the lines, and disregarding the perishability of syrups and the possibility of scheduling preventive maintenances. A mathematical model for the general problem, called SMMRPM, has been proposed and applied in several instances to show the adherence and flexibility of the model to represent practical cases that can be found in reality. For the case of the dedication of tanks to lines, the model was compared with the dedicated model F1 (FERREIRA et al, 2012). The results indicate that the SMMRPM model is flexible and adherent to represent practical scenarios in which other models are not applicable, for example the possibility of scheduling preventive maintenance and consideration of perishability are differential of the proposal. In the plans obtained, it was shown that it is important to include these considerations that significantly affect the productive plans. In the case of dedication, compared to the dedicated model, the formulation SMMRPM achieves production plans, on average, 52.63 \% less costly than F1.
Nesta dissertação de mestrado é pesquisado o problema geral integrado de dimensionamento e sequenciamento de lotes da produção de bebidas não alcoólicas com sincronia ente os estágios e janelas de tempo de operação para programação de manutenções preventivas. O problema é caracterizado por ter dois estágios sincronizados e dependentes entre si. As máquinas do primeiro estágio (tanques) podem suprir ao mesmo tempo várias linhas de envase no segundo estágio, onde são envasados os itens finais. Existem tempos e custos de setup dependentes da sequência de produção. A revisão da literatura relacionada indica que modelos existentes referem-se, em geral, a casos particulares do problema geral aqui tratado, sendo que os casos mais comuns são a dedicação de tanques à linhas, e desconsideração da perecibilidade dos xaropes e da possibilidade de programar manutenções preventivas. Foi proposto um modelo matemático para o problema geral, denominado SMMRPM, e aplicado em diversas instâncias a fim de mostrar a aderência e a flexibilidade do modelo para representar casos práticos que podem ser achados na realidade. Para o caso da dedicação de tanques a linhas, o modelo foi comparado com o modelo dedicado F1 (FERREIRA et al, 2012). Os resultados indicam que o modelo SMMRPM é flexível e aderente para representar cenários práticos em que outros modelos não são aplicáveis, por exemplo a possibilidade de programar manutenções preventivas e consideração da perecibilidade são diferenciais da proposta. Nos planos obtidos foi mostrada a importância da inclusão destas considerações que afetam significativamente os planos produtivos. No caso da dedicação, comparado com o modelo dedicado, a formulação SMMRPM consegue planos de produção, em média, 52.63 % menos custosos que o F1.
Demanda Social

This thesis considers the disk scheduling problem. The problem is investigated in two types of settings: offline and online. We first adopt the traveling salesman problem with time windows in the scheduling literature for solving the offline problem. Then we develop a decision epoch scheme in which offline problems are iteratively used in solving the online problem. We perform an experimental study for our approach and two well-known disk scheduling algorithms, and compare them according to several performance criteria.

A flexible workforce or a versatile machine is employed to perform various types of operations. Often these resources are associated with setups. Whenever a worker or machine switches from processing one type of operation to another a setup time may be required although several operations of a same type can be processed in succession after a single setup. The presence of setups gives rise to the problem of choosing batch sizes that are neither too large nor too small. In the last one and a half decade, many researchers have addressed the problem of scheduling with batching. A majority of articles assumes that there is only one type of scarce resource, which is typically machine. Often there can be two scarce resources such as a worker and a machine or a machine and a tool. We propose a resource constrained scheduling model with a single operator and two or more machines. Whenever the operator changes machine, a setup time is required that may be sequence dependent or sequence independent. We consider the two cases of an open shop and a flow shop. In the open shop case, the order in which a job visits the machines is unrestricted. In the flow shop case, every job must visit the machines in the same order. We consider various scheduling objectives. For variable number of machines, many cases are intractable. We discuss some dominance properties that narrow down the search for an optimal schedule. We present a dynamic programming approach which solves a large number of cases. The running time of the dynamic program is polynomial for a fixed number of machines. For the case of two machines, we show that the dominance properties have a nice interpretation. We develop some algorithms and justify their use by establishing running times, comparing the running times with those of the existing algorithms, and testing the performance of the algorithms.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.
Includes bibliographical references (p. [109]-113).
In this dissertation we study a broad class of stochastic scheduling problems characterized by the presence of hard deadline constraints. The input to such a problem is a set of jobs, each with an associated value, processing time, and deadline. We would like to schedule these jobs on a set of machines over time. In our stochastic setting, the processing time of each job is random, known in advance only as a probability distribution (and we make no assumptions about the structure of this distribution). Only after a job completes do we know its actual "instantiated" processing time with certainty. Each machine can process only a singe job at a time, and each job must be assigned to only one machine for processing. After a job starts processing we require that it must be allowed to complete - it cannot be canceled or "preempted" (put on hold and resumed later). Our goal is to devise a scheduling policy that maximizes the expected value of jobs that are scheduled by their deadlines. A scheduling policy observes the state of our machines over time, and any time a machine becomes available for use, it selects a new job to execute on that machine. Scheduling policies can be classified as adaptive or non-adaptive based on whether or not they utilize information learned from the instantiation of processing times of previously-completed jobs in their future scheduling decisions. A novel aspect of our work lies in studying the benefit one can obtain through adaptivity, as we show that for all of our stochastic scheduling problems, adaptivity can only allow us to improve the expected value obtained by an optimal policy by at most a small constant factor. All of the problems we consider are at least NP-hard since they contain the deterministic 0/1 knapsack problem as a special case. We therefore seek to develop approximation algorithms: algorithms that run in polynomial time and compute a policy whose expected value is provably close to that of an optimal adaptive
(cont.) policy. For all the problems we consider, we can approximate the expected value obtained by an optimal adaptive policy to within a small constant factor (which depends on the problem under consideration, but is always less than 10). A small handful of our results are pseudo-approximation algorithms, delivering an approximately optimal policy that is feasible with respect to a slightly expanded set of deadlines. Our algorithms utilize a wide variety of techniques, ranging from fairly well-established methods like randomized rounding to more novel techniques such as those we use to bound the expected value obtained by an optimal adaptive policy. In the scheduling literature to date and also in practice, the "deadline" of a job refers to the time by which a job must be completed. We introduce a new model, called the start deadline model, in which the deadline of a job instead governs the time by which we must start the job. While there is no difference between this model and the standard "completion deadline" model in a deterministic setting, we show that for our stochastic problems, one can generally obtain much stronger approximation results with much simpler analyses in the start deadline model. The simplest problem variant we consider is the so-called stochastic knapsack problem, where all jobs share a common deadline and we schedule them on a single machine. The most general variant we consider involves scheduling jobs with individual deadlines on a set of "unrelated" parallel machines, where the value of a job and its processing time distribution can vary depending on the machine to which it is assigned.
(cont.) We also discuss algorithms based on dynamic programming for stochastic scheduling problems and their relatives in a discrete-time setting (where processing times are small integers), and we show how to use a new technique from signal processing called zero-delay convolution to improve the running time of dynamic programming algorithms for some of these problems.
by Brian Christopher Dean.
Ph.D.

Crew scheduling and crew rostering are similar and related problems which can be solved by similar procedures. So far, the existing solution methods usually create a model for each one of these problems (scheduling and rostering), and when they are solved together in some cases an interaction between models is considered in order to obtain a better solution. A single set covering model to solve simultaneously both problems is presented here, where the total quantity of drivers needed is directly considered and optimized. This integration allows to optimize all of the depots at the same time, while traditional approaches needed to work depot by depot, and also it allows to see and manage the relationship between scheduling and rostering, which was known in some degree but usually not easy to quantify as this model permits. Recent research in the area of crew scheduling and rostering has stated that one of the current challenges to be achieved is to determine a schedule where crew fatigue, which depends mainly on the quality of the rosters created, is reduced. In this approach rosters are constructed in such way that stable working hours are used in every week of work, and a change to a different shift is done only using free days in between to make easier the adaptation to the new working hours. Computational results for real-world-based instances are presented. Instances are geographically diverse to test the performance of the procedures and the model in different scenarios.

Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-09-21T13:50:00Z No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5)
Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2016-09-27T19:31:27Z (GMT) No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5)
Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2016-09-27T19:31:38Z (GMT) No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5)
Made available in DSpace on 2016-09-27T19:42:35Z (GMT). No. of bitstreams: 1 TeseCCMT.pdf: 3540141 bytes, checksum: e392913d01ce26b3d8bd932aa7e84611 (MD5) Previous issue date: 2015-03-31
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
The generation of Reactive Production Scheduling (PRP) in order to minimize the makespan is an important activity in the manufacturing industry, in view of the numerous articles reflecting this search today. Among these studies highlight the global search use in hybridization or collaboration with local search, especially of Genetic Algorithm (GA) with Variable Neighborhood Search (VNS). But see that the neighborhood structures used are not related to the goal of makespan minimization or when they are, are difficult to obtain. In order to cover this topic, this thesis proposes the hypothesis that a strongly correlated neighborhood structure with objective of makespan minimization in PRP problems, based on spanning tree, and applied on a collaboration among a genetic algorithm with VNS, perform better or equal to those obtained by other studies using other neighborhood structures or without the use of local search. The purpose was to construct a collaboration of GA and VNS using a neighborhood structure based on the mapping of the solution in the spanning tree associated with the problem, in the local search time, and operating with the insert, swap and 2-opt operators. The planning of experiments for validation contemplated since the implementation and comparison of four variants of reactive production scheduling in three job shop scenarios of different sizes. Each pair of comparisons had its calculated sample size and has been tested with the appropriate hypothesis test. The four variants were compared: Genetic Algorithm only and three collaborations of GA with VNS using the neighborhood structure proposal and two other neighborhood structures (Critical Path and Natural Representation) found in the literature review. The scenarios came from Taillard base. The tests corroborate the hypothesis, with 95% confidence, compared to other works and the main contribution of this thesis is to create an efficient method for minimizing makespan in PRP.
A geração de Programação Reativa da Produção (PRP), com o objetivo de minimizar o makespan, é uma atividade importante na indústria manufatureira, tendo em vista os numerosos artigos que abordam esta pesquisa na atualidade. Dentre estas pesquisas, destaca-se o uso de hibridização ou colaboração de busca global com busca local, notadamente de Algoritmo Genético (AG) com Variable Neighborhood Search (VNS). Porém, nota-se que as estruturas de vizinhança utilizadas não são correlatas à função de minimização de makespan ou, quando o são, são de difícil obtenção. Com o intuito de cobrir tal tópico, esta tese propõe a hipótese de que uma estrutura de vizinhança fortemente correlata ao objetivo de minimização de makespan em problemas de PRP, baseando-se em árvore de cobertura e aplicada em uma colaboração de algoritmo genético e VNS, obtém resultados melhores aos obtidos por outros trabalhos, que fazem uso de outras estruturas de vizinhança ou que não utilizam a busca local. A proposta é a construção de um método de colaboração entre AG e VNS usando uma estrutura de vizinhança baseada no mapeamento da solução, em tempo de busca local, na árvore de cobertura associada ao problema, atuando com os operadores insert, swap e 2-opt. O planejamento dos experimentos para validação contempla a execução e comparação de quatro variantes de solução de problemas de Programação Reativa da Produção em três cenários de job shop de diversas dimensões. Cada par de comparações tem seu tamanho amostral calculado e é examinado com o teste de hipótese adequado. As quatro variantes comparadas são: Algoritmo Genético e três colaborações entre Algoritmo Genético e Variable Neighborhood Search (VNS) usando a estrutura de vizinhança proposta e outras duas estruturas de vizinhança (Caminho Crítico e Representação Natural) encontradas na revisão da literatura. Os cenários vem da base Taillard. Os testes corroboram a hipótese com 95% de confiança na comparação com outros trabalhos e a principal contribuição desta tese é a criação de um método eficiente para minimização de makespan em PRP.

This thesis aims to review and analyze the scheduling problem in general and Job Shop Scheduling Problem (JSSP) in particular and the solution techniques applied to these problems. The JSSP is the most general and popular hard combinational optimization problem in manufacturing systems. For the past sixty years, an enormous amount of research has been carried out to solve these problems. The literature review showed the inherent shortcomings of solutions to scheduling problems. This has directed researchers to develop hybrid approaches, as no single technique for scheduling has yet been successful in providing optimal solutions to these difficult problems, with much potential for improvements in the existing techniques. The hybrid approach complements and compensates for the limitations of each individual solution technique for better performance and improves results in solving both static and dynamic production scheduling environments. Over the past years, hybrid approaches have generally outperformed simple Genetic Algorithms (GAs). Therefore, two novel priority heuristic rules are developed: Index Based Heuristic and Hybrid Heuristic. These rules are applied to benchmark JSSP and compared with popular traditional rules. The results show that these new heuristic rules have outperformed the traditional heuristic rules over a wide range of benchmark JSSPs. Furthermore, a hybrid GA is developed as an alternate scheduling approach. The hybrid GA uses the novel heuristic rules in its key steps. The hybrid GA is applied to benchmark JSSPs. The hybrid GA is also tested on benchmark flow shop scheduling problems and industrial case studies. The hybrid GA successfully found solutions to JSSPs and is not problem dependent. The hybrid GA performance across the case studies has proved that the developed scheduling model can be applied to any real-world scheduling problem for achieving optimal or near-optimal solutions. This shows the effectiveness of the hybrid GA in real-world scheduling problems. In conclusion, all the research objectives are achieved. Finaly, the future work for the developed heuristic rules and the hybrid GA are discussed and recommendations are made on the basis of the results.

This dissertation focuses on supply chain design and logistics problems with emphasis on biomass logistics and routing problems. In biomass logistics, we have studied problems arising in a switchgrass-based bio-ethanol supply chain encountered in the Southeast, and a corn stover harvest scheduling problem faced in the Midwest Unites States, both pertaining to the production of cellulosic ethanol. The main contributions of our work have been in introducing new problems to the literature that lie at the interface of the lot-sizing and routing problems, and in developing effective exact algorithms for their solution. In the routing area, we have addressed extensions of the well-known traveling salesman and vehicle routing problems. We have proposed new formulations and have developed exact algorithms for the single and multiple asymmetric traveling salesmen problems (ATSP and mATP), the high-multiplicity asymmetric traveling salesman problem (HMATSP) and its extensions, and the fixed-destination multi-depot traveling salesman problem with load balancing (FD-MTSPB). Furthermore, we have introduced a new strategy to reduce routing cost in the classical vehicle routing problem (VRP).
Ph. D.

Agent-based computing has attracted much attention as a promising technique for application domains that are distributed, complex and heterogeneous. Current research on multi-agent systems (MAS) has become mature enough to be applied as a technology for solving problems in an increasingly wide range of complex applications. The main formal architectures used to describe the relationships between agents in MAS are centralised and distributed architectures. In computational complexity theory, researchers have classified the problems into the followings categories: (i) P problems, (ii) NP problems, (iii) NP-complete problems, and (iv) NP-hard problems. A method for computing the solution to NP-hard problems, using the algorithms and computational power available nowadays in reasonable time frame remains undiscovered. And unfortunately, many practical problems belong to this very class. On the other hand, it is essential that these problems are solved, and the only possibility of doing this is to use approximation techniques. Heuristic solution techniques are an alternative. A heuristic is a strategy that is powerful in general, but not absolutely guaranteed to provide the best (i.e. optimal) solutions or even find a solution. This demands adopting some optimisation techniques such as Evolutionary Algorithms (EA). This research has been undertaken to investigate the feasibility of running computationally intensive algorithms on multi-agent architectures while preserving the ability of small agents to run on small devices, including mobile devices. To achieve this, the present work proposes a new Hybrid Multi-Agent Architecture (HMAA) that generates new heuristics for solving NP-hard problems. This architecture is hybrid because it is "semi-distributed/semi-centralised" architecture where variables and constraints are distributed among small agents exactly as in distributed architectures, but when the small agents become stuck, a centralised control becomes active where the variables are transferred to a super agent, that has a central view of the whole system, and possesses much more computational power and intensive algorithms to generate new heuristics for the small agents, which find optimal solution for the specified problem. This research comes up with the followings: (1) Hybrid Multi-Agent Architecture (HMAA) that generates new heuristic for solving many NP-hard problems. (2) Two frameworks of HMAA have been implemented; search and optimisation frameworks. (3) New SMA meeting scheduling heuristic. (4) New SMA repair strategy for the scheduling process. (5) Small Agent (SMA) that is responsible for meeting scheduling has been developed. (6) “Local Search Programming” (LSP), a new concept for evolutionary approaches, has been introduced. (7) Two types of super-agent (LGP_SUA and LSP_SUA) have been implemented in the HMAA, and two SUAs (local and global optima) have been implemented for each type. (8) A prototype for HMAA has been implemented: this prototype employs the proposed meeting scheduling heuristic with the repair strategy on SMAs, and the four extensive algorithms on SUAs. The results reveal that this architecture is applicable to many different application domains because of its simplicity and efficiency. Its performance was better than many existing meeting scheduling architectures. HMAA can be modified and altered to other types of evolutionary approaches.