Denna rapport behandlar kandidatprojektet Optily som utförts av 8 studenter på Tekniska högskolan vid Linköpings universitet. Hela processen från planering och utveckling till resultatet av den slutgiltiga produkten presenteras och diskuteras. Även erfarenheter som fångats upp av projektgruppen under denna process behandlas. Företaget Ionbond Sweden AB, som är kund i projektet, arbetar med ytbeläggning av rundskaftade föremål. För att underlätta planeringen av hur deras beläggningskammare ska packas har ett datorprogram kallat Optily utvecklats av projektgruppen. Detta har med framgång ökat effektiviteten i packningen av maskinerna vilket leder till ökad omsättning eftersom fler föremål kan köras tillsammans. Utöver ökad omsättning bidrar detta också till att hjälpa Ionbond Sweden AB att nå sina uppsatta miljömål. Programmet har även lyckats förbättra arbetssituationen för de anställda genom att på förhand visa hur maskinerna ska packas och vilka ordrar som då kommer få plats. Genom att integrera systemet med Ionbond Sweden AB:s nuvarande produktdatabas hanteras alla olika produkter som kan behöva ytbeläggas. Packningens utformning tas sedan fram genom att placera objekten med hjälp av en optimeringsalgoritm vilken når ett resultat som konsekvent är bättre än vad planeringsansvarig tidigare lyckats med. Resultatet av optimeringen visualiseras sedan med hjälp av en schematisk bild på hur objekten ska placeras i beläggningskammaren för att på bästa sätt utnyttja den tillgängliga volymen.

Various types of transportation issues are a common practice. The issue may be approached mainly as the distribution of products from suppliers to consumers while minimising distribution costs. The difference of real transportation issues predominantly relates to the considered restrictions, such as capacities of vehicles and orders, time windows and other special distribution restrictions. Transportation issues were already defined by F.L. Hitchcock in 1941 and since then, a wide range of stochastic and non- determinist methods providing solutions to transportation issues have been developed. Nevertheless, introducing distribution restrictions in resolving real-life problems makes it difficult for such methods to be applied. This thesis provides a compilation of the well-known determinist methods that may be used to resolve transportation issues. The methods that are appropriate for resolving real issues are discussed in more detail. The solution procedure of the selected method is demonstrated using simple examples and the results are compared with the results of other methods. An analysis of the above methods is used to design and implement new methods to resolve real transportation issues, their results being compared with the methods provided by the commercial software product.

O problema de empacotamento de cilindros em níveis é comumente encontrado nas indústrias de cerâmica. Solucionar este problema significa encontrar o posicionamento ideal dos itens cerâmicos cilíndricos dentro do forno de modo que o menor número de fornos seja utilizado e os itens não se sobreponham e obedeçam aos limites do recipiente. Também é considerado o uso de prateleiras para que haja uma melhor ocupação do espaço do forno. Propomos uma formulação matemática não-linear inteira mista e métodos de resolução heurísticos e exato para o problema. Os métodos heurísticos consistem em escolher uma estratégia de ordenação, posicionar os itens em cada nível por meio da heurística Bottom-Left e posicionar os níveis no recipiente utilizando as estratégias Best-Fit, First-Fit ou Worst-Fit. Ao total, propomos seis variações heurísticas para resolução do problema. O método exato consiste em estimar o número de níveis e recipientes necessários e resolver o problema por meio de um solver de otimização global. Os experimentos computacionais foram realizados para um conjunto de instâncias que criamos. Os resultados mostraram que o método exato é capaz de encontrar a solução ótima em um curto período de tempo para instâncias de pequeno porte e que as heurísticas são capazes de resolver o problema em um tempo computacional baixo, para instâncias de pequeno, médio e grande porte, sendo que algumas heurísticas apresentam melhor desempenho que outras. / The cylinder packing problem in levels is commonly found in ceramic industries. Solving this problem consists in finding the ideal position of items inside furnaces so that the minimum number of furnaces is used and the items do not overlap and obeying furnaces size. In this case, it is possible to add levels to the furnace. We proposed a non-linear integer mixed mathematical model for the problem and heuristic and exact resolution methods. Heuristic methods consist of choosing a sorting strategy, packing the items at each level by a Bottom-Left heuristic, and positioning the levels in the furnace using Best-Fit, First- Fit or Worst-Fit strategy. In total, it is proposed six heuristic variations to solve the problem. The exact method consists in solving the problem by a global optimization solver. The computational experiments were run over a set of new proposed instances. The results have shown that the exact method is able to find an optimal solution in a short period of time for small instances and that the proposed heuristics are capable of solving the problem in a low computational time for small, medium and large instances. Furthermore, some of them have performed better than others.

