Em um mercado global, tem sido observada a tendência para a dispersão geográfica das fabricas. Esta dispersão e motivada pela oportunidade de explorar as vantagens locais, sob diferentes pontos de vista. Essa estrutura também permite a interação mais intensa entre plantas de diferentes empresas produtivas. Neste sentido, o conceito de Empresa Virtual (EV) e fundamental para explorar novas estratégias de negócios, tais como foco nas competências essenciais, orientação máxima para o cliente e produção distribuída. No entanto, nesta nova estrutura produtiva, há novos requisitos para o planejamento e para o estabelecimento da data de entrega dos pedidos. Um sistema de Planejamento e Controle da Produção (PCP) convencional utiliza uma arquitetura hierárquica, o que não atende o requisito de autonomia das empresas parceiras. Para atender a essas novas exigências, este trabalho apresenta uma arquitetura de sistemas de planejamento e controle da produção no contexto de EV. Na proposta são utilizados os conceitos de janelas de tempo em conjunto com propagação de restrições para atender os requisitos de prazo de entrega de produtos. Estes dois conceitos tem sido amplamente utilizados na literatura relacionada a sistemas de planejamento convencionais, no entanto, não no contexto de EV. Nesta abordagem, as janelas de tempo delimitam o intervalo de alocação das tarefas nos sistemas de produção envolvidos, enquanto as restrição de capacidade identificam janelas de tempo factíveis considerando a importância da data de vencimento do pedido. E apresentado um exemplo da utilização da arquitetura e um exemplo de implementação. Este trabalho engloba EVs com empresas parceiras de diversos tipos de produção (produção em lotes e produção discreta). E utilizado o Production Flow Schema (PFS) para modelagem dos processos produtivos segundo uma abordagem hierárquica, com base em sucessivos renamentos para construir o modelo de forma progressiva e estruturada onde as propriedades do modelo ficam asseguradas por construção. Este refinamento gera sub-grafos em Rede de Petri, que são utilizados para a analise e o controle do processo produtivo. / In a global market, the trend for geographical dispersion of manufacturing plants has been observed. This dispersion is motivated by the opportunity to exploit local advantages under dierent viewpoints. This structure also allows for more intense interaction between plants of dierent productive enterprises. In this sense, the concept of Virtual Enterprise (VE) is fundamental to explore new business strategies such asfocus on core competencies,maximal customer orientationanddistributed production. However, in this new productive structure, there are new requirements for planning and for establishing the delivery date of the orders. A conventional Production Planning and Control system (PPC) uses a hierarchical architecture, which does not meet the requirement of autonomy of the partners companies. To address these new requirements, this work introduces a Production Planning and Control System Architecture in EV context. In the proposal are used the concepts oftime windowsandconstraint propagationto meet the deadline requirements of product delivery. These two concepts have been widely used in the literature relating to conventional planning systems, however, not in the EV context. In this approach, thetime windowsdelimit the allocation range of tasks in production systems involved, while the capacity constraint identify the feasible time window considering the importance of the ordes due date. An example of using the architecture and an implementation is presented. This work includes EVs with partner companies of various types of production (production batch and discrete manufacturing). Production Flow Schema (PFS) is used for modeling the processes according to a hierarchical approach based on successive renements to construct progressive and structured model where the properties of model are ensured by construction. This renement generates sub-graphs in Petri Net, which are used for the analysis and control of the production process.

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T18:16:55Z (GMT). No. of bitstreams: 1 Hokama_PedroHenriqueDelBianco_M.pdf: 1340789 bytes, checksum: b5cc3f26e41b90afabdfac5c7a33bf05 (MD5) Previous issue date: 2011 / Resumo: Nesta dissertação de mestrado apresentamos um método exato para o Problema do Caixeiro Viajante com Restrições de Empacotamento Tridimensional, que combina o Problema do Caixeiro Viajante o Problema de Empacotamento Tridimensional com Restrição de Ordem. Neste problema, um veículo deve partir carregado de um depósito e entregar caixas em pontos pré-definidos para seus clientes. Cada cliente tem um conjunto de caixas que deve receber e o objetivo é minimizar o custo de deslocamento do veículo. As caixas devem ser retiradas a partir da porta do contêiner do veículo e a remoção das caixas de um cliente não podem ser obstruídas pelas caixas a serem descarregadas posteriormente. Propomos uma abordagem exata baseada em branch-and-cut para buscar uma rota de custo mínimo. Apresentamos algumas adaptações de algoritmos da literatura e uma formulação em Programação por Restrições para encontrar um empacotamento que obedece restrições de ordem. Realizamos testes computacionais em instâncias geradas aleatoriamente e comparamos resultados com os algoritmos adaptados da literatura. Os resultados foram bastante satisfatórios resolvendo instâncias de tamanho médio em tempo computacional aceitável na prática / Abstract: We present an exact method for the Traveling Salesman Problem with Three-dimensional Loading Constraints. This problem combines the Traveling Salesman Problem, and the Three- Dimensional Packing Problem With Loading Constraints. In this problem, a vehicle must be loaded at the depot and deliver boxes to the customers. Every customer has a set of boxes that should receive and our goal is to minimize the travel cost of the vehicle. Unloading is done through a single side of the container and items from an unloading customer must not be blocked by items to be delivered later. We propose exact and heuristic branch-and-cut algorithm to find a minimum cost route. Adaptations of algorithms from the literature and a Constraint Programming formulation is presented to find a packing that consider unloading contraints. We performed computational tests on instances randomly generated and compared results with the algorithms adapted from literature. The results were quite satisfactory resolving several instances in reasonable computational time / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Un vérificateur de modèle peut produire une trace de contreexemple, pour un programme erroné, qui est souvent difficile à exploiter pour localiser les erreurs dans le code source. Dans ma thèse, nous avons proposé un algorithme de localisation d'erreurs à partir de contreexemples, nommé LocFaults, combinant les approches de Bounded Model Checking (BMC) avec un problème de satisfaction de contraintes (CSP). Cet algorithme analyse les chemins du CFG (Control Flow Graph) du programme erroné pour calculer les sous-ensembles d'instructions suspectes permettant de corriger le programme. En effet, nous générons un système de contraintes pour les chemins du graphe de flot de contrôle pour lesquels au plus k instructions conditionnelles peuvent être erronées. Ensuite, nous calculons les MCSs (Minimal Correction Sets) de taille limitée sur chacun de ces chemins. La suppression de l'un de ces ensembles de contraintes donne un sous-ensemble satisfiable maximal, en d'autres termes, un sous-ensemble maximal de contraintes satisfaisant la postcondition. Pour calculer les MCSs, nous étendons l'algorithme générique proposé par Liffiton et Sakallah dans le but de traiter des programmes avec des instructions numériques plus efficacement. Cette approche a été évaluée expérimentalement sur des programmes académiques et réalistes. / A model checker can produce a trace of counter-example for erroneous program, which is often difficult to exploit to locate errors in source code. In my thesis, we proposed an error localization algorithm from counter-examples, named LocFaults, combining approaches of Bounded Model-Checking (BMC) with constraint satisfaction problem (CSP). This algorithm analyzes the paths of CFG (Control Flow Graph) of the erroneous program to calculate the subsets of suspicious instructions to correct the program. Indeed, we generate a system of constraints for paths of control flow graph for which at most k conditional statements can be wrong. Then we calculate the MCSs (Minimal Correction Sets) of limited size on each of these paths. Removal of one of these sets of constraints gives a maximal satisfiable subset, in other words, a maximal subset of constraints satisfying the postcondition. To calculate the MCSs, we extend the generic algorithm proposed by Liffiton and Sakallah in order to deal with programs with numerical instructions more efficiently. This approach has been experimentally evaluated on a set of academic and realistic programs.

