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.

O transporte rodoviário é uma das atividades econômicas do homem que mais contribuem para a emissão de Gases de Efeito Estufa (GEE) na atmosfera. Sabe-se que a emissão de CO2 está diretamente vinculada ao consumo de combustível. Por isso, é possível encontrar uma série de trabalhos que objetivam diminuir as emissões por meio da redução do consumo de combustível dos veículos. A otimização de rotas é uma importante ferramenta para essa redução e, consequentemente, possibilita minimizar as emissões dos veículos. Esta pesquisa tem como objetivo aplicar em uma empresa líder na distribuição de revistas no país o PRP, que é um modelo de minimização do consumo de combustível/emissão de GEE por meio de ajustes das variáveis como velocidade média, quantidade de carga transportada, distância percorrida e inclinações das vias. Como a maioria das metodologias de estimativa de combustível existentes na literatura não considera a inclinação das vias nos seus cálculos, neste trabalho foi necessário desenvolver uma metodologia para incluí-la no modelo. Testes foram efetuados com variações nas janelas de tempo, e o modelo mostrou-se sensível a cada uma das variáveis analisadas, gerando economias em 100% das rotas estudadas. / Road transport is one of the biggest contributors of Greenhouse Gases emissions of all humans economic activities. It is known that CO2 emissions are directly related to fuel consumption, so that is why it is possible to find a series of studies that aims to reduce emissions by reducing vehicles fuel consumption. Route optimization is an important tool for reducing fuel consumption and hence emissions. This research aims to implement the PRP model in a leading company in the country, which is a model that minimizes fuel consumption/GHG emissions through adjustments of variables such as average speed, pay load, distance traveled and slopes of the road. Most existing fuel estimation methodologies found in the literature does not consider the slope of the roads in their calculations. So in this research it was necessary to develop a methodology to include it in the model. Tests were performed with variations in the time windows and the model was sensitive to each of the variables analyzed, generating savings on 100% of the studied routes.

Made available in DSpace on 2015-03-05T13:59:42Z (GMT). No. of bitstreams: 0 Previous issue date: 27 / Nenhuma / As escalas de tripulações em companhias aéreas é um fator importante na logística de operações dessas empresas e um problema interessante para a aplicação de Pesquisa operacional. Os custos com tripulantes no transporte aéreo são extremamente altos, superiores a 20% dos custos de operações das empresas. Diante desse contexto, este trabalho vem abordar o problema de rotações de tripulações em empresas aéreas. Uma rotação de tripulação – crew pairings – é uma seqüência de etapas ou segmentos de vôo que começam e terminam em uma base domiciliar de tripulantes. O objetivo deste planejamento é encontrar um subconjunto dessas rotações com custo mínimo e que cubra todas as etapas de vôo na programação da empresa atendendo as restrições inerentes ao problema. O trabalho desenvolveu uma solução para o problema com um modelo set covering/set partitioning, primeiramente, promovendo, uma solução inicial viável que foi aplicada, numa segunda etapa, a um processo de otimização utilizando a meta-heurística Busca Tabu e jan / The flight scheduling crews in airliners are an important factor in logistic of operations of a these companies and interesting problem for the application of Operational Research. The costs with crew members in the air transportation are extremely high, superior 20% of the costs of operations of the companies. So, this study presents an approach of the crew pairing problem in airlines. The objective of this planning is to find a subgroup of these pairings with minimum cost and that it covers all the flight legs in the programming of the airliners taking care of the inherent restrictions to the problem. The solution for the problem implemented a set covering/set partitioning model, first, promoting, a viable initial solution that was applied, in one second stage, to optimize process using the meta-heuristic Tabu Search and time windows. The results had disclosed values satisfactory, demonstrating solutions that, compared with the real solution, had promoted minimization indices superior 70%. The validation

