Scheduling problem and shift design problems are well known NP-hard problems within the optimization area. Often time, the two problems are studied individually. In this thesis however, we are looking at the combination of both problems. More specifically, the aim of this thesis is to suggest an optimal scheduling policy given that there are no predefined shifts to begin with. The duration of a shift, along with the start and end time may vary. Thus we have proposed to split the problem into two sub-problems: weekly scheduling problem and daily scheduling problem. As there are no exact solution methods that are feasible, two meta-heuristics method has been employed to solve the sub-problems: Simulated Annealing (SA) and Genetic Algorithm (GA). We have provided proofs of concepts for both methods as well as explored the scalability. This is especially important as the number of employee is expected to grow significantly throughout the year. The results obtained has shown to be promising and can be built upon for further capabilities. / Schemaläggning och skiftdesignsproblem är välkända och välstuderade NP-svåra beslutsproblem inom optimeringsområdet. Oftast så studeras dessa problem enskilt, men i detta arbete så studeras en kombination av båda problemen. Mer specifikt är målet med detta arbete att föreslå ett förnuftigt handlingsätt till att skapa ett veckoschema där skift inte är predefinierade för alla veckor. Starttiden, sluttiden och varaktigheten av ett skift kan förändras från vecka till vecka. Därför har problemet delats upp till två delar: Veckoschemaläggnings- och dagsschemaläggningsproblem. Trots uppdelningen så är båda delproblem för komplexa för att lösas exakt. Därför har två metaheuristiska metoder använts som lösningsmetoder: Simulerad Glödgning och Genetisk Algoritm. I detta arbete bevisas båda lösningsmetoderna till att vara bra nog, och dessutom studeras även skalbarheten av modellen. Detta senare är särskilt viktigt eftersom antal anställda som ska schemaläggas förväntas att öka genomåren. De erhållna resultaten har visat sig vara lovande och bevisligen så kan modellen expanderas med er villkor

Studenten und Konstrukteure mit verschiedener konstruktionsmethodischer Ausbildung wurden bezüglich ihres Vorgehens beim Konstruieren und ihrer Konstruktionsleistungen untersucht. Dabei zeigte sich, dass die Wirkung der Ausbildung für drei Teilleistungen (Konzepte erstellen, Konzepte bewerten, Entwürfe erstellen) verschieden ist. Für die konstruktionsmethodischen Empfehlungen für die frühen Phasen wird eine neue Konzeption vorgeschlagen. Der Einfluss kognitiver Variablen (Arbeitsgedächtnis, heuristische Kompetenz, Interferenz) wurde untersucht.

No description available.

De nombreux problèmes en transport et en logistique peuvent être formulés comme des modèles de conception de réseau. Ils requièrent généralement de transporter des produits, des passagers ou encore des données dans un réseau afin de satisfaire une certaine demande tout en minimisant les coûts. Dans ce mémoire, nous nous intéressons au problème de conception de réseau avec coûts fixes et capacités. Ce problème consiste à ouvrir un sous-ensemble des liens dans un réseau afin de satisfaire la demande, tout en respectant les contraintes de capacités sur les liens. L'objectif est de minimiser les coûts fixes associés à l'ouverture des liens et les coûts de transport des produits. Nous présentons une méthode exacte pour résoudre ce problème basée sur des techniques utilisées en programmation linéaire en nombres entiers. Notre méthode est une variante de l'algorithme de branch-and-bound, appelée branch-and-price-and-cut, dans laquelle nous exploitons à la fois la génération de colonnes et de coupes pour la résolution d'instances de grande taille, en particulier, celles ayant un grand nombre de produits. En nous comparant à CPLEX, actuellement l'un des meilleurs logiciels d'optimisation mathématique, notre méthode est compétitive sur les instances de taille moyenne et supérieure sur les instances de grande taille ayant un grand nombre de produits, et ce, même si elle n'utilise qu'un seul type d'inégalités valides. / Many problems in transportation and logistics can be formulated as network design models. They usually require to transport commodities, passengers or data in a network to satisfy a certain demand while minimizing the costs. In this work, we focus on the multicommodity capacited fixed-charge network design problem which consists of opening a subset of the links in the network to satisfy the demand. Each link has a capacity and a fixed cost that is paid if it is opened. The objective is to minimize the fixed costs of the opened links and the transportation costs of the commodities. We present an exact method to solve this problem based on mixed integer programming techniques. Our method is a specialization of the branch-and-bound algorithm, called branch-and-price-and-cut, in which we use column generation and cutting-plane method to solve large-scale instances. We compare our method with CPLEX, currently one of the best solver. Numerical results show that our method is competitive on medium-scale instances and better on large-scale instances.