Cette thèse, réalisée en collaboration avec Sagem Défense Sécurité, porte sur l'élaboration d'une stratégie de recherche efficace pour la résolution de problèmes de planification d'itinéraires de véhicules. Nous considérons ici en particulier les problèmes de planification avec contraintes de points de passage et de "capacité" (énergie, bande passante radio) appliquées au véhicule. Ce document propose une approche originale, hybridant un algorithme de colonies de fourmis avec un solveur de Programmation par Contraintes existant. Le premier est utilisé pour résoudre rapidement une version relaxée du problème. La solution partielle obtenue est alors employée pour guider la recherche du second, par le biais d'une méthode de sonde, vers les zones les plus prometteuses de l'espace d'état. Cette approche permet ainsi de combiner la rapidité des métaheuristiques et la complétude de la programmation par contraintes. Nous montrons expérimentalement que cette approche satisfait les exigences pour une utilisation du planificateur dans un cadre embarqué. / This thesis, led in collaboration with Sagem Defence & Security, focuses on defining an efficient search strategy to solve vehicle path planning problems. This work addresses more precisely planning problems in which waypoints and "capacity" constraints (energy, radio bandwidth) are applied to vehicles.This document proposes an original approach, mixing an Ant Colony algorithm with an existing Constraint Programming solver. The former is used to fastly solve a relaxed version of the problem. The partial solution returned is then employed to guide the search of the latter, through a Probe Backtrack mechanism, towards the most promising areas of the state space. This approach allows to combine the metaheuristics solving fastness and the Constraint Programming completeness. We experimentally show that this approach meets the requirements for an on-line use of the planner.