Este trabalho apresenta um estudo teórico da Técnica de Geração de Colunas (GC) aplicada em alguns Problemas de Roteamento de Veículo (PRV). Essa técnica foi inicialmente utilizada para tratar problemas de otimização de grande porte com estruturas especiais[Dantzig & Wolfe, 1960]. Dentre as diversas classes de problemas de roteamento; revisamos a aplicação dessa técnica a dois casos particulares: O problema de roteamento de helicópteros em plataformas marítimas, cujo objetivo minimizar o custo total do transporte; O problema de roteamento com janela de tempo, onde a função objetivo é descrita pelo tamanho da frota e o custo do percurso. Revisamos e implementamos um algoritmo de caminho mínimo com janela de tempo (CMJT). Esse algoritmo surge como um sub-problema do algoritmo Primai Simplex para resolver o problema de partição de conjunto, utilizado para modelar o problema de roteamento com janela de tempo. / This work presents a study about the Column Generation Technique (CG) applied to some Vehicle Ftouting Problems. The technique was first used to deal with optimization problems having special structures. Among the vaa-ious classes of routing problems, we review the use of the technique in two specific cases: Ftouting helicopters for crew exchanges on off-shore locations, where the objective is to minimize the total transportation cost; Ftouting with time windows, where the objective function is composed by the size of the fleet and the cost of route. We review and implement a shortest path algorithm with time windows. This algorithm aa-ises as a sub-problem in the Primai Simplex algorithm to solve the linear relaxation of the set partitioning problem used to model the routing problem with time windows.

La performance logistique des entreprises et l’optimisation des transports sont devenues un grand problème ces dernières années. La planification et l’optimisation des services constituent en particulier un nouveau défi. Afin d’accroître la productivité et de réduire les coûts de la logistique, ce travail de recherche contribue à l’optimisation d’un problème de tournées de service à domicile multi-dépôt, multi-période avec fenêtres de temps de vie réelle. Le problème vient d’un contexte réaliste et est formulé comme un modèle en Mixed Integer Programming (MIP). Les résultats avec Cplex montrent que ce problème ne peut être résolu par des méthodes exactes dans un délai raisonnable pour une utilisation pratique. Par conséquent, nous introduisons des heuristiques. Premièrement, les heuristiques de recherche locales sont utilisées pour résoudre le problème. Les solutions réalisables initiales sont générées par une heuristique de construction et plusieurs heuristiques de recherche locales sont appliquées pour obtenir des solutions dans un temps de calcul assez court. Ensuite, nous proposons un algorithme génétique avec une nouvelle représentation du chromosome et de nouveaux opérateurs génétiques pour le problème abordé. Enfin, nous considérons un algorithme génétique avec contrôle de la diversité pour problèmes à grande échelle. Les solutions infaisables sont prises en compte dans la population et la contribution à la diversité fait partie de l’évaluation afin d’éviter une recherche prématurée. Ces méthodes ont été mises en œuvre avec succès pour optimiser le problème de routage. / The logistics performance of enterprises and the optimization of transportation have become a great issue in recent years. Field force planning and optimization is a new challenge for the service sector. In order to increase productivity and reduce cost of logistics, this research contributes to the optimization of a real-life multi-depot multi-period field service routing problem with time window. The problem is abstracted from the realistic problem and formulated as a Mixed Integer Programming (MIP) model. Computational results with Cplex show that this problem cannot be solved by exact methods in reasonable time for practical use. First, local search heuristics are used for solving the problem. Initial feasible solutions are generated by a constructive heuristic and several local search heuristics are applied to obtain solutions in a very short computing time. Then we propose a genetic algorithm with new representation of chromosome and new genetic operators for the addressed problem. Finally we consider a genetic algorithm with diversity control to deal with large scale problems. Infeasible solutions are taken account in the population and the diversity contribution is part of the evaluation to avoid premature of search. These methods have been successfully implemented to the optimization of the routing problem