Problemas de corte e empacotamento de itens irregulares são problemas que visam determinar um leiaute ótimo de objetos pequenos dentro de objetos maiores, a fim de atender a uma demanda. Estes problemas têm grande importância prática, já que surgem em vários tipos de indústria (como a têxtil, a de móveis e a de calçados). O problema estudado neste trabalho é o problema de corte de itens irregulares em recipientes. Os recipientes são delimitados e o objetivo é encontrar um leiaute dos objetos menores, sem sobreposição, dentro dos objetos maiores utilizando a menor quantidade de recipientes. Propomos um novo método de resolução para o problema. Nosso método é um algoritmo que gerencia um conjunto de heurísticas, de baixo nível, específicas para a resolução do problema com recipientes retangulares e irregulares. Recipientes irregulares são polígonos convexos e não convexos, que podem ser furados. As heurísticas desenvolvidas utilizam uma malha de pontos sobre a técnica de no-fit polygon para evitar a sobreposição dos itens e encontrar posições viáveis no recipiente retangular ou irregular. Os experimentos computacionais foram feitos para um grande conjunto de instâncias, de recipientes retangulares e irregulares. Os resultados demonstram a competitividade do método, que obtêm resultados bons e algumas soluções ótimas, em um tempo computacional aceitável. / Cutting and packing of irregular items are problems that aim to determine the optimum layout of small objects within larger objects (that we call bins), in order to meet a demand. These problems have great practical importance, since they emerge in various types of industry (such as textile, furniture and shoemaking). The problem studied in this work is the irregular bin packing problem. The bins are enclosed and the goal is to find a layout of items, without overlap, within the bins by using the minimum quantity of them. We propose a new method of resolution to this problem. Our method is an algorithm that manages a set of low-level heuristics, specific to solve the problem with rectangular bins and irregular bins. Irregular bins are convex and non-convex polygons, which may contain holes. The developed heuristics uses a mesh of points and the technique of no-fit polygon to avoid the overlapping of items and find feasible positions in rectangular or irregular bins. The computational experiments were performed for a large set of instances, using both rectangular and irregular bins. The results demonstrate the competitiveness of the method, which can get good results and some optimal solutions within an acceptable computational time.

O problema de empacotamento de cilindros em níveis é comumente encontrado nas indústrias de cerâmica. Solucionar este problema significa encontrar o posicionamento ideal dos itens cerâmicos cilíndricos dentro do forno de modo que o menor número de fornos seja utilizado e os itens não se sobreponham e obedeçam aos limites do recipiente. Também é considerado o uso de prateleiras para que haja uma melhor ocupação do espaço do forno. Propomos uma formulação matemática não-linear inteira mista e métodos de resolução heurísticos e exato para o problema. Os métodos heurísticos consistem em escolher uma estratégia de ordenação, posicionar os itens em cada nível por meio da heurística Bottom-Left e posicionar os níveis no recipiente utilizando as estratégias Best-Fit, First-Fit ou Worst-Fit. Ao total, propomos seis variações heurísticas para resolução do problema. O método exato consiste em estimar o número de níveis e recipientes necessários e resolver o problema por meio de um solver de otimização global. Os experimentos computacionais foram realizados para um conjunto de instâncias que criamos. Os resultados mostraram que o método exato é capaz de encontrar a solução ótima em um curto período de tempo para instâncias de pequeno porte e que as heurísticas são capazes de resolver o problema em um tempo computacional baixo, para instâncias de pequeno, médio e grande porte, sendo que algumas heurísticas apresentam melhor desempenho que outras. / The cylinder packing problem in levels is commonly found in ceramic industries. Solving this problem consists in finding the ideal position of items inside furnaces so that the minimum number of furnaces is used and the items do not overlap and obeying furnaces size. In this case, it is possible to add levels to the furnace. We proposed a non-linear integer mixed mathematical model for the problem and heuristic and exact resolution methods. Heuristic methods consist of choosing a sorting strategy, packing the items at each level by a Bottom-Left heuristic, and positioning the levels in the furnace using Best-Fit, First- Fit or Worst-Fit strategy. In total, it is proposed six heuristic variations to solve the problem. The exact method consists in solving the problem by a global optimization solver. The computational experiments were run over a set of new proposed instances. The results have shown that the exact method is able to find an optimal solution in a short period of time for small instances and that the proposed heuristics are capable of solving the problem in a low computational time for small, medium and large instances. Furthermore, some of them have performed better than others.