Cette thèse a pour objectif la génération de séquences de franchissement dans les Réseaux de Petri Temporisés (RdPT) en utilisant une approche incrémentale. Le verrou principal auquel est confronté ce travail est l’explosion combinatoire qui résulte de la construction classique du graphe d’accessibilité du RdPT. Nous proposons d’utiliser la notion de séquence de steps temporisés, afin d’exprimer progressivement l’ensemble des séquences de franchissements permettant de passer d’un état courant à un état cible. La notion de step temporisé correspond à une abstraction logique du comportement du système considéré. Le caractère incrémental de l’approche a pour objectif de gagner en efficacité. En effet, il consiste à exprimer tout nouvel état de la résolution par rapport à une profondeur K+1, en fonction d’un état atteint à la profondeur K. Ainsi, nous proposons plusieurs algorithmes de recherche incrémentale permettant d'améliorer l'efficacité de la résolution des problèmes d'accessibilité. Nous utilisons ensuite la programmation par contraintes pour modéliser le problème de recherche d’accessibilité dans un RdPT et mettre en œuvre notre approche incrémentale. Notre approche permet également d’ajouter des contraintes spécifiques à un contexte de résolution. Nous avons notamment utilisé cette possibilité pour proposer des techniques d'identification des jetons dans un RdPT borné, dans le cadre de la reconfiguration des systèmes manufacturiers. Nous concluons par l’évaluation de différentes applications constituant des « benchmarks » permettant d’illustrer l'efficacité des approches proposées / This PhD thesis is dedicated to the generation of firing sequences in Timed Petri Net (TPN) using an incremental approach. To reduce the influence of the well-known combinatorial explosion issue, a unique sequence of timed steps is introduced to represent implicitly the underlying reachability graph of the TPN, without needing its whole construction. This sequence of timed steps is developed based on the logical abstraction technique. The advantage of the incremental approach is that it can express any state just from the last step information, instead of representing all states before.Several incremental search algorithms are introduced to improve the efficiency of our methodology. Constraint programming techniques are used to model and solve our incremental model, in which search strategies are developed that can search for solutions more efficiently. Our methodology can be used to add specific constraints to model realistic systems. Token identification techniques are developed to handle token confusion issues that appear when addressing the reconfiguration of manufacturing systems. Experimental benchmarks illustrate the effectiveness of approaches proposed in this thesis

Software systems in the automotive domain are generally safety critical and subject to strict timing requirements. Systems of this character are often constructed utilizing periodically executed tasks, that have a hard deadline. In addition, these systems may have additional deadlines that can be specified on cause-effect chains, or simply task chains. They are defined by existing tasks in the system, hence the chains are not stand alone additions to the system. Each chain provide an end-to-end timing constraint targeting the propagation of data through the chain of tasks. These constraints specify the additional timing requirements that need to be fulfilled, when searching for a valid schedule. In this thesis, an offline non-preemptive scheduling method is presented, designed for single core systems. The scheduling problem is defined and formulated utilizing Constraint Programming. In addition, to ensure that end-to-end timing requirements are met, job-level dependencies are considered during the schedule generation. Utilizing this approach can guarantee that individual task periods along with end-to-end timing requirements are always met, if a schedule exists. The results show a good increase in schedulability ratio when utilizing job-level dependencies compared to the case where job-level dependencies are not specified. When the system utilization increases this improvement is even greater. Depending on the system size and complexity the improvement can vary, but in many cases it is more than double. The scheduling generation is also performed within a reasonable time frame. This would be a good benefit during the development process of a system, since it allows fast verification when changes are made to the system. Further, the thesis provide an overview of the entire process, starting from a system model and ending at a fully functional schedule executing on a hardware platform.

