Lean Manufacturing has proven to be a very successful strategy for achieving production efficiencies. The basic elements of lean manufacturing are flow and pull. The traditional methods for establishing flow and pull do not fit well in the realm of high variety low volume manufacturing systems. This thesis provides a general framework for establishing flow and pull in high variety low volume manufacturing systems, through the concept of hybrid flow layouts. The existing analytical procedure for forming hybrid flow layouts is described and a new heuristic procedure, that overcomes some of the limitations of the existing procedure, is proposed. The performance of the new procedure in comparison to the existing procedure is illustrated using a real world case study. Finally, certain practical implementation issues that affect the formation of hybrid flow layouts are provided.

This research aims at a study of the hybrid flow shop problem which has parallel batch-processing machines in one stage and discrete-processing machines in other stages to process jobs of arbitrary sizes. The objective is to minimize the makespan for a set of jobs. The problem is denoted as: FF|batch1, sj|Cmax. The problem is formulated as a mixed-integer linear program. The commercial solver, AMPL/CPLEX, is used to solve problem instances to their optimality. Experimental results show that AMPL/CPLEX requires considerable time to find the optimal solution for even a small size problem, i.e., a 6-job instance requires 2 hours in average. A bottleneck-first-decomposition heuristic (BFD) is proposed in this study to overcome the computational (time) problem encountered while using the commercial solver. The proposed BFD heuristic is inspired by the shifting bottleneck heuristic. It decomposes the entire problem into three sub-problems, and schedules the sub-problems one by one. The proposed BFD heuristic consists of four major steps: formulating sub-problems, prioritizing sub-problems, solving sub-problems and re-scheduling. For solving the sub-problems, two heuristic algorithms are proposed; one for scheduling a hybrid flow shop with discrete processing machines, and the other for scheduling parallel batching machines (single stage). Both consider job arrival and delivery times. An experiment design is conducted to evaluate the effectiveness of the proposed BFD, which is further evaluated against a set of common heuristics including a randomized greedy heuristic and five dispatching rules. The results show that the proposed BFD heuristic outperforms all these algorithms. To evaluate the quality of the heuristic solution, a procedure is developed to calculate a lower bound of makespan for the problem under study. The lower bound obtained is tighter than other bounds developed for related problems in literature. A meta-search approach based on the Genetic Algorithm concept is developed to evaluate the significance of further improving the solution obtained from the proposed BFD heuristic. The experiment indicates that it reduces the makespan by 1.93% in average within a negligible time when problem size is less than 50 jobs.

No description available.

In this dissertation, we investigate the use of lot streaming in a two-stage assembly system and a two-stage hybrid flow shop in order to improve system performance. Lot streaming accelerates the flow of a production lot through a production process by splitting it into sublots, and then, processing these sublots in an overlapping fashion over the machines, thereby reducing work-in-process and cycle-time. Traditionally, lot streaming has been applied to problems in various flow shop machine configurations. It has also been applied to machine environments of job shop, open shop, and parallel machines. Its application to assembly system is relatively new. The two-stage assembly system that we consider consists of multiple suppliers at Stage 1 with each supplier producing one type of a subassembly (or a component), and one or more assembly locations at Stage 2, where the subassemblies are then put together. Lot-attached and sublot-attached setup time and cost are encountered on the machines at both the stages, and sublot-attached time and cost are encountered for the transfer of sublots from Stage 1 to Stage 2. Mass customization is an example of such a system in which the final assembly of a product is postponed to capture specific customer demands. Dell Computer constitutes a real-life example of this system. A customer picks his/her computer processor, memory, storage, and other equipment, on Dell's web site. Dell's supply chain is configured to obtain subassemblies from suppliers (stage 1), and then, to assemble the requisite systems in different market areas (stage 2). This enables a reduction in operating cost while improving responsiveness to customers. The problem that we address is as follows: Given a maximum number of sublots of each lot, determine the number of sublots to use (assuming equal sublot sizes), and also, the sequence in which to process the lots, in order to minimize two criteria, namely, makespan, total cost. We propose two column generation-based methods that rely on different decomposition schemes. The results of our computational investigation conducted by using randomly generated data sets reveal that the proposed column generation methods obtain solutions in a few seconds of CPU time while the direct solution by CPLEX of a mixed integer programming model of the problem requires much larger CPU times. For the hybrid flow shop lot streaming problem, the machine configuration that we consider consists of one machine at Stage 1 and two machines at Stage 2 (designated as 1+2 system). A single lot is to be processed in the system, and the objective is to minimize the makespan. A removal time is associated with each sublot at Stage 1. We present a mixed integer programming model for this problem to determine optimal number of sublots and sublot sizes. First, we consider the case of a given number of sublots for which we develop closed-form expressions to obtain optimal, continuous sublot sizes. Then, we consider determination of optimal number of sublots in addition to their sizes. We develop an upper bound on optimal number of sublots, and use a simple search procedure in conjunction with the closed-form expressions for sublot sizes to obtain an optimal solution. We also consider the problem of determining integer sublot sizes, and propose a heuristic method that directly solves the mixed integer programming model after having fixed values of appropriate variables. The results of our numerical experimentation reveal the efficacy of the proposed method to obtain optimal, continuous sublot sizes, and also, that of the proposed heuristic method to obtain integer sublot sizes, which are within 0.2% of optimal solutions for the testbed of data used, each obtained within a few seconds of CPU time. The last problem that we address is an extension of the single-lot lot streaming problem for a $1+2$ hybrid flow shop considered above to the case of multiple lots, where each lot contains items of a unique product type. We consider two objectives: minimize makespan, and minimize the sum of the completion times for all the lots. The consideration of multiple lots introduces a complicating issue of sequencing the lots. We use the results derived for the single-lot problem and develop effective heuristic methods for this problem. The results of our computational investigation on the use of different heuristic methods reveal their efficacy in solving this problem. / Ph. D.