Cette thèse a été réalisée dans le cadre du projet « Gestion et Optimisation de la Chaîne Documentaire », projet labellisé par le Pôle de compétitivité des Industries du Commerce. Le projet a pour but de concevoir et de développer un nouveau workflow et un outil d’aide à la décision. Ce système doit être capable de gérer et d’optimiser le flux complet dématérialisé de contrats reçus à COFIDIS.Nous présentons d’abord le framework retenu dans le cadre du projet pour modéliser et implémenter le workflow. En phase de conception BPMN a été choisi. Pour la partie développement, l’utilisation de BPEL a été préconisée pour implémenter et exécuter l'application finale (services web).Cependant la flexibilité offerte par BPMN peut conduire à des propriétés indésirables du processus telles que blocage et inaccessibilité. De plus, BPMN a été conçu pour fournir des modèles Orientés Process. Les données ou les ressources y sont donc peu représentées. En conséquence, l'analyse de performance sur un modèle BPMN est quasi inexistante.Afin de surmonter ces problèmes nous proposons d’insérer dans le framework deux nouvelles phases. Ces deux phases sont appliquées au modèle BPMN. La première est une phase de vérification et de validation et la deuxième une phase d'optimisation. Ces deux phases sont réalisées en transformant le modèle BPMN vers un langage formel. Notre choix dans ce travail a été d'utiliser les réseaux de Petri. Ce qui nous a permis de vérifier et de valider de bonnes propriétés du process. Quant à l’optimisation, nous avons défini une nouvelle variante du problème d’affectation (bin packing problem) et proposé une résolution à intégrer dans le processus d’aide à la décision / This thesis has been realized as a part of the project GOCD (French acronym for Management and optimization of document life cycle) and within the context of the French competitive cluster PICOM. The project aims to design and develop a new paperless workflow system and decision making tool to replace the current paper based system. The new workflow system must manage and optimize received credit demands at COFIDIS.The first part of this thesis presents and discusses a framework to model and implement workflow systems. The proposed framework allows more flexibility in workflow reengineering process and operational analysis for different business process. The proposed framework uses the most recent and promising language to model and execute workflow the Business Process Modeling Notation (BPMN) and Business Process Execution Language (BPEL).The flexibility offered by BPMN can also lead to undesirable properties for business process such as deadlocks and unreachablity. More, BPMN notation was designed to model business process, and little consideration was concentrated to represent data and resources. As a result, carrying out performance analysis on a BPMN model is also limited.To overcome these problems, we propose two additional phases in the reengineering process. They are applied to the target BPMN model. The first phase is verification and validation and the second one is optimization. These two phases are realized by transforming the BPMN model to a formal language, Petri nets. As for optimization, a new variant of bin packing problem has been defined. And we propose to integrate its resolution in a decision making tool