L’optimisation de la planification de la maintenance des équipements de production d’électricité est une question importante pour éviter des temps d’arrêt inutiles et des coûts opérationnels excessifs. Dans cette thèse, nous présentons une classification multidimensionnelle des études de Recherche Opérationnelle portant sur ce sujet. Le secteur des énergies renouvelables étant en pleine expansion, nous présentons et discutons ensuite d’un problème de maintenance de parcs éoliens terrestres. Le problème est traité sur un horizon à court terme et l’objectif est de construire un planning de maintenance qui maximise le revenu lié à production d’électricité des éoliennes tout en prenant en compte des prévisions de vent et en gérant l’affectation de techniciens. Nous présentons plusieurs modélisations du problème basées sur la programmation linéaire. Nous décrivons aussi une recherche à grands voisinages basée sur la programmation par contraintes.Cette méthode heuristique donne des résultats probants.Nous résolvons ensuite le problème avec une approche exacte basée sur une décomposition du problème. Dans cette méthode, nous construisons successivement des plannings de maintenance optimisés et rejetons, à l’aide de coupes spécifiques, ceux pour lesquels la disponibilité des techniciens est insuffisante. Les résultats suggèrent que cette méthode est la mieux adaptée pour ce problème. Enfin, pour prendre en compte l’incertitude inhérente à la prévision de vitesses de vent, nous proposons une approche robuste dans laquelle nous prenons des décisions garantissant la réalisabilité du planning de maintenance et le meilleur revenu pour les pires scénarios de vent. / Efficiently scheduling maintenance operations of generating units is key to prevent unnecessary downtime and excessive operational costs. In this work, we first present a multidimensional classification of the body of work dealing with the optimization of the maintenance scheduling in the operations research literature. Motivated by the recent emergence of the renewable energy sector as an Environmental priority to produce low-carbon power electricity, we introduce and discuss a challenging Maintenance scheduling problem rising in the onshore wind industry. Addressing the problem on a short-term horizon, the objective is to find a maintenance plan that maximizes the revenue generated by the electricity production of the turbines while taking into account wind predictions, multiple task execution modes, and technician-to-task assignment constraints. We start by presenting several integer linear Programming formulations of the problem. We then describe a constraint programming-based large neighborhood search which proves to be an efficient heuristic solution method. We then design an exact branch-and-check approach based on a decomposition of the problem. In this method, we successively build maintenance plans while discarding – using problem-specific cuts – those that cannot be performed by the technicians. The results suggest that this method is the best suited to the problem. To tackle the Inherent uncertainty on the wind speed, we also propose a robust approach in which we aim to take risk-averse decisions regarding the revenue associated with the maintenance plan and its feasibility.

Un système de systèmes est un système dont les composants sont eux-mêmes des systèmes indépendants, tous communiquant pour atteindre un objectif commun. Lorsque ces systèmes sont mobiles, il peut être difficile d'établir des connexions de bout-en-bout. L'architecture mise en place dans de telles situations est appelée réseau tolérant aux délais. Les données sont transmises d'un système à l'autre – selon les opportunités de communication, appelées contacts, qui apparaissent lorsque deux systèmes sont proches – et disséminées dans l'ensemble du réseau avec l'espoir que chaque message atteigne sa destination. Si une donnée est trop volumineuse, elle est découpée. Chaque fragment est alors transmis séparément.Nous supposons ici que la séquence des contacts est connue. On s'intéresse donc à des applications où la mobilité des systèmes est prédictible (les réseaux de satellites par exemple). Nous cherchons à exploiter cette connaissance pour acheminer efficacement des informations depuis leurs sources jusqu'à leurs destinataires. Nous devons répondre à la question : « Quels éléments de données doivent être transférés lors de chaque contact pour minimiser le temps de dissémination » ?Nous formalisons tout d'abord ce problème, appelé problème de dissémination, et montrons qu'il est NP-difficile au sens fort. Nous proposons ensuite des algorithmes pour le résoudre. Ces derniers reposent sur des règles de dominance, des procédures de prétraitement, la programmation linéaire en nombres entiers, et la programmation par contraintes. Une partie est dédiée à la recherche de solutions robustes. Enfin, nous rapportons des résultats numériques montrant l'efficacité de nos algorithmes. / Systems of systems are supersystems comprising elements which are themselves independent operational systems, all interacting to achieve a common goal. When the subsystems are mobile, these may suffer from a lack of continuous end-to-end connectivity. To address the technical issues in such networks, the common approach is termed delay-tolerant networking. Routing relies on a store-forward mechanism. Data are sent from one system to another – depending on the communication opportunities, termed contacts, that arise when two systems are close – and stored throughout the network in hope that all messages will reach their destination. If data are too large, these must be split. Each fragment is then transmitted separately.In this work, we assume that the sequence of contacts is known. Thus, we focus on applications where it is possible to make realistic predictions about system mobility (e.g. satellite networks). We study the problem of making the best use of knowledge about possibilities for communication when data need to be routed from a set of systems to another within a given time horizon. The fundamental question is: "Which elements of the information should be transferred during each contact so that the dissemination length is minimized"?We first formalize the so-called dissemination problem, and prove this is strongly NP-Hard. We then propose algorithms to solve it. These relies on different dominance rules, preprocessing procedures, integer-linear programming, and constraint programming. A chapter is dedicated to the search for robust solutions. Finally experimental results are reported to show the efficiency of our algorithms in practice.