Profiling techniques to detect performance bugs in applications are usually customized to detect a specific bug pattern and involve significant engineering effort. In spite of this effort, many techniques either suffer from high runtime overheads or are imprecise. This necessitates the design of a common and efficient instrumentation substrate that profiles the flow of objects during an execution. Designing such a substrate which enables profile generation precisely with low overhead is non-trivial due to the number of objects created, accessed and paths traversed by them in an execution. In this thesis, we design and implement an efficient instrumentation substrate that efficiently generates object flow profiles for Java programs, without requiring any modifications to the underlying virtual machine. We achieve this by applying Ball-Larus numbering on a specialized hy-brid ow graph (hfg). The hfg path profiles that are collected during runtime are post-processed o ine to derive the object flow profiles. We extend the design to handle inter-procedural objec flows by constructing flow summaries for each method and incorporating them appropriately. We have implemented the substrate and validated its efficacy by applying it on programs from popular benchmark suites including dacapo and java-grande. The results demonstrate the scalability of our approach, which handles 0.2M to 0.55B object accesses with an average runtime overhead of 8x. We also demonstrate the effectiveness of the generated profiles by implementing three client analyses that consume the profiles to detect performance bugs. The analyses are able to detect 38 performance bugs which when refactored result in signi cant performance gains (up to 30%) in running times.

Abstract Optimizing the use of resources plays an important role in today’s modern manufacturing and service organizations. Scheduling, involving setup times and costs, leads to better allocation of resources over time to perform a collection of required tasks. This compilation dissertation examines how the learning effect of workers and a combination of setup activities can be used to optimize resource utilization in manufacturing systems and maintenance services. The learning effect is a technique that can model improvement in worker’s ability as a result of repeating similar tasks. By considering the learning effect, setup times will be reduced, and a schedule can be determined to place jobs that share similar tools and fixtures next to each other. The purpose is to schedule a set of jobs in a hybrid flow shop environment while minimizing two criteria that represent the manufacturers’ and consumers’ concerns: namely maximum completion time (makespan) and total tardiness. Combining setup activities can also reduce setup times and costs. In the maintenance of systems consisting of multiple components, costs can be saved when several components are jointly maintained. By using this technique, a schedule can be determined to minimize the total cost of maintenance and renewal projects for various components and their relevant setup activities. Mathematical programming models that incorporate these aspects of the problem are developed in this research and the performance of the proposed models are tested on a set of problem instances. The results of this work show that the proposed techniques perform well in reducing setup times and costs and eliminate the need for setups through scheduling. This work proposes several exact, heuristic, and meta-heuristic methods to solve the developed models and compare their efficiency. This study contributes to the theoretical discussion of multi-criteria production and maintenance scheduling. For practitioners, this dissertation work provides optimization techniques and tools through scheduling that can help keep costs down and allow companies to operate according to time and budget constraints. / Tiivistelmä Resurssien käytön optimoinnilla on tärkeä rooli nykypäivän tuotanto- ja palveluympäristöissä. Joukko tehtäviä voidaan toteuttaa resurssitehokkaammin niille varatussa ajassa huomioimalla aikataulutuksessa asetusajat ja –kustannukset. Tämä kokoomaväitöskirja tarkastelee, kuinka työntekijöiden oppimisefektin mallinnus ja asetustoimien yhdistäminen tukevat resurssien optimointia tuotantojärjestelmissä ja kunnossapitopalveluissa. Oppimisefekti on tekniikka, jolla voidaan mallintaa työntekijän osaamisen kehittymistä samankaltaisia työtehtäviä toistettaessa. Huomioimalla oppimisefekti asetusaikoja voidaan pienentää, ja töille luoda aikataulu jossa samankaltaiset työkalut ja laitteet ovat lähellä toisiaan. Osana väitöskirjaa esitetään työerän aikataulutus tietyssä yksittäistuotantoympäristössä minimoiden kahta kriteeriä: valmistajan tavoite kokonaisläpimenoaika ja asiakkaan tavoite yksittäisten töiden aikataulussa valmistuminen. Toinen väitöskirjassa esitetty tekniikka asetusaikojen ja –kustannusten pienentämiseen on asetustöiden yhdistely. Useista komponenteista koostuvassa systeemissä kustannussäästöjä voidaan saavuttaa huoltamalla useita komponentteja yhtä aikaa. Tämän yhdistelyn avulla voidaan luoda aikataulu, joka minimoi useiden komponenttien ylläpidon, uusimisen, ja asetuskustannusten kokonaiskustannuksen. Työssä mallinnetaan näitä tekniikoita matemaattisen ohjelmoinnin keinoin, ja luotuja malleja testataan joukolla esimerkkiongelmia. Väitöskirjan tulokset osoittavat, että ehdotetuilla tekniikoilla voidaan vähentää asetusaikoja ja –kustannuksia, tai poistaa asetustöistä aiheutuvia kustannuksia kokonaan. Siinä esitetään useita eksakteja, heuristisia ja metaheuristisia menetelmiä kehitettyjen mallien ratkaisuun ja niiden suorituskyvyn vertailuun. Työn tulokset edistävät tieteellistä keskustelua monikriteeriskeduloinnin alalla, erityisesti liittyen tuotanto- ja kunnossapitosysteemeihin. Käytännön toimijoille väitöskirja tarjoaa optimointitekniikoita- ja työkaluja aikataulutukseen ja sen kautta taloudellisissa ja ajallisissa rajoitteissa toiminnan mahdollistamiseen.