Interval graphs are well studied structures. Intervals can represent resources like jobs to be sched-uled. Finding maximum independent set in interval graphs would correspond to scheduling maximum number of non-conflicting jobs on the computer. Most optimization problems on interval graphs like independent set, vertex cover, dominating set, maximum clique, etc can be solved efficiently using combinatorial algorithms in polynomial time. Hitting, Covering and Packing problems have been ex-tensively studied in the last few decades and have applications in diverse areas. While they are NP-hard for most settings, they are polynomial solvable for intervals. In this thesis, we consider the generaliza-tions of hitting, covering and packing problems for intervals. We model these problems as min-cost flow problems using non-trivial reduction and solve it using standard flow algorithms. Demand-hitting problem which is a generalization of hitting problem is defined as follows: Given N intervals, a positive integer demand for every interval, M points, a real weight for every point, select a subset of points H, such that every interval contains at least as many points in H as its demand and sum of weight of the points in H is minimized. Note that if the demand is one for all intervals, we get the standard hitting set problem. In this case, we give a dynamic programming based O(M + N) time algorithm assuming that intervals and points are sorted. A special case of the demand-hitting set is the K-hitting set problem where the demand of all the intervals is K. For the K-hitting set problem, we give a O(M2N) time flow based algorithm. For the demand-hitting problem, we make an assumption that no interval is contained in another interval. Under this assumption, we give a O(M2N) time flow based algorithm. Demand-covering problem which is a generalization of covering problem is defined as follows: Given N intervals, a real weight for every interval, M points, a positive integer demand for every point, select a subset of intervals C, such that every point is contained in at least as many intervals in C as its demand and sum of weight of the intervals in C is minimized. Note that if the demand of points are one, we get the standard covering set problem. In this case, we give a dynamic programming based O(M + N log N) time algorithm assuming that points are sorted. A special case of the demand-covering set is the K-covering set problem where the demand of all the points is K. For the K-covering set problem, we give a O(MN2) time flow based algorithm. For the demand-covering problem, we give a O(MN2) time flow based algorithm. K-pack points problem which is a generalization of packing problem is defined as follows: Given N intervals, an integer K, M points, a real weight for every point, select a subset of points Y , such that every interval contains at most K points from Y and sum of weight of the points in Y is maximized. Note that if K is one, we get the standard pack points problem. In this case, we give a dynamic pro-gramming based O(M + N) time algorithm assuming that points and intervals are sorted. For K-pack points problem, we give O(M2 log M) time flow based algorithm assuming that intervals and points are sorted.

Un problème courant en logistique, gestion d’entrepôt, industrie manufacturière ou gestion d’énergie dans les centres de données est de placer des objets dans un espace limité, ou conteneur. Ce problème est appelé problème de placement. De nombreux travaux dans la littérature gèrent le problème de placement en considérant des objets de formes particulières ou en effectuant des approximations polygonales. L’objectif de cette thèse est d’autoriser toute forme qui admet une définition mathématique (que ce soit avec des inégalités algébriques ou des fonctions paramétrées). Les objets peuvent notamment être courbes et non-convexes. C’est ce que nous appelons le problème de placement générique. Nous proposons un cadre de résolution pour résoudre ce problème de placement générique, basé sur les techniques d’intervalles. Ce cadre possède trois ingrédients essentiels : un algorithme évolutionnaire plaçant les objets, une fonction de chevauchement minimisée par cet algorithme évolutionnaire (coût de violation), et une région de chevauchement qui représente un ensemble pré-calculé des configurations relatives d’un objet (par rapport à un autre) qui créent un chevauchement. Cette région de chevauchement est calculée de façon numérique et distinctement pour chaque paire d’objets. L’algorithme sous-jacent dépend également du fait qu’un objet soit représenté par des inégalités ou des fonctions paramétrées. Des expérimentations préliminaires permettent de valider l’approche et d’en montrer le potentiel. / A common problem in logistic, warehousing, industrial manufacture, newspaper paging or energy management in data centers is to allocate items in a given enclosing space or container. This is called a packing problem. Many works in the literature handle the packing problem by considering specific shapes or using polygonal approximations. The goal of this thesis is to allow arbitrary shapes, as long as they can be described mathematically (by an algebraic equation or a parametric function). In particular, the shapes can be curved and non-convex. This is what we call the generic packing problem. We propose a framework for solving this generic packing problem, based on interval techniques. The main ingredients of this framework are: An evolutionary algorithm to place the objects, an over lapping function to be minimized by the evolutionary algorithm (violation cost), and an overlapping region that represents a pre-calculated set of all the relative configurations of one object (with respect to the other one) that creates an overlapping. This overlapping region is calculated numerically and distinctly for each pair of objects. The underlying algorithm also depends whether objects are described by inequalities or parametric curves. Preliminary experiments validate the approach and show the potential of this framework.