Le problème de conception de réseaux est un problème qui a été beaucoup étudié dans le domaine de la recherche opérationnelle pour ses caractéristiques, et ses applications dans des nombreux domaines tels que le transport, les communications, et la logistique. Nous nous intéressons en particulier dans ce mémoire à résoudre le problème de conception de réseaux avec coûts fixes et sans capacité, en satisfaisant les demandes de tous les produits tout en minimisant la somme des coûts de transport de ces produits et des coûts fixes de conception du réseau. Ce problème se modélise généralement sous la forme d’un programme linéaire en nombres entiers incluant des variables continues. Pour le résoudre, nous avons appliqué la méthode exacte de Branch-and-Bound basée sur une relaxation linéaire du problème avec un critère d’arrêt, tout en exploitant les méthodes de génération de colonnes et de génération de coupes. Nous avons testé la méthode de Branch-and-Price-and-Cut sur 156 instances divisées en cinq groupes de différentes tailles, et nous l’avons comparée à Cplex, l’un des meilleurs solveurs d’optimisation mathématique, ainsi qu’à la méthode de Branch-and- Cut. Notre méthode est compétitive et plus performante sur les instances de grande taille ayant un grand nombre de produits. / The network design problem has been studied extensively in the field of operational research given its characteristics and applications in many areas such as transportation, communications, and logistics. We are particularly interested in solving the multicommodity uncapacitated fixed-charge network design problem, with the aim of meeting the demands of all the products while minimizing the total cost of transporting commodities and designing the network. This problem is typically modeled as a linear integer program including continuous variables. To solve it, we applied the exact method of Branch-and-bound based on linear relaxation with a stopping criterion, while exploiting the column generation and cutting-plane methods. We tested our Branch-and-Price-and-Cut algorithm on 156 instances divided into five groups of different sizes, and we compared it with Cplex, one of the best mathematical optimization solvers. We compare it also with the Branch-and-Cut method. Numerical results show that our method is competitive and perform better especially on large-scale instances with many commodities.

Submitted by Maicon Juliano Schmidt (maicons) on 2015-06-11T19:24:34Z No. of bitstreams: 1 Débora de Oliveira Lemos Rocha de Souza.pdf: 11262812 bytes, checksum: 1afc26309c47e8dc71f1c5e88aae7409 (MD5) / Made available in DSpace on 2015-06-11T19:24:34Z (GMT). No. of bitstreams: 1 Débora de Oliveira Lemos Rocha de Souza.pdf: 11262812 bytes, checksum: 1afc26309c47e8dc71f1c5e88aae7409 (MD5) Previous issue date: 2015-03-27 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / FAPERGS - Fundação de Amparo à Pesquisa do Estado do Rio Grande do Sul / Algumas ações do processo projetual se restringem aos pensamentos dos designers, gerando uma dificuldade para compreender o processo e torná-lo explícito. As pesquisas nessa área tentam transpor essas limitações, buscando perceber o modo como os designers resolvem os problemas para aprimorar a sua atuação. Esses problemas são caracterizados como mal-estruturados e podem ser vistos de diferentes perspectivas, gerando respostas distintas. O conceito de coevolução percebe a resolução de problemas de forma evolutiva: à medida que compreende-se um pouco mais o problema, as respostas tornam-se mais aprimoradas. Esta dissertação tem como objetivo geral compreender a coevolução do problema de design. Para isso, realizou-se uma pesquisa exploratória em um workshop em design, coletando as informações por meio de grupos focais e do registro, em vídeo, do processo realizado pelos participantes. A técnica utilizada para analisar as informações coletadas nos grupos focais e nos vídeos foi a análise de conteúdo, com algumas adaptações necessárias à pesquisa realizada. Na análise, percebeu-se que a coevolução é influenciada: 1) pela formulação inicial do problema que funciona como uma força motora, impulsionando o processo de resolução do problema; 2) pela forma como as equipes se articulam, levando-se em conta o modo como os integrantes desempenham diferentes papeis e estabelecem um ritmo de resolução do problema de acordo com experiências anteriores que trazem para o projeto; 3) pelos questionamentos em relação ao problema ou à solução, caracterizando-se como uma das estratégias utilizadas pelos designers para avançar no espaço-problema ou no espaço-solução. Concluiu-se, assim, que não só o espaço-problema e o espaço-solução se modificam no percurso do projeto de forma a provocar uma evolução mútua, mas os diversos fatores que envolvem o processo projetual também influenciam na coevolução do problema de design. / Some actions in the design process are restricted to the designers’ thoughts, what may cause some difficulties in understanding the process itself and making it explicit. Studies in this area attempt to overcome these limitations by looking into the way designers solve problems to improve their performance. These problems are usually characterized as ill-structured and can be seen from different perspectives, leading to distinct answers. The concept of co-evolution regards problem resolution in an evolutive manner: as the problem is better understood, the answers become more refined. The overall objective of this work is to understand the co-evolution of the design problem. In order to do this, an exploratory research was conducted within a design workshop, where data was collected by means of both focal groups and videos recording the participants’ process. The technique used to analyse all this data was Content Analysis, with some necessary adaptations to the context of the present research. In the analysis, it was possible to observe that co-evolution is influenced by: 1) the initial formulation of the problem that works as a driving force, boosting the problem resolution process; 2) the way the groups manage themselves, taking into consideration the manner in which different members play distinct roles and establish a problem resolution pace based on previous experiences they bring to the project; and 3) inquiries related to the problem or the solution, which can be regarded as one of the strategies used by designers to move forward into the problem space or the solution space. In conclusion, all these observations lead to the understanding that not only the problem space and the solution space modify themselves in the course of the project, triggering mutual evolution, but the diverse aspects involved in the design context also have some influence on the co-evolution of the design problem.

