Para iniciar esta Tesis Doctoral se buscó un problema de producción sencillo pero de amplia aplicación práctica que permitiera adaptarlo para llegar a problemas más generales y de más amplia aplicación. Por este motivo, nos centramos en las máquinas paralelas, y dentro de ellas, en las no relacionadas dado que son una generalización de los casos de máquinas idénticas y de las uniformemente relacionadas. Escogimos el objetivo de minimizar el tiempo máximo de finalización o Cm ax, uno de los más comunes de la literatura. Este problema tiene la facultad de que, a pesar de su carácter teórico, tiene una amplia aplicación práctica, como el caso de secuenciar las tareas de los hornos de cocción cerámicos. Por otra parte se quería ampliar el problema para el caso en que no se usaran todas las máquinas o no se hicieran todos los trabajos necesariamente. Las metas perseguidas son el presentar unos algoritmos sencillos y potentes para la resolución del problema R//Cm ax, capaces de constituirse en el estado del arte. Dado que los modernos ordenadores montan casi en su totalidad varios núcleos en su CPU y los algoritmos se van adaptando a este hecho, también se ha buscado realizar una adaptación de los algoritmos para su uso en paralelo. Finalmente, se pone como meta el encontrar métodos eficaces y sencillos para la resolución de problemas de este tipo en donde no se emplearan todas las máquinas o no se realizaran todos los trabajos. En la presente Tesis Doctoral se realizó un amplio estudio de la literatura existente respecto al problema de máquinas paralelas no relacionadas y se extrajo el estado del arte, así como un estudio del posible tipo de instancias a emplear, dado que no existía una grupo de instancias tipo para este problema. Se presentan cuatro algoritmos iniciales sencillos que mejoran los resultados del estado del arte en algunos casos y dan mejores resultados de media en el conjunto total de instancias tratadas. / Fanjul Peyró, L. (2011). Nuevos algoritmos para el problema de secuenciación en máquinas paralelas no relacionadas y generalizaciones [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/9312

Dans cette thèse nous nous sommes intéressés à l’extension du problème job-shop en ajoutant la contrainte du transport des jobs entre les différentes machines. Dans cette étude nous avons retenu l’existence de deux types de robots, les robots de capacité de chargement unitaire (capacité=1 veut dire qu’un robot ne peut transporter qu’un seul job à la fois) et les robots de capacité de chargement non unitaire (capacité>1 veut dire qu’un robot peut transporter plusieurs job à la fois). Nous avons traité cette extension en deux étapes. Ainsi, la première étape est consacrée au problème du job-shop avec plusieurs robots de capacité de chargement unitaire et en seconde étape en ajoutant la capacité de chargement non unitaire aux robots. Pour les deux problèmes étudiés nous avons proposé :• Une modélisation linéaire ;• Une modélisation sous forme de graphe disjonctif ;• Plusieurs heuristiques de construction de solutions ;• Plusieurs recherches locales qui améliorent les solutions obtenues ;• Utilisation des algorithmes génétiques / mémétiques comme schéma global d’optimisation ;• De nouveaux benchmarks, des résultats de test de nos approches sur nos benchmarks et ceux de la littérature et ces résultats sont commentés et comparés à ceux de la littérature. Les résultats obtenus montrent la pertinence de notre modélisation ainsi que sa qualité. / In this thesis we are interested in the extension of the job-shop problem by adding the constraint of transport of jobs between different machines. In this study we used two types of robots, robots with unary loading capacity (capacity =1 means that each robot can carry only one job at a time,) and robots with non unary loading capacities (robot with capacity >1 can carry more than one job at time). Thus, the first step is devoted to the problem of job-shop with several robots with unary loading capacity. In the second step we extend the problem by adding the non-unary loading capacities to the robots. For both problems studied we have proposed :• A linear modeling ;• A Disjunctive graph Model ;• Several constructive heuristics ;• Several local searches methods that improve the obtained solutions ;• Use of genetic / memetic algorithms as a global optimization schema ;• New benchmarks, test results of our approaches on our benchmarks and those present in the literature and these results are commented and compared with those of literature. The results show the relevance of our model and its quality.