Problemas de corte e empacotamento de itens irregulares são problemas que visam determinar um leiaute ótimo de objetos pequenos dentro de objetos maiores, a fim de atender a uma demanda. Estes problemas têm grande importância prática, já que surgem em vários tipos de indústria (como a têxtil, a de móveis e a de calçados). O problema estudado neste trabalho é o problema de corte de itens irregulares em recipientes. Os recipientes são delimitados e o objetivo é encontrar um leiaute dos objetos menores, sem sobreposição, dentro dos objetos maiores utilizando a menor quantidade de recipientes. Propomos um novo método de resolução para o problema. Nosso método é um algoritmo que gerencia um conjunto de heurísticas, de baixo nível, específicas para a resolução do problema com recipientes retangulares e irregulares. Recipientes irregulares são polígonos convexos e não convexos, que podem ser furados. As heurísticas desenvolvidas utilizam uma malha de pontos sobre a técnica de no-fit polygon para evitar a sobreposição dos itens e encontrar posições viáveis no recipiente retangular ou irregular. Os experimentos computacionais foram feitos para um grande conjunto de instâncias, de recipientes retangulares e irregulares. Os resultados demonstram a competitividade do método, que obtêm resultados bons e algumas soluções ótimas, em um tempo computacional aceitável. / Cutting and packing of irregular items are problems that aim to determine the optimum layout of small objects within larger objects (that we call bins), in order to meet a demand. These problems have great practical importance, since they emerge in various types of industry (such as textile, furniture and shoemaking). The problem studied in this work is the irregular bin packing problem. The bins are enclosed and the goal is to find a layout of items, without overlap, within the bins by using the minimum quantity of them. We propose a new method of resolution to this problem. Our method is an algorithm that manages a set of low-level heuristics, specific to solve the problem with rectangular bins and irregular bins. Irregular bins are convex and non-convex polygons, which may contain holes. The developed heuristics uses a mesh of points and the technique of no-fit polygon to avoid the overlapping of items and find feasible positions in rectangular or irregular bins. The computational experiments were performed for a large set of instances, using both rectangular and irregular bins. The results demonstrate the competitiveness of the method, which can get good results and some optimal solutions within an acceptable computational time.