Studenten und Konstrukteure mit verschiedener konstruktionsmethodischer Ausbildung wurden bezüglich ihres Vorgehens beim Konstruieren und ihrer Konstruktionsleistungen untersucht. Dabei zeigte sich, dass die Wirkung der Ausbildung für drei Teilleistungen (Konzepte erstellen, Konzepte bewerten, Entwürfe erstellen) verschieden ist. Für die konstruktionsmethodischen Empfehlungen für die frühen Phasen wird eine neue Konzeption vorgeschlagen. Der Einfluss kognitiver Variablen (Arbeitsgedächtnis, heuristische Kompetenz, Interferenz) wurde untersucht.

De nombreux problèmes en transport et en logistique peuvent être formulés comme des modèles de conception de réseau. Ils requièrent généralement de transporter des produits, des passagers ou encore des données dans un réseau afin de satisfaire une certaine demande tout en minimisant les coûts. Dans ce mémoire, nous nous intéressons au problème de conception de réseau avec coûts fixes et capacités. Ce problème consiste à ouvrir un sous-ensemble des liens dans un réseau afin de satisfaire la demande, tout en respectant les contraintes de capacités sur les liens. L'objectif est de minimiser les coûts fixes associés à l'ouverture des liens et les coûts de transport des produits. Nous présentons une méthode exacte pour résoudre ce problème basée sur des techniques utilisées en programmation linéaire en nombres entiers. Notre méthode est une variante de l'algorithme de branch-and-bound, appelée branch-and-price-and-cut, dans laquelle nous exploitons à la fois la génération de colonnes et de coupes pour la résolution d'instances de grande taille, en particulier, celles ayant un grand nombre de produits. En nous comparant à CPLEX, actuellement l'un des meilleurs logiciels d'optimisation mathématique, notre méthode est compétitive sur les instances de taille moyenne et supérieure sur les instances de grande taille ayant un grand nombre de produits, et ce, même si elle n'utilise qu'un seul type d'inégalités valides. / Many problems in transportation and logistics can be formulated as network design models. They usually require to transport commodities, passengers or data in a network to satisfy a certain demand while minimizing the costs. In this work, we focus on the multicommodity capacited fixed-charge network design problem which consists of opening a subset of the links in the network to satisfy the demand. Each link has a capacity and a fixed cost that is paid if it is opened. The objective is to minimize the fixed costs of the opened links and the transportation costs of the commodities. We present an exact method to solve this problem based on mixed integer programming techniques. Our method is a specialization of the branch-and-bound algorithm, called branch-and-price-and-cut, in which we use column generation and cutting-plane method to solve large-scale instances. We compare our method with CPLEX, currently one of the best solver. Numerical results show that our method is competitive on medium-scale instances and better on large-scale instances.

No description available.

Tato disertační práce se zabývá vývojem, modelováním a analýzou poptávkově orientovaných úloh, které zahrnují marketingová, operační a logistická rozhodnutí. Úlohy jsou zvoleny tak, aby mohly být dále rozšířeny o koncept tzv. dynamického oceňování a jiných dynamických marketingových rozhodnutí. V práci jsou využity dvě základní poptávkově orientované úlohy: a) úloha kolportéra novin, která je zvolena pro její jednoduchou formu a která tak slouží jako nástroj pro ilustrativní ukázky rozhodovacích procesů v podobných typech úloh, a b) úloha návrhu dopravní sítě, kde jsou využity některé výsledky a znalosti získané při řešení úlohy kolportéra novin. Kolportér (či obecně maloobchodník) čelí náhodné poptávce, která může být postupně ovlivněna oceňováním, marketingovými (tj. reklamními) rozhodnutími a nakonec jejich kombinací. Poptávka obsahuje tedy náhodnou složku, která je pomocí přístupů stochastické optimalizace modelována ve specifickém tvaru (tj. aditivní či multiplikativní tvar). Závislost cena-poptávka je zachycena pomocí nelineární klesající poptávkové funkce, zatímco (vhodná) reklama vede ke zvýšení poptávky (běžně rostoucí s-křivka či konkávní funkce). Výsledky získané při řešení úlohy kolportéra novin s oceňováním jsou následně využity v úloze návrhu dopravní sítě. Tato stochastická úloha je modelována (reformulována) pomocí dvou přístupů stochastické optimalizace: wait-and-see přístup a here-and-now přístup. Jelikož tato implementace vede na lineární či nelineární celočíselnou (navíc scénářovou) úlohu, jsou v práci zmíněny taky výpočetní nástroje. Autor pro řešení používá (původní) tzv. hybridní algoritmus, což je kombinace heuristického (genetického) algoritmu a nástroje optimalizačního softwaru. Potenciální aplikace sestavených modelů, obzvláště v oblasti odpadového hospodářství, jsou diskutovány v závěrečné části disertační práce.