published_or_final_version / abstract / Industrial and Manufacturing Systems Engineering / Master / Master of Philosophy

Ngo-Tai Fong. / Thesis (Ph.D.)--Chinese University of Hong Kong, 1996. / Includes bibliographical references (leaves 158-168). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Manufacturing Systems: An Overview --- p.1 / Chapter 1.2 --- Previous Research --- p.3 / Chapter 1.3 --- Motivation --- p.5 / Chapter 1.4 --- Outline of the Thesis --- p.8 / Chapter 2 --- Preliminaries --- p.11 / Chapter 2.1 --- Problem Formulation: Deterministic Production Planning --- p.11 / Chapter 2.2 --- Markov Chain --- p.15 / Chapter 2.3 --- Problem Formulation: Stochastic Production Planning --- p.18 / Chapter 2.4 --- Some Lemmas --- p.24 / Chapter 3 --- Open-Loop Production Planning in Stochastic Flowshops --- p.26 / Chapter 3.1 --- Introduction --- p.26 / Chapter 3.2 --- Limiting Problem --- p.29 / Chapter 3.3 --- Weak-Lipschitz Continuity --- p.34 / Chapter 3.4 --- Constraint Domain Approximation --- p.41 / Chapter 3.5 --- Asymptotic Analysis: Initial States in Sε --- p.47 / Chapter 3.6 --- Asymptotic Analysis: Initial States in S \ Sε --- p.61 / Chapter 3.7 --- Concluding Remarks --- p.70 / Chapter 4 --- Feedback Production Planning in Deterministic Flowshops --- p.72 / Chapter 4.1 --- Introduction --- p.72 / Chapter 4.2 --- Assumptions --- p.75 / Chapter 4.3 --- Optimal Feedback Controls --- p.76 / Chapter 4.3.1 --- The Case c1 < c2+ --- p.78 / Chapter 4.3.2 --- The Case c1 ≥ c2+ --- p.83 / Chapter 4.4 --- Concluding Remarks --- p.88 / Chapter 5 --- Feedback Production Planning in Stochastic Flowshops --- p.90 / Chapter 5.1 --- Introduction --- p.90 / Chapter 5.2 --- Original and Limiting Problems --- p.91 / Chapter 5.3 --- Asymptotic Optimal Feedback Controls for pε --- p.97 / Chapter 5.3.1 --- The Case c1 < c2+ --- p.97 / Chapter 5.3.2 --- The Case c1 ≥ c2+ --- p.118 / Chapter 5.4 --- Concluding Remarks --- p.124 / Chapter 6 --- Computational Evaluation of Hierarchical Controls --- p.126 / Chapter 6.1 --- Introduction --- p.126 / Chapter 6.2 --- The Problem and Control Policies under Consideration --- p.128 / Chapter 6.2.1 --- The Problem --- p.128 / Chapter 6.2.2 --- Hierarchical Control (HC) --- p.131 / Chapter 6.2.3 --- Kanban Control (KC) --- p.133 / Chapter 6.2.4 --- Two-Boundary Control (TBC) --- p.137 / Chapter 6.2.5 --- "Similarities and Differences between HC, KC, and TBC" --- p.141 / Chapter 6.3 --- Computational Results --- p.142 / Chapter 6.4 --- Comparison of HC with Other Polices --- p.145 / Chapter 6.5 --- Concluding Remarks --- p.151 / Chapter 7 --- Conclusions and Future Research --- p.153 / Bibliography --- p.158