No presente trabalho, é abordada a operação de transporte de cargas fracionadas, especificamente a determinação de quais linhas de transporte deverão ser ofertadas dentro de uma rede de terminais, de maneira a atender toda a demanda no nível de serviço desejado ao menor custo possível. Para tanto, é feita inicialmente uma descrição do problema de transporte de carga fracionada, seguido de uma revisão bibliográfica de trabalhos anteriores que já tenham abordado o tema. É então realizada a delimitação do escopo do estudo e a proposição de um modelo matemático em programação linear inteira-mista. Em seguida, é apresentado um algoritmo de resolução, consistindo na aplicação de uma heurística construtiva e uma heurística de melhoria, ambas embasadas na aplicação de caminhos mínimos com janelas de tempo a partir de custos marginais. O método é delineado para três versões do problema, estipuladas a partir de diferentes tratamentos à restrição de caminhos em formato de árvore dentro do sistema. Primeiramente, o algoritmo é aplicado a pequenas instâncias fictícias, realizando a comparação com a modelagem em programação linear inteira-mista proposta. Na maioria dos casos, não houve diferença nos valores de função objetivo encontrados, embora tenham sido identificados gaps grandes no processamento. Posteriormente, é realizada a aplicação a dados reais de uma transportadora brasileira. Para as três versões do problema, a redução de custos potencial identificada é significativa, com tempos de processamento similares ou menores do que o encontrado na literatura. Por fim, os resultados obtidos são discutidos sendo apresentadas considerações finais acerca do trabalho realizado e possíveis melhorias para pesquisas futuras. / At the present work, the operation of less-than-truckload (LTL) will be studied, more specifically the determination of which lines will be offered in a network of terminals. The service network design must attend all demands, respecting their deadlines while aiming cost reductions. The objective of this work is to propose algorithms to solve the service network design problem of LTL operations, reducing operation costs while respecting specified service levels. First, a brief introduction to the problem is made, and similar research is reviewed. Then the scope of the research is determined and a mathematical model of the problem in mixed-integer programming is presented. Next, an algorithm is proposed, consisting in a constructive heuristic followed by a local search. Both phases are based on finding minimum paths with time windows using marginal costs along the network. Three different versions of the problem are analyzed, shifting the approach given to the constraint of in-tree structure that shipments should follow in the network. The algorithm is firstly tested to small fictional instances, allowing comparison to the mixed programming model proposed earlier. No relevant differences between objective functions were found, even though substantial gaps values were identified during processing. A second test used a real dataset of a Brazilian LTL carrier. In all versions of the problem the operation cost reduction was promising, with processing times similar to the ones found in literature. The conclusion provides a discussion of the obtained results and recommendations for future research.