In this article, we propose a new grid-free and exact solution method for computing solutions associated with an hybrid traffic flow model based on the Lighthill- Whitham-Richards (LWR) partial differential equation. In this hybrid flow model, the vehicles satisfy the LWR equation whenever possible, and have a fixed acceleration otherwise. We first present a grid-free solution method for the LWR equation based on the minimization of component functions. We then show that this solution method can be extended to compute the solutions to the hybrid model by proper modification of the component functions, for any concave fundamental diagram. We derive these functions analytically for the specific case of a triangular fundamental diagram. We also show that the proposed computational method can handle fixed or moving bottlenecks.

The sponsor of the thesis is the Composite Unit of AIRBUS Nantes plant, which manufactures aircraft composite. The basic process to manufacture composite parts is to lay-up raw composite material on a tool and involves very costly means and raw material. This process can be modeled as a two-stage hybrid flow shop problem with specific constraints, particularly prescription constraints on the jobs. This thesis restates the practical problem as a scheduling problem by doing hypotheses and restrictions. Then, it designs a mathematical model based on time-indexed variables. This model has been implemented in an IP solver to solve real based scenarios. A heuristic algorithm is developed for obtaining good solutions quickly. Finally, the heuristic is used to increase the execution speed of the IP solver. This thesis concludes by a discussion on the advantages and disadvantages of each option (IP solver vs. heuristic software) for the sponsor. / Master of Science