by Chu Kwok-Fai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 91-93). / Abstracts in English and Chinese. / List of Figures --- p.vii / List of Tables --- p.viii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Literature Review --- p.4 / Chapter 1.2.1 --- Ordinary Dispatching Policies --- p.5 / Chapter 1.2.2 --- Setup-oriented Dispatching Policies --- p.7 / Chapter 1.3 --- Organization of Thesis --- p.10 / Chapter 2 --- Slack Based Policies --- p.11 / Chapter 2.1 --- Definition of Slack --- p.12 / Chapter 2.2 --- Least Slack Policy (LS) --- p.13 / Chapter 2.3 --- Least Weighted Slack Policy (LWS) --- p.15 / Chapter 2.3.1 --- Definition of Weighted Slack --- p.15 / Chapter 2.3.2 --- Policy Mechanism and Discussion --- p.15 / Chapter 2.4 --- Least Mean Slack Policy (LMS) --- p.16 / Chapter 2.4.1 --- Batch Size and Its Lower Bound --- p.16 / Chapter 2.4.2 --- Policy Mechanism and Discussion --- p.17 / Chapter 2.5 --- Least Weighted Mean Slack Policy (LWMS) --- p.18 / Chapter 2.5.1 --- Definition of Weighted Mean Slack --- p.18 / Chapter 2.5.2 --- Policy Mechanism and Discussion --- p.18 / Chapter 2.6 --- Illustrative Example --- p.21 / Chapter 2.7 --- Due-date Window Expansion --- p.24 / Chapter 2.7.1 --- Due-date Window --- p.24 / Chapter 2.7.2 --- LWMS Policy: Due Date Window Expansion --- p.25 / Chapter 3 --- Simulation Study --- p.27 / Chapter 3.1 --- Models Description --- p.27 / Chapter 3.1.1 --- Two-Machines-Two-Products Model --- p.27 / Chapter 3.1.2 --- Assembly Lines Model --- p.29 / Chapter 3.1.3 --- Micro-Chips Testing Model --- p.31 / Chapter 3.2 --- Simulation Experiment Description --- p.32 / Chapter 4 --- Simulation Result and Analysis --- p.38 / Chapter 4.1 --- Simulation Result --- p.39 / Chapter 4.1.1 --- Two-Machines-Two-Products Model --- p.39 / Chapter 4.1.2 --- Assembly Lines Model --- p.39 / Chapter 4.1.3 --- Micro-Chips Testing Model --- p.43 / Chapter 4.2 --- Statistical Analysis --- p.44 / Chapter 4.2.1 --- Significance of Weighted Factor and Batch Size --- p.44 / Chapter 4.2.2 --- Comparison Among Different Policies --- p.46 / Chapter 4.3 --- Discussion of Results --- p.50 / Chapter 5 --- An Experimental Implementation and Conclusion Remarks --- p.51 / Chapter A --- Reducing MCT and SDCT by LS policy --- p.55 / Chapter A.1 --- Reducing Variance of Lateness --- p.55 / Chapter A.2 --- Reducing Variance of Cycle Time --- p.56 / Chapter A.3 --- Reducing Mean Cycle Time --- p.56 / Chapter B --- Complete Simulation Result --- p.58 / Chapter B.1 --- Two-Machines-Two-Products Model --- p.58 / Chapter B.1.1 --- "Wip, Batch Size and Throughput" --- p.58 / Chapter B.1.2 --- MCT and SDCT --- p.62 / Chapter B.1.3 --- Machine Utilization --- p.66 / Chapter B.2 --- Assembly Lines Model --- p.68 / Chapter B.2.1 --- "WIP, Batch Size and Throughput" --- p.68 / Chapter B.2.2 --- MCT and SDCT --- p.70 / Chapter B.2.3 --- Machine Utilization --- p.73 / Chapter B.3 --- Micro-Chips Testing Model --- p.82 / Chapter B.3.1 --- "WIP, Throughput, MCT and SDCT" --- p.82 / Chapter B.3.2 --- Machine Utilization --- p.84 / Chapter C --- MANOVA studies on Weighted Factor and Batch Size --- p.86 / Chapter C.1 --- Two-Machines-Two-Products Model --- p.86 / Chapter C.1.1 --- Least Weighted Slack Policy --- p.86 / Chapter C.1.2 --- Least Mean Slack Policy --- p.87 / Chapter C.1.3 --- Least Weighted Mean Slack Policy --- p.87 / Chapter C.2 --- Assembly Lines Model --- p.88 / Chapter C.2.1 --- Least Weighted Slack Policy --- p.88 / Chapter C.2.2 --- Least Mean Slack Policy --- p.88 / Chapter C.2.3 --- Least Weighted Mean Slack Policy --- p.89 / Chapter C.3 --- Micro-Chips Testing Model --- p.89 / Chapter C.3.1 --- Least Weighted Slack Policy --- p.89 / Chapter C.3.2 --- Least Mean Slack Policy --- p.90 / Chapter C.3.3 --- Least Weighted Mean Slack Policy --- p.90 / Bibliography --- p.91

The optimal allocation of buffers in serial production systems is one of the oldest and most researched problems in Industrial Engineering. In general, there are three main approaches to the buffer allocation problem when the objective is to maximize throughput. The first is basically a systematic trial and error procedure supported either by discrete event simulation or analytical models. A second approach is to allocate buffers based on general design rules that have been established in the research literature through experimentation. And the third approach is to apply a buffer allocation optimization algorithm to a specific production line. All these approaches have limitations and could be time and resource consuming. Additionally, most of the existing research on buffer allocation only considers production systems modeled with an infinite supply of raw materials before the first workstation and an unlimited capacity for finished goods after the last workstation. In reality many production systems are designed as closed systems where an interaction between the last and the first workstations in the line is present. In a closed production system, there is a finite buffer after the last workstation and the number of "carriers" holding jobs that move through the line is fixed. The objective of this thesis was to develop efficient heuristic algorithms for the buffer allocation problem in closed production systems. Two heuristics for buffer allocation were implemented. Heuristic H 1 uses the idea that highly utilized workstation stages require any available buffer more than sub-utilized stages. Heuristic H2 uses information stored in the longest path of a network representation of job flow to determine where additional buffers are most beneficial. An experiment was designed to determine if there are any statistically significant differences between throughput values with buffer allocations obtained with a genetic algorithm, also developed in this research, and through puts with buffer allocations generated by Hi and H2. Several types of closed production systems were examined in eight different test cases. No significant differences in performance were observed. The efficiency of the heuristics was also analyzed. A significant difference between the speeds of Hi and H2 is found. The analysis performed in this research indicates that heuristic H2 is sufficiently effective and accurate for determining near optimal buffer allocations in closed production systems. / Graduation date: 2005