Dans cette thèse nous nous sommes intéressés à l'extension du problème job-shop en ajoutant la contrainte du transport des jobs entre les différentes machines. Dans cette étude nous avons retenu l'existence de deux types de robots, les robots de capacité de chargement unitaire (capacité=1 veut dire qu'un robot ne peut transporter qu'un seul job à la fois) et les robots de capacité de chargement non unitaire (capacité>1 veut dire qu'un robot peut transporter plusieurs job à la fois). Nous avons traité cette extension en deux étapes. Ainsi, la première étape est consacrée au problème du job-shop avec plusieurs robots de capacité de chargement unitaire et en seconde étape en ajoutant la capacité de chargement non unitaire aux robots. Pour les deux problèmes étudiés nous avons proposé :* Une modélisation linéaire ;* Une modélisation sous forme de graphe disjonctif ;* Plusieurs heuristiques de construction de solutions ;* Plusieurs recherches locales qui améliorent les solutions obtenues ;* Utilisation des algorithmes génétiques / mémétiques comme schéma global d'optimisation ;* De nouveaux benchmarks, des résultats de test de nos approches sur nos benchmarks et ceux de la littérature et ces résultats sont commentés et comparés à ceux de la littérature. Les résultats obtenus montrent la pertinence de notre modélisation ainsi que sa qualité.

Atualmente, os hospitais se veem obrigados a melhorar sua produtividade. Os centros cirúrgicos, além de ser um dos setores com maiores custos, também é o que mais gera receita dentro de um hospital, dessa forma torna-se extremamente importante o gerenciamento eficiente desse setor. Os métodos de otimização para programação de cirurgias podem ser usados como ferramentas para reduzir filas e ociosidade nos centros cirúrgicos, aumentando sua produtividade. O Problema de Programação de Cirurgias Eletivas com Múltiplos Recursos e Múltiplas Etapas consiste em alocar os recursos às etapas do processo cirúrgico dos pacientes, considerando as diferentes necessidades e rotas de cada paciente e, então, programar essas etapas no tempo respeitando a disponibilidade dos recursos e a sequência das etapas do processo cirúrgico dos pacientes. Esse problema é classificado na literatura como NP-hard e pode ser descrito como um Job Shop Flexível com blocking e função objetivo de minimização do número de pacientes não atendidos e do instante de término da última etapa, o makespan. O Objetivo desse trabalho é propor um modelo matemático e uma heurística construtiva para a resolução desse problema. O modelo matemático Multi-Mode Blocking Job Shop (MMBJS) apresentado em Pham e Klikert (2008) é explorado e algumas melhorias são apontadas neste trabalho. Um modelo matemático de Programação Linear Inteira Mista alternativo é proposto, a fim de reduzir o esforço computacional, ajustar o cálculo do makespan e sugerir uma estratégia de priorização de pacientes. Testes computacionais foram realizados, afim de comparar o modelo MMJBS e o modelo proposto. Para instâncias em que todos os pacientes são atendidos, as soluções encontradas pelo CPLEX para ambos modelos são iguais, porém o tempo computacional necessário para encontrar uma solução ótima é em média 45% menor no modelo proposto. Também foram realizados testes computacionais com objetivo de observar o comportamento do modelo com diferentes configurações de recursos. Para instâncias com 15 pacientes, os testes apontam que o tempo computacional para encontrar a solução ótima é superior a 2h de processamento. Dessa forma, uma heurística construtiva é proposta, com objetivo de gerar soluções factíveis com pouco esforço computacional. A heurística proposta aloca cada etapa do tratamento de cada paciente aos recursos necessários, respeitando as janelas de disponibilidade dos recursos e buscando reduzir a folga no sistema. Um exemplo de aplicação da heurística construtiva é apresentado. As propostas para trabalhos futuros são apresentadas no capítulo final desta dissertação. / For the past few years, hospitals have been forced to improve their productivity, with surgical centers being one of the sectors with higher costs within such organizations, but also the ones that generate the most revenue. Thus, optimization methods for surgical programming are tools that can be used to reduce queues and idleness in these sectors and consequently achieve the aforementioned goals. The \"Problem of Programming Multiple Surgical Resources with Multiple Steps\"consists in allocating the existing resources to each surgery stage that a patient will need to go through, considering the different needs, sequence and specificities of each of them, and then scheduling these steps in time. This type of problem is classified in the current literature as an NP-hard problem, being described as a Flexible Job Shop with blocking and an objective function that seeks to minimize the number of patients not served and the total makespan. The general purpose of this research is to propose a mathematical model and a constructive heuristic for this type problem. The proposed model explores the mathematical model Multi-Mode Blocking Job Shop (MMBJS) presented in Pham and Klikert (2008) suggesting improvements through the use of an alternative Mixed Integer Linear Programming that aims to: reduce the computational effort, adjust the makespan calculation and suggest a strategy of patients prioritization. In order to prove the benefits of the proposed enhancements, computational tests were performed to compare the MMJBS model and the proposed model, identifying that for instances where in which all patients are attended, the solutions found by CPLEX for both models are the same, but with a lower computational time the proposed model (45% average reduction). Also, other computational tests were performed to observe the behavior of the model with different configurations of resources. For instances with 15 patients, the tests indicate that the computational time to find the optimal solution is greater than 2 hours of processing. Thus a constructive heuristic is proposed, it aims to generate feasible solutions with little computational effort. The proposed heuristic allocates each surgery stage of a patient to the necessary resources, respecting the available windows and seeking to reduce the total slack in the system. An example of the application of the constructive heuristic is also presented. At last, future works proposals are presented in the final chapter of this dissertation.

No description available.

No description available.

In this thesis we have tackled a few scheduling problems under energy constraint, since the energy issue is becoming crucial, for both economical and environmental reasons. In the first chapter, we exhibit tight bounds on the energy metric of a classical algorithm that minimizes the makespan of independent tasks. In the second chapter, we schedule several independent but concurrent pipelined applications and address problems combining multiple criteria, which are period, latency and energy. We perform an exhaustive complexity study and describe the performance of new heuristics. In the third chapter, we study the replica placement problem in a tree network. We try to minimize the energy consumption in a dynamic frame. After a complexity study, we confirm the quality of our heuristics through a complete set of simulations. In the fourth chapter, we come back to streaming applications, but in the form of series-parallel graphs, and try to map them onto a chip multiprocessor. The design of a polynomial algorithm on a simple problem allows us to derive heuristics on the most general problem, whose NP-completeness has been proven. In the fifth chapter, we study energy bounds of different routing policies in chip multiprocessors, compared to the classical XY routing, and develop new routing heuristics. In the last chapter, we compare the performance of different algorithms of the literature that tackle the problem of mapping DAG applications to minimize the energy consumption.

The Master’s thesis deals with production scheduling in an industrial company. It uses the means of artificial intelligence to develop an appropriate production schedule in a generalized Flow-shop Programming problem. This problem can be solved by application which is a result of this thesis and was prepaired with use of the software Matlab 7.1 and its Genetic Algorithm and Direct Search toolbox. There is a part devoted to the use of advanced production systems (APS) and the concept of the operative production planning in praxis as well. The thesis pays attention to various optimization models in production scheduling and supply chain management too.

This paper presents the development and mathematical implementation of a production scheduling model utilizing mixed-integer linear programming (MILP). A simplified model of a real-world multi-product batch plant constitutes the basis. The paper shows practical extensions to the model, resulting in a digital twin of the plant. Apart from sequential arrangement, the final model contains maintenance periods, campaign planning and storage constraints to a limited extend. To tackle weak computational performance and missing model features, a condensed mathematical formulation is introduced at first. After stating that these measures do not suffice for applicability in a restrained time period, a novel solution strategy is proposed. The overall non-iterative algorithm comprises a multi-step decomposition approach, which starts with a reduced scope and incrementally complements the schedule in multiple subproblem stages. Each of those optimizations holds less decision variables and makes use of warmstart information obtained from the predecessor model. That way, a first feasible solution accelerates the subsequent improvement process. Furthermore, the optimization focus can be shifted beneficially leveraging the Gurobi solver parameters. Findings suggest that correlation may exist between certain characteristics of the scheduling scope and ideal parameter settings, which yield potential for further investigation. Another promising area for future research addresses the concurrent multi-processing of independent MILPs on a single machine. First observations indicate that significant performance gains can be achieved in some cases, though sound dependencies were not discovered yet.

The central thesis of this dissertation is that by combining classical scheduling methodologies with those of inventory management and queueing theory we can better model, understand and solve complex real-world scheduling problems. In part II of this dissertation, we provide models of a realistic supply chain scheduling problem that capture both its combinatorial nature and its dependence on inventory availability. We present an extensive empirical evaluation of how well implementations of these models in commercially available software solve the problem. We are therefore able to address, within a specific problem, the need for scheduling to take into account related decision-making processes. In order to simultaneously deal with combinatorial and dynamic properties of real scheduling problems, in part III we propose to integrate queueing theory and deterministic scheduling. Firstly, by reviewing the queueing theory literature that deals with dynamic resource allocation and sequencing and outlining numerous future work directions, we build a strong foundation for the investigation of the integration of queueing theory and scheduling. Subsequently, we demonstrate that integration can take place on three levels: conceptual, theoretical and algorithmic. At the conceptual level, we combine concepts, ideas and problem settings from the two areas, showing that such combinations provide insights into the trade-off between long-run and short-run objectives. Next, we show that theoretical integration of queueing and scheduling can lead to long-run performance guarantees for scheduling algorithms that have previously been proved only for queueing policies. In particular, we are the first to prove, in two flow shop environments, the stability of a scheduling method that is based on the traditional scheduling literature and utilizes processing time information to make sequencing decisions. Finally, to address the algorithmic level of integration, we present, in an extensive future work chapter, one general approach for creating hybrid queueing/scheduling algorithms. To our knowledge, this dissertation is the first work that builds a framework for integrating queueing theory and scheduling. Motivated by characteristics of real problems, this dissertation takes a step toward extending scheduling research beyond traditional assumptions and addressing more realistic scheduling problems.