Thesis (MScEng)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: Society is continually in search of ways to optimise various objectives. When faced with multiple and con icting objectives, humans are in need of solution techniques to enable optimisation. This research is based on a recent venture in the eld of multi-objective optimisation, the use of the cross-entropy method to solve multi-objective problems. The document provides a brief overview of the two elds, multi-objective optimisation and the cross-entropy method, touching on literature, basic concepts and applications or techniques. The application of the method to two problems is then investigated. The rst application is to the multi-objective vehicle routing problem with soft time windows, a widely studied problem with many real-world applications. The problem is modelled mathematically with a transition probability matrix that is updated according to cross-entropy principles before converging to an approximation solution set. The highly constrained problem is successfully modelled and the optimisation algorithm is applied to a set of benchmark problems. It was found that the cross-entropy method for multi-objective optimisation is a valid technique in providing feasible and non-dominated solutions. The second application is to a real world case study in blood management done at the Western Province Blood Transfusion Service. The conceptual model is derived from interviews with relevant stakeholders before discrete event simulation is used to model the system. The cross-entropy method is used to optimise the inventory policy of the system by simultaneously maximising the combined service level of the system and minimising the total distance travelled. By integrating the optimisation and simulation model, the study shows that the inventory policy of the service can improve signi cantly, and the use of the cross-entropy algorithm adequately progresses to a front of solutions. The research proves the remarkable width and simplicity of possible applications of the cross-entropy algorithm for multi-objective optimisation, whilst contributing to literature on the vehicle routing problem and blood management. Results on benchmark problems for the vehicle routing problem with soft time windows are provided and an improved inventory policy is suggested to the Western Province Blood Transfusion Service. / AFRIKAANSE OPSOMMING: Die mensdom is voortdurend op soek na maniere om verskeie doelwitte te optimeer. Wanneer die mens konfrontreer word met meervoudige en botsende doelwitte, is oplossingsmetodes nodig om optimering te bewerkstellig. Hierdie navorsing is baseer op 'n nuwe wending in die veld van multi-doelwit optimering, naamlik die gebruik van die kruisentropie metode om multi-doelwit probleme op te los. Die dokument verskaf 'n bre e oorsig oor die twee velde { multi-doelwit optimering en die kruis-entropie-metode { deur kortliks te kyk na die beskikbare literatuur, basiese beginsels, toepassingsareas en metodes. Die toepassing van die metode op twee onafhanklike probleme word dan ondersoek. Die eerste toepassing is di e van die multi-doelwit voertuigroeteringsprobleem met plooibare tydvensters. Die probleem word eers wiskundig modelleer met 'n oorgangswaarskynlikheidsmatriks. Die matriks word dan deur kruis-entropie beginsels opdateer voor dit konvergeer na 'n benaderingsfront van oplossings. Die oplossingsruimte is onderwerp aan heelwat beperkings, maar die probleem is suksesvol modelleer en die optimeringsalgoritme is gevolglik toegepas op 'n stel verwysingsprobleme. Die navorsing het gevind dat die kruis-entropie metode vir multi-doelwit optimering 'n geldige metode is om 'n uitvoerbare front van oplossings te beraam. Die tweede toepassing is op 'n gevallestudie van die bestuur van bloed binne die konteks van die Westelike Provinsie Bloedoortappingsdiens. Na aanleiding van onderhoude met die relevante belanghebbers is 'n konsepmodel geskep voor 'n simulasiemodel van die stelsel gebou is. Die kruis-entropie metode is gebruik om die voorraadbeleid van die stelsel te optimeer deur 'n gesamentlike diensvlak van die stelsel te maksimeer en terselfdetyd die totale reis-afstand te minimeer. Deur die optimerings- en simulasiemodel te integreer, wys die studie dat die voorraadbeleid van die diens aansienlik kan verbeter, en dat die kruis-entropie algoritme in staat is om na 'n front van oplossings te beweeg. Die navorsing bewys die merkwaardige wydte en eenvoud van moontlike toepassings van die kruis-entropie algoritme vir multidoelwit optimering, terwyl dit 'n bydrae lewer tot die afsonderlike velde van voertuigroetering en die bestuur van bloed. Uitslae vir die verwysingsprobleme van die voertuigroeteringsprobleem met plooibare tydvensters word verskaf en 'n verbeterde voorraadbeleid word aan die Westelike Provinsie Bloedoortappingsdiens voorgestel.

Um tema pouco estudado na literatura, mas frequentemente encontrado por empresas prestadoras de serviço, é o Problema de Escalonamento de Técnicos de Campos (Field Technician Scheduling Problem). O problema consiste em associar um número de tarefas - em diversos locais, com diferentes prioridades e com janelas de tempo - a uma quantidade de técnicos - com diferentes horários de expediente e com habilidades distintas - que saem no início do horário de trabalho da sede da empresa, para onde devem retornar antes do fim do expediente. Cada tarefa é atendida por um único técnico. Esse problema é estudado neste trabalho. A primeira parte do trabalho apresenta um modelo de programação linear inteira mista (PLIM) e, dada a complexidade do problema, heurísticas construtivas e meta-heurísticas foram desenvolvidas. Na função objetivo, procura-se principalmente maximizar o número ponderado de tarefas executadas em um dia de trabalho, de acordo com as suas prioridades. Em linhas gerais, as heurísticas construtivas ordenam as tarefas de acordo com um critério pré-estabelecido e, em seguida, designam cada uma a um dos técnicos capazes de realiza-la sem violar as restrições do problema. Tendo em conta o bom desempenho obtido em outros problemas semelhantes, foi adotado um Algoritmo Genético denominado Biased Random-Key Genetic Algorithms (BRKGA), que utiliza chaves aleatórias para codificar e decodificar as soluções. Codificadores e decodificadores adaptados ao problema foram desenvolvidos e testes computacionais são apresentados. As soluções obtidas em problemas de pequenas dimensões são comparadas com as soluções ótimas conhecidas e, para aprimorar a avaliação do desempenho nas instâncias médias e grandes, quatro procedimentos para obter limitantes superiores foram propostos. Testes computacionais foram realizados em 1040 instâncias. O BRKGA encontrou 99% das 238 soluções ótimas conhecidas e, nas 720 instâncias de dimensões médias e grandes, ficou em média a 3,8% dos limitantes superiores. As heurísticas construtivas superaram uma heurística construtiva da literatura em 90% das instâncias. A segunda parte do trabalho apresenta uma nova abordagem para o Problema de Escalonamento de Técnicos de Campo: um modelo biobjetivo, onde uma segunda função objetivo buscará que as tarefas prioritárias sejam realizadas o mais cedo possível. Uma versão multiobjectivo do BRKGA foi desenvolvida, considerando diversas estratégias para classificar a população do algoritmo e escolher as melhores soluções (estratégias de elitismo). Codificadores e decodificadores foram criados para o problema multiobjectivo. Os resultados computacionais obtidos são comparados com os resultados de um Algoritmo Genético conhecido na literatura, o Nondominated Sorting Genetic Algorithm II (NSGA II). Para instâncias de pequenas dimensões, os resultados da meta-heurística proposta também são comparados com a fronteira ótima de Pareto de 234 instâncias, obtidas por enumeração completa. Em média, o BRKGA multiobjectivo encontrou 94% das soluções da fronteira ótima de Pareto e, nas instâncias médias e grandes, superou o desempenho do NSGA-II nas medidas de avaliação adotadas (porcentagem de soluções eficientes, hipervolume, indicador epsílon e cobertura). / An important topic in service companies, but little studied until now, is the field technician scheduling problem. In this problem, technicians have to execute a set of jobs or service tasks. Technicians have different skills and working hours. Tasks are in different locations within a city, with different time windows, priorities, and processing times. Each task is executed by only one technician. This problem is addressed in this thesis. The first part of the research presents the mixed integer linear programming model (MILP) and, due to the complexity of this problem, constructive heuristics and metaheuristics were proposed. The objective function is to maximize the sum of the weighted performed tasks in a day, based on the priority of tasks. In general terms, in the proposed constructive heuristics, jobs are ordered according to a criterion and, after that, tasks are assigned to technicians without violating constraints. A Genetic Algorithm (the Biases Randon Key Genetic Algorithm - -RKGA) is applied to the problem, based on its success in similar problems; the BRKGA uses random keys and a decoder transforms each chromosome of the Genetic Algorithm into a feasible solution of the problem. Decoders and encoders adapted to the problem were developed and computational tests are presented. A comparison between the solutions of the heuristic methods and optimal solutions values was also conducted for small instances and, to analyze medium and large instances, four upper bound models were proposed. Computational experiments with 1040 instances were carried out. The BRKGA reached 99% of the 238 optimal solutions and, for 720 medium and large instances, the average upper bound gap was 3,8%. Constructive heuristics overcame a heuristic of the literature in 90% of the instances. The second part of this research presents a new approach of the Field Technician Scheduling Problem: a multiobjective model, with a second objective function to execute the priority tasks as soon as possible. A multiobjective BRKGA was developed, with different strategies to classify the Genetic Algorithm population and to select the elite solutions (elite strategies). Decoders and encoders were developed for the multiobjective problem too. The results were compared with a known Genetic Algorithm, the Nondominated Sorting Genetic Algorithm II (NSGA II). For 234 small instances, the results were compared with the Pareto optimal solutions, obtained by complete enumeration. On average, the BRKGA found 94% of the Pareto optimal solutions and, for 720 medium and large instances, outperformed the NSGA-II by means of the measures adopted (percentage of efficient solutions, hypervolume, epsilon and coverage).

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.

In this study, three different algorithms are implemented to solve thecapacitated vehicle routing problem with and without time windows:ant colony optimization, a genetic algorithm and a genetic algorithmwith self-organizing map. For the capacitated vehicle routing problemthe Augerat et al’s benchmark problems were used and for the capaci-tated vehicle routing problem with time windows the Solomon’sbenchmark problems. All three algorithms were tuned over thirtyinstances per problem with the tuners SPOT and ParamILS. The tuningresults from all instances were combined to the final parameter valuesand tested on a larger set of instances. The test results were used tocompare the algorithms and tuners against each other. The ant colonyoptimization algorithm outperformed the other algorithms on bothproblems when considering all instances. The genetic algorithm withself-organizing map found more best known solutions than any otheralgorithm when using parameters, on the capacitated vehicle routingproblem. The algorithms performed well and several new best knownresults were discovered for the capacitated vehicle routing problem andnew best solutions found by heuristics were discovered for the 100customer Solomon problems. When comparing the tuners they bothworked well and no clear winner emerged.