Olofsfors is a steel product manufacturer in Nordmaling, Sweden, producing steel edges for snowplows, tracks for forest machines, and wear edges for buckets on heavy equipment. Most of their products are heated to 900◦ C and then cooled down in water, so-called quenching, during the hardening process. A group of ovens and quench machines together form an oven system and this is used for the hardening. Since it takes a long time for the ovens to reach operating temperature, they are always kept on, which is why it is important to utilize them as effectively as possible. This project investigates the potential utilization increase of one of the three oven systems in the wear edge production unit. This oven system is part of a production line that consists of a saw and a mill, and can process products up to two meters in length, and is hereon called the two-meter line. The two-meter line has a natural inflow through the saw, but raw material produced in other parts of the factory can also be fetched from another inlet. The use of the other inlet is limited by the operator of the two-meter line who has to fetch the material with a forklift. This could be automated so that the operator would not have to handle this inlet. The purpose is to investigate the potential increases in utilization of the oven system for different degrees of automation in order to make the most of the machines and the operator at the two-meter line. In the end, a recommendation is given with a set of ideal properties of the investment that could improve productivity the most. The main method applied in order to explore the potential use of the oven system is a re-entrant flow shop scheduling model. As preceding steps, the production line is first mapped in order to find potential routes for different product families, then the order quantities in the production data are translated into jobs to be scheduled with the help of packing problems and batching rules. The scheduling model of the production line is then solved heuristically with a genetic algorithm based on the sequence of jobs entering the production line followed by a method for creating a deterministic schedule based on this initial sequence of jobs. Lastly, a sensitivity analysis is applied to the processing time for the steps performed by the operator to evaluate the results' robustness. The conclusion is that there is a substantial potential to increase the utilization of the oven system of the two-meter line. The largest potential is when the operator is not actively working at the production line; a maximum of 15.6 h on average. There does also exist a potential to increase utilization while the operator is working at the production line; a maximum of 3.9 h on average. The automation degree needed is high in both cases but due to different reasons. When the operator is not working, the automatic solution needs to work without supervision for longer periods of time, while, in the other case, it needs to be smart enough to adjust to not disturb the operator’s work. For the future, the recommendation is to focus the next step on finding investment options that could exploit the time when the operator is not working. By further specifying the potential investment alternatives, the cost factor can be added to the analysis as well. / Olofsfors AB är en stålproduktstillverkare i Nordmaling, Sverige, som producerar vägstål till bland annat snöplogar, band till skogsmaskiner och slitstål till entreprenadmaskiner. De flesta av deras produkter hettas upp till 900 C och släcks sedan i vatten under härdningsprocessen. En grupp av ugnar och härdmaskiner kallas tillsammans för ett ungsystem och det används till härdningen. Eftersom det tar lång tid att värma upp ugnarna står de alltid på-slagna och det är därför viktigt att använda dem så effektivt som möjligt.  I detta projekt har potentialen att öka användandet av ett av tre ugnsystem i slitstålsproduktionen undersökts.  Ugnsystemet i fråga är en del av en produktionslinje som också består av en såg och en fräs och kan härda artiklar med längder upp till två meter och kallas därför här tvåmeterslinjen. Den naturliga ingången för råmaterial i produktionslinjen är genom sågen, men det finns även en alternativ ingång för råmaterial som förbehandlats i tidigare produktionssteg i fabriken. Användandet av den andra ingången till produktionlinjen begränsas av att operatören i produktionslinjen måste hämta materialet med truck. Detta in-flöde skulle gå att automatisera så att operatören inte skulle behöva hämta dessa artiklar.  Syftet är att undersöka det potentiella ökade nyttjandet av ugnsystemet för olika grader av automation för att bäst använda maskiner och operatör i tvåmeterslinjen. I slutet ges en rekommendation gällande vilka egenskaper investeringen bör ha för att öka produktiviteten mest.  Huvudmetoden för att undersöka möjligt ökat nyttjande av ugnarna är en schemaläggningsmodel. Som underliggande steg kartläggs först produktionslinjen och de olika rutter som olika produktfamiljer tar genom produktionslinjen. Produktkvantiteterna för varje order i produktionsdatan omvandlas sedan till jobb som kan schemaläggas genom packningsproblem och regler för laststorlekar i de olika maskinerna. Schemaläggningsmodellen löses sedan heuristiskt med hjälp av en genetisk algoritm som bestämmer den initiala sekvensen av jobben i första steget, tillsammans med en deterministisk metod för att skapa ett helt schema baserat på den initiala sekvensen av jobben. Slutligen genomförs en känslighetsanalys på processtiderna för steg som motsvarar operatören för att undersöka hur robust resultatet är.    Slutsatsen är att det finns en stor potential att öka nyttjandet av ugnsystemet i tvåmeterslinjen. Den största potentialen är när operatören inte arbetar aktivt vid produktionslinjen, med ett maximum på ca 15,6 h per dag. Det finns också en möjlighet att utöka nyttjandet av ugnarna under tiden som operatören arbetar aktivt med ordrar och outnyttjad tid då är 3,9 h i genomsnitt. Graden av automation är hög oberoende av vilken tid som ska utnyttjas men på grund av olika anledning. Om tiden då operatören inte aktivt jobbar utnyttjas, måste den automatiserade lösningen fungera autonomt under längre tid. Om den istället förväntas fungera parallellt med operatören måste den anpassas smart så att den inte stör operatörens arbete och flöde. Rekommendationen är att fokusera på att hitta konkreta investeringsalternativ som utnyttjar tiden då operatören inte aktivt arbetar för att få bättre kostnadsunderlag att ha med i den vidare analysen.