Este trabalho trata do problema de programação de operações no ambiente flow shop com máquinas múltiplas, com seus tempos de preparação (setup) assimétricos e dependentes da seqüência de processamento das tarefas. Este ambiente de produção é comum em indústrias gráficas, químicas, têxteis, de papel e de tinta, caracterizadas por sistemas com amplo mix de produtos. Qualquer processo produtivo requer um gerenciamento eficaz por meio do Planejamento e Controle da Produção (PCP). Esta atividade inclui a programação da produção, ou seja, a alocação de recursos para a execução de tarefas em uma base de tempo. A atividade de programação é uma das tarefas mais complexas no gerenciamento de produção, pois há a necessidade de lidar com diversos tipos diferentes de recursos e atividades simultaneamente. Além disso, o número de soluções possíveis cresce exponencialmente em várias dimensões, de acordo com a quantidade de tarefas, operações ou máquinas, conferindo uma natureza combinatorial ao problema. No ambiente estudado neste trabalho as operações de cada tarefa são executadas em múltiplos estágios de produção, podendo variar a quantidade de máquinas em cada um deles. Cada operação é processada por apenas uma máquina em cada estágio. Os tempos de preparação das máquinas possuem uma variabilidade relevante em função da ordem de execução das tarefas nas máquinas. A função-objetivo considerada é a minimização da duração total da programação (makespan). Foram desenvolvidos quatro métodos heurísticos construtivos com base em algoritmos reportados na literatura para solução de problemas flow shop permutacional e máquinas paralelas no ambiente cujo tempo de setup é dependente da seqüência. Como não foram encontrados na literatura métodos para programação no ambiente tratado neste trabalho, os algoritmos construídos foram comparados entre si. O foco da pesquisa foi o estudo da influência da relação entre as ordens de grandeza dos tempos de processamento e de setup em cada método de solução. Os resultados obtidos na experimentação computacional foram analisados e discutidos com base na porcentagem de sucesso, desvio relativo (%), desvio-padrão do desvio relativo e tempo médio de computação / This work adressess the hybrid flow shop scheduling problem with asymmetric sequence dependent setup times. This environment of production system is common in graphical, chemical, fabric, paper and ink industries. It’s characterized by systems with large mix of products. Any productive process requires an efficient management by means of Production Planning and Control. This activity includes scheduling, i.e., the resources allocation for the execution of jobs in a time base. Scheduling is one of the tasks most complex in production management, since it deals simultaneously with different types of resources and activities. Moreover, the number of possible solutions grows exponentially in some dimensions, in accordance with the number of jobs, operations or machines, conferring a combinatorial nature to the problem. In the environment studied in this work, the operations of each job are processed in multiple production stages. The number of machines in each stage can be different. Each operation is processed by only one machine in each stage. The setup times have a significant variability in function of the sequence of job processing on the machines. The objective is minimizing the total time to complete the schedule (makespan). Four constructive heuristic methods were developed on the basis of algorithms reported in the literature for solving permutation flow shop and parallel machine problems with sequence dependent setup times. The proposed heuristic methods have been compared between themselves, since no constructive heuristics have been found in the literature for the scheduling problem considered in this work. The focus of the research was the study of the influence of the relations among the range of the times processing and setup times in each method. The statistics used in order to evaluate the heuristic performances were the percentage of success (in finding the best solution), relative deviation, standard deviation of relative deviation and average computation time. Results from computational experience are discussed

A teoria de programação da produção preocupa-se em fornecer diretrizes e métodos eficientes para a utilização dos recursos nas atividades produtivas. Este trabalho investiga o problema de programação da produção em ambientes flow shop com máquinas múltiplas e tempos de preparação das máquinas assimétricos e dependentes da seqüência de execução das tarefas. A atividade de programação da produção constitui uma das várias funções executadas pelo planejamento e controle da produção, que tem como objetivo comandar e gerenciar o processo produtivo, e caracteriza uma das atividades mais complexas no gerenciamento dos sistemas produtivos. A programação da produção preocupa-se com a alocação de recursos sobre o tempo para executar um conjunto de tarefas. No ambiente estudado neste trabalho as operações de cada tarefa são executadas em múltiplos estágios de produção, podendo variar a quantidade de máquinas em cada um deles. Cada operação é processada por apenas uma máquina em cada estágio. Os tempos de preparação das máquinas possuem uma variabilidade relevante em função da ordem de execução das tarefas nas mesmas. A função-objetivo considerada é a minimização do tempo médio de fluxo. Foram desenvolvidos quatro métodos heurísticos construtivos com base em algoritmos reportados na literatura para solução do problema flow shop permutacional e máquinas paralelas cujo tempo de setup é dependente da seqüência de execução das tarefas. Como não foram encontrados na literatura métodos de solução para o problema investigado neste trabalho, os algoritmos propostos foram comparados entre si. Foi efetuado um estudo da influência da relação entre as ordens de grandeza dos tempos de processamento das tarefas e do setup das máquinas em cada método de solução. Os resultados obtidos na experimentação computacional foram analisados e discutidos com base na porcentagem de sucesso, desvio relativo, desvio-padrão do desvio relativo e tempo médio de computação. / Scheduling theory attempts to provide guidelines and efficient methods to the use of the resources in the productive activities. This study investigates the hybrid flow shop problem with asymmetric sequence dependent setup times. The activity of production scheduling constitute is one of the several functions carried by production planning and control, which has as the objective command and management the production system, and characterize is one of the tasks most complex in production management. This activity of the scheduling aims within the allocation of the resources for the execution of jobs in a time base. In the environment studied in this work, the operations of each job are processed in multiple production stages. The number of machines in each stage can be different. Each operation is processed by only one machine in each stage. The setup times have a significant variability in function of the sequence of job processing on the machines. The objective is minimizing the mean flow time. Four constructive heuristic methods were proposed on the basis of algorithms reported in the literature for solving permutation flow shop and parallel machine problems with sequence dependent setup times. The proposed heuristic methods will have compared between themselves, since no constructive heuristics have been found in the literature for the scheduling problem considered in this work. It was carried out the study of the influence of the relations among the range of the times processing and setup times in each method. The statistics used in order to evaluate the heuristic performances were the percentage of success (in finding the best solution), relative deviation, standard deviation of relative deviation and average computation time. Results from computational experience are discussed.