Process planning and scheduling are two important manufacturing planning functions which are traditionally performed separately and sequentially. Usually, the process plan has to be prepared first before scheduling can be performed. However, due to the complexity of manufacturing systems and the uncertainties and dynamical changes encountered in practical production, process plans and schedules may easily become inefficient or even infeasible. The concept of integrated process planning and scheduling (IPPS) has been proposed to improve the efficiency, effectiveness as well as flexibility of the respective process plan and schedule. By combining both functions together, the process plan for producing a part could be dynamically arranged in accordance with the availability of manufacturing resources and current status of the system, and its operations’ schedule could be determined concurrently. Therefore, IPPS could provide an essential solution to the dynamic process planning and scheduling problem in the practical manufacturing environment. Nevertheless, process planning and scheduling are both complex functions that depend on many factors and flexibilities in the manufacturing system, IPPS is therefore a highly complex NP-hard problem. Ant colony optimization (ACO) is a widely applied meta-heuristics, which has been proved capable of generating feasible solutions for IPPS problem in previous research. However, due to the nature of the ACO algorithm, the performance is not that favourable compared with other heuristics. This thesis presents an enhanced ACO approach for IPPS. The weaknesses and limitations of standard ACO algorithm are identified and corresponding modifications are proposed to deal with the drawbacks and improve the performance of the algorithm. The mechanism is implemented on a specifically designed multi-agent system (MAS) framework in which ants are assigned as software agents to generate solutions. First of all, the manufacturing processes of the parts are graphically formulated as a disjunctive AND/OR graph. In applying the ACO algorithm, ants are deployed to find a path on the disjunctive graph. Such an ant route indicates a corresponding solution with associated operations scheduled by the sequence of ant visit. The ACO in this thesis is enhanced with the novel node selection heuristic and pheromone update strategy. With the node selection heuristic, pheromone is deposited on the nodes as well as edges on the ant path. This is contrast to the conventional ACO algorithm that pheromone is only deposited on edges. In addition, a more reasonable strategy based on “earliest completion time” of operations are used to determine the heuristic desirability of ants, instead of the “greedy” strategy used in standard ACO, which is based on the “shortest processing time”. The approach is evaluated by a comprehensive set of problems with a full set of flexibilities, while multiple performance measurements are considered, including makespan, mean flow time, average machine utilization and CPU time, among which makespan is the major criterion. The results are compared with other approaches and encouraging improvements on solution quality could be observed. / published_or_final_version / Industrial and Manufacturing Systems Engineering / Master / Master of Philosophy