Constraint programming (CP) is a technology in which a combinatorial problem is modelled as a conjunction of constraints on variables ranging over given initial domains, and optionally an objective function on the variables. Such a model is given to a general-purpose solver performing systematic search to find constraint-satisfying domain values for the variables, giving an optimal value to the objective function. A constraint predicate (also known as a global constraint) does two things: from the modelling perspective, it allows a modeller to express a commonly occurring combinatorial substructure, for example that a set of variables must take distinct values; from the solving perspective, it comes with a propagation algorithm, called a propagator, which removes some but not necessarily all impossible values from the current domains of its variables when invoked during search. Although modern CP solvers have many constraint predicates, often a predicate one would like to use is not available. In the past, the choices were either to reformulate the model or to write one's own propagator. In this dissertation, we contribute to the automatic design of propagators for new predicates. Integer time series are often subject to constraints on the aggregation of the features of all maximal occurrences of some pattern. For example, the minimum width of the peaks may be constrained. Automata allow many constraint predicates for variable sequences, and in particular many time-series predicates, to be described in a high-level way. Our first contribution is an algorithm for generating an automaton-based predicate description from a pattern, a feature, and an aggregator. It has previously been shown how to decompose an automaton-described constraint on a variable sequence into a conjunction of constraints whose predicates have existing propagators. This conjunction provides the propagation, but it is unknown how to propagate it efficiently. Our second contribution is a tool for deriving, in an off-line process, implied constraints for automaton-induced constraint decompositions to improve propagation. Further, when a constraint predicate functionally determines a result variable that is unchanged under reversal of a variable sequence, we provide as our third contribution an algorithm for deriving an implied constraint between the result variables for a variable sequence, a prefix thereof, and the corresponding suffix.

De nombreuses applications informatiques nécessitent de résoudre des problèmes de décision qui sont difficiles d’un point de vue mathématique. La programmation par contraintes permet de modéliser et résoudre certains de ces problèmes, parfois définis sur des graphes. Au delà des difficultés intrinsèques aux problèmes étudiés, la taille des instances à traiter contribue à la difficulté de la résolution. Cette thèse traite de l’utilisation des graphes en programmation par contraintes, dans le but d’en améliorer la capacité de passage à l’échelle. Une première partie porte sur l’utilisation de contraintes pour résoudre des problèmes de graphes impliquant la recherche d’arbres, de chemins et de cycles Hamiltoniens. Ce sont des problèmes importants que l’on retrouve dans de nombreuses applications industrielles. Nous étudions à la fois le filtrage et les stratégies d’exploration de l’espace de recherche. Nous chercherons ensuite à nous extraire progressivement des problèmes classiquement définis sur les graphes pour exploiter ce concept sur des problèmes définis sur les entiers, voire les réels. Une seconde partie porte ainsi sur l’utilisation des graphes pour le filtrage de contraintes globales très répandues. Nous proposerons entre autres d’utiliser des graphes comme support pour décomposer dynamiquement des algorithmes de filtrage, de manière générique. Le fil conducteur de ces travaux sera d’une part l’utilisation du concept de graphe à la base de chaque raisonnement et d’autre part, la volonté pratique d’augmenter la taille des problèmes pouvant être traités en programmation par contraintes. / Many IT applications require to solve decision problems which are hard from a mathematical point of view. Constraint-programming enables to model and solve some of these problems. Among them, some are defined over graphs. Beyond the difficulty stemming from each of these problems, the size of the instance to solve increases the difficulty of the task. This PhD thesis is about the use of graphs within constraint programming, in order to improve its scalability. First, we study the use of constraint-programming to solve some graph problems involving the computation of trees and Hamiltonian paths and cycles. These problems are important and can be found in many industrial applications. Both filtering and search are investigated. Next, we move on problems which are no longer defined in terms of graph properties. We then study the use of graphs to propagate global constraints. In particular, we suggest a generic schema, relying ona graph structure, to dynamically decompose filtering algorithms. The central theme in this work is the use of graph concepts at the origin of every reasoning and the practical will to increase the size of problems that can be addressed in constraint-programming.