This research focuses on large-scale manufacturing systems having a number of stations with multiple tools and product types with different and deterministic processing steps. The objective is to determine the production quantities of multiple products and the tool requirements of each station that maximizes net profit while satisfying strategic constraints such as cycle times, required throughputs, and investment. The formulation of the problem, named OptiProfit, is a mixed-integer nonlinear programming (MINLP) with the stochastic issues addressed by mean-value analysis (MVA) and queuing network models. Observing that OptiProfit is an NP-complete, nonconvex, and nonmonotonic problem, the research develops a heuristic method, Differential Coefficient Based Search (DCBS). It also performs an upper-bound analysis and a performance comparison with six variations of Greedy Ascent Procedure (GAP) heuristics and Modified Simulated Annealing (MSA) in a number of randomized cases. An example problem based on a semiconductor manufacturing minifab is modeled as an OptiProfit problem and numerically analyzed. The proposed methodology provides a very good quality solution for the high-level design and operation of manufacturing facilities.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O problema de seqüenciamento da produção vem sendo estudado desde o início da década de 50 do século passado e tem recebido nestes últimos cinqüenta anos uma considerável atenção de pesquisadores de todo o mundo. Como resultado atualmente encontra-se disponível uma gama de métodos de otimização e aproximação voltados para solução deste tipo de problema, sendo que a aplicação destes métodos mostra-se limitada à solução de problemas padrões de seqüenciamento, os quais consideram um conjunto de simplificações que os distanciam dos problemas ocorrentes nos ambientes reais de produção. Nesta dissertação o problema de seqüenciamento da produção sob análise trata-se especificamente do problema ocorrente nas micro e pequenas empresas do setor de confecções situadas no município de Nova Friburgo, onde foi constatado que quase não há um planejamento prévio da produção e quando o mesmo ocorre é feito com base somente em informações empíricas sem a aplicação de nenhuma metodologia e sem o auxílio de qualquer ferramenta computacional. Tal falta de planejamento resulta em um mau aproveitamento dos recursos de produção e impede que a empresa possa produzir em maior escala, o que se mostra necessário já que usualmente a demanda supera a capacidade produtiva da maioria das empresas do setor de confecções, principalmente em se tratando do sub-setor de moda íntima o qual abrange a maioria das empresas do município de Nova Friburgo. Visando melhorar o potencial competitivo destas empresas, esta dissertação se propõe a modelar matematicamente o seu processo de produção e desenvolver uma ferramenta computacional para a programação da produção baseada no método Tabu Search. / The manufacturing scheduling problem has been investigated since the 50s of the past century, and has received in the last 50 years a lot of attention from researchers around the world. As a result of such research efforts a lot of approximation and optimization methods are now available for the solution of such problems. Nonetheless, the application of these methods has been limited to standard problems of scheduling which considers a member of simplifications that do not correspond to the practical situations found in real production sets. In the present dissertation the manufacturing scheduling problem is devoted to real small and companies of productions sector of Nova Friburgo, for which has been observed that there is almost no prior production planning made, and when it is performed it is based only on empirical information without the application of a methodology or the aid of a computational tool. Such lack of planning results in a poor use of the production resources and prevents the company to produce in a larger scale, which is necessary because usually the demand is larger than the production capability of the majority of the companies of productions sector, manly in the sub-sector of underwear which corresponds to the majority of the companies of Nova Friburgo. Seeking to enhance the competitive edge of such companies the present dissertation has the purpose of modeling the production process and develop a computational tool for the production scheduling based on the Tabu Search method.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O problema de seqüenciamento da produção vem sendo estudado desde o início da década de 50 do século passado e tem recebido nestes últimos cinqüenta anos uma considerável atenção de pesquisadores de todo o mundo. Como resultado atualmente encontra-se disponível uma gama de métodos de otimização e aproximação voltados para solução deste tipo de problema, sendo que a aplicação destes métodos mostra-se limitada à solução de problemas padrões de seqüenciamento, os quais consideram um conjunto de simplificações que os distanciam dos problemas ocorrentes nos ambientes reais de produção. Nesta dissertação o problema de seqüenciamento da produção sob análise trata-se especificamente do problema ocorrente nas micro e pequenas empresas do setor de confecções situadas no município de Nova Friburgo, onde foi constatado que quase não há um planejamento prévio da produção e quando o mesmo ocorre é feito com base somente em informações empíricas sem a aplicação de nenhuma metodologia e sem o auxílio de qualquer ferramenta computacional. Tal falta de planejamento resulta em um mau aproveitamento dos recursos de produção e impede que a empresa possa produzir em maior escala, o que se mostra necessário já que usualmente a demanda supera a capacidade produtiva da maioria das empresas do setor de confecções, principalmente em se tratando do sub-setor de moda íntima o qual abrange a maioria das empresas do município de Nova Friburgo. Visando melhorar o potencial competitivo destas empresas, esta dissertação se propõe a modelar matematicamente o seu processo de produção e desenvolver uma ferramenta computacional para a programação da produção baseada no método Tabu Search. / The manufacturing scheduling problem has been investigated since the 50s of the past century, and has received in the last 50 years a lot of attention from researchers around the world. As a result of such research efforts a lot of approximation and optimization methods are now available for the solution of such problems. Nonetheless, the application of these methods has been limited to standard problems of scheduling which considers a member of simplifications that do not correspond to the practical situations found in real production sets. In the present dissertation the manufacturing scheduling problem is devoted to real small and companies of productions sector of Nova Friburgo, for which has been observed that there is almost no prior production planning made, and when it is performed it is based only on empirical information without the application of a methodology or the aid of a computational tool. Such lack of planning results in a poor use of the production resources and prevents the company to produce in a larger scale, which is necessary because usually the demand is larger than the production capability of the majority of the companies of productions sector, manly in the sub-sector of underwear which corresponds to the majority of the companies of Nova Friburgo. Seeking to enhance the competitive edge of such companies the present dissertation has the purpose of modeling the production process and develop a computational tool for the production scheduling based on the Tabu Search method.