Dissertations / Theses on the topic 'Production planning and scheduling problem'

Spatial resource allocation is an important consideration in shipbuilding and large-scale manufacturing industries. Spatial scheduling problems (SSP) involve the non-overlapping arrangement of jobs within a limited physical workspace such that some scheduling objective is optimized. Since jobs are heavy and occupy large areas, they cannot be moved once set up, requiring that the same contiguous units of space be assigned throughout the duration of their processing time. This adds an additional level of complexity to the general scheduling problem, due to which solving large instances of the problem becomes computationally intractable. The aim of this study is to gain a deeper understanding of the relationship between the spatial and temporal components of the problem. We exploit these acquired insights on problem characteristics to aid in devising solution procedures that perform well in practice. Much of the literature on SSP focuses on the objective of minimizing the makespan of the schedule. We concentrate our efforts towards the minimum sum of completion times objective and state several interesting results encountered in the pursuit of developing fast and reliable solution methods for this problem. Specifically, we develop mixed-integer programming models that identify groups of jobs (batches) that can be scheduled simultaneously. We identify scenarios where batching is useful and ones where batching jobs provides a solution with a worse objective function value. We present computational analysis on large instances and prove an approximation factor on the performance of this method, under certain conditions. We also provide greedy and list-scheduling heuristics for the problem and compare their objectives with the optimal solution. Based on the instances we tested for both batching and list-scheduling approaches, our assessment is that scheduling jobs similar in processing times within the same space yields good solutions. If processing times are sufficiently different, then grouping jobs together, although seemingly makes a more effective use of the space, does not necessarily result in a lower sum of completion times.

Process planning and scheduling are two important manufacturing planning functions which are closely related to each other. Usually, process planning and scheduling have to be performed sequentially, whereby the process plans are the input for scheduling. Many investigations have shown that the separate conduction of the two functions is much likely to ruin the effectiveness and feasibility of the process plans and schedules, and it is also difficult to cater for the occurrence of uncertainties in the dynamic manufacturing environment. The purpose of integrated process planning and scheduling (IPPS) is to perform the two functions concurrently. IPPS is a typical combinatorial optimization problem which belongs to the category of NP-hard problems. Research on IPPS has intensified in recent years. Researchers have reported various IPPS systems and solution approaches which are able to generate good solutions for specific IPPS problems. However, there is in general an absence of theoretical models for the IPPS problem representation, and research on the theoretical aspects of the IPPS is limited. The objective of this research is to establish a metaheuristic-based solution approach for the IPPS problem in flexible jobshop type of manufacturing systems. To begin with, a graph-based modeling approach for formulating the IPPS problem domain is proposed. This approach defines a way to use a category of AND/OR graphs to construct IPPS models. The graph-based IPPS model can be formulated using mathematical programming tools including polynomial mixed integer programming (PMIP) and mixed integer linear programming (MILP). The analytical mathematical programming approaches can be used to solve simple IPPS instances but they are not capable for large-scale IPPS problems. This research proposes a new IPPS modelling approach to incorporate metaheuristics in the solution strategy. Actually, the solution strategy comprises the metaheuristics and a mapping function. The metaheuristic is responsible for generating the operation sequences; a mapping function is then used to assign the operations to appropriate time slots on a schedule. General studies of applying constructive and improvement metaheuristics to solve the IPPS problem are conducted in this research. The ant colony optimization (ACO) is applied as a representative constructive metaheuristic, and a nonstandard genetic algorithm approach object-coding genetic algorithm (OCGA) is implemented as an improvement metaheuristic. The OCGA contains dedicated genetic operations to support the object-based genetic representation, and three particular mechanisms for population evolution. The metaheuristic-based solution approaches are implemented in a multi-agent system (MAS) platform. The hybrid MAS and metaheuristics based IPPS solution methodology is able to carry out dynamic rescheduling to cope with occurrence of uncertainties in practical manufacturing environments. Experiments have been carried out to test the IPPS solution approach proposed in this thesis. It is shown that both metaheuristics, ACO and OCGA, are having good performance in terms of solution quality and computational efficiency. In particular, due to the special genetic operations and population evolutionary mechanisms, the OCGA shows great advantages in experiments on benchmark problems. Finally, it is shown that the hybrid approach of MSA and metaheuristics is able to support real-time rescheduling in dynamic manufacturing systems.
published_or_final_version
Industrial and Manufacturing Systems Engineering
Doctoral
Doctor of Philosophy

This research is motivated by the need for considering lot sizing while accepting customer orders in a make-to-order (MTO) environment, in which each customer order must be delivered by its due date. Job shop is the typical operation model used in an MTO operation, where the production planner must make three concurrent decisions; they are order selection, lot size, and job schedule. These decisions are usually treated separately in the literature and are mostly led to heuristic solutions. The first phase of the study is focused on a formal definition of the problem. Mathematical programming techniques are applied to modeling this problem in terms of its objective, decision variables, and constraints. A commercial solver, CPLEX is applied to solve the resulting mixed-integer linear programming model with small instances to validate the mathematical formulation. The computational result shows it is not practical for solving problems of industrial size, using a commercial solver. The second phase of this study is focused on development of an effective solution approach to this problem of large scale. The proposed solution approach is an iterative process involving three sequential decision steps of order selection, lot sizing, and lot scheduling. A range of simple sequencing rules are identified for each of the three sub-problems. Using computer simulation as the tool, an experiment is designed to evaluate their performance against a set of system parameters. For order selection, the proposed weighted most profit rule performs the best. The shifting bottleneck and the earliest operation finish time both are the best scheduling rules. For lot sizing, the proposed minimum cost increase heuristic, based on the Dixon-Silver method performs the best, when the demand-to-capacity ratio at the bottleneck machine is high. The proposed minimum cost heuristic, based on the Wagner-Whitin algorithm is the best lot-sizing heuristic for shops of a low demand-to-capacity ratio. The proposed heuristic is applied to an industrial case to further evaluate its performance. The result shows it can improve an average of total profit by 16.62%. This research contributes to the production planning research community with a complete mathematical definition of the problem and an effective solution approach to solving the problem of industry scale.

In this dissertation, we consider two specific types of problems over networks. In the first problem, we explore systematic methods to address some of the challenges in largescale maintenance planning in integrated chemical sites. In the second problem, we investigate different optimization model formulations for the design of flow distribution networks where the flow is potential-driven and nonlinearly related to the potential loss. Maintenance turnaround in the processing industry is a complex asset renewal project that includes huge capital expenditures and downtime losses. The option of deferring or rescheduling a turnaround project typically provides immediate financial relief from capital expenditure. However, the risk of running into site-wide disruptions in the form of unplanned events, yield, and reliability losses is not straightforward to assess. We propose mathematical optimization models to evaluate the risk of loss from turnaround deferrals in integrated sites and provide alternatives to reliably operate the site in a medium-term horizon. In the first chapter, we introduce the turnaround planning problem and the challenges it poses in integrated sites. We also introduce the background for the network design problem. In the second chapter, we study the financial impact of rescheduling turnarounds and the associated risk under unplanned outages. We compare the risk profiles presented by different production planning strategies. We propose a stochastic programming model for production planning that optimally builds up inventory ahead of time to hedge against production losses during unplanned outages. In the third chapter, we extend the stochastic optimization to handle a large set of scenarios and propose a Lagrangean decomposition method that improves a myopic production plan. The fourth chapter proposes a mixed-integer linear programming model that prescribes turnaround schedules when the underlying assets undergo yield loses and selectivity degradation. Here, we also study the impact of deferrals over a long-term horizon. The penultimate chapter addresses the nonlinear network design problem.The closing chapter summarizes the work and provides a few future directions. In the spirit of advancing manufacturing paradigms, the thesis supports investment in modeling efforts that address enterprise-wide planning problems.

Nowadays, every company seeks to optimize its Supply Chain (SC) in response to competitive pressures or to acquire advantage of new flexibility in the restrictions on world trade. The process systems engineering research community has been aware of this change and is playing a key role in expanding the system boundaries from chemical process systems to business process systems. The global optimization of a SC network is an extremely complex task. For this reason, SC decisions are typically divided into three decision levels: the operational (scheduling), the tactical (planning), and the strategic (design). Since most academic developments are too distant from industrial environments, the aim of this thesis is to be a step forward in narrowing the gap between planning and scheduling theory and practice by devising efficient mathematical approaches for solving real-life industrial scheduling and planning problems. An overview of production planning and scheduling, an analysis of existing approaches, methods and tools used throughout this study are first presented. The second part of this thesis is focused on the development of mathematical models for production processes with continuous parallel units. In this part, a novel mathematical programming framework is developed based on elegant modeling of the underlying problem. This work addresses challenging problems in a highly complex real-life bottling facility. The proposed framework addresses appropriately important changeover aspects such as changeover carryover and crossover, thereby leading to solutions with resulting in higher utilization of resources. The third part is focused on semicontinuous industries, which combine continuous and batch operation modes. First, a mathematical programming framework and a solution strategy are presented for the optimal production scheduling of multiproduct multistage semicontinuous process industries. A problem in an ice-cream production line has been considered; and it has been successfully solved. Second, a general mathematical programming approach is developed for the resource-constrained production planning problem in semicontinuous processes. This work has been motivated by a challenging problem in food processing industries related to yogurt production lines, where labor constitutes the limited resource constraint. Third, a novel mathematical formulation for the simultaneous optimization of production and logistics operations planning in large-scale single- or multi-site semicontinuous process industries is proposed. Alternative transportation modes are considered. Two industrial-size case studies for a real-life dairy industry have been solved. The forth part of the thesis deals with scheduling in batch processes. First, a real-life multiproduct multistage pharmaceuticals production facility is considered. A systematic two-stage iterative solution strategy, based on mathematical programming, has been developed to address this problem. Additionally, a new precedence concept have been developed in order to cope with objectives containing changeover issues. A salient feature of the proposed approach is that the scheduler can maintain the number of decisions at a reasonable level, thus reducing the solution search space. This often ensures a more stable and predictable optimization model behavior. Finally, a preliminary two-layered decomposition method to the batch process scheduling problem in multipurpose production plants is developed. The procedure is tested on several instances of a benchmark scheduling problem that considers a polymers production plant.
Hoy en día, debido a que las condiciones económicas y políticas cambian rápidamente, las empresas globales se enfrentan a un desafío continuo para reevaluar constantemente y configurar de forma óptima las operaciones de su cadena de suministro (CS) para alcanzar los índices de rendimiento clave, tales como la reducción de costes de rentabilidad y servicio al cliente. Las empresas buscan optimizar sus CSs en respuesta a presiones de la competencia o para adquirir ventaja de una mayor flexibilidad en las restricciones sobre todo en el comercio mundial. Las industrias de proceso también siguen esta tendencia. La comunidad que investiga la ingeniería de los sistemas de procesos ha sido consciente de este cambio y, hoy en día, está jugando un papel clave en la expansión de los límites de los sistemas más allá de los procesos químicos para incluir también los sistemas de negocio. La optimización global de una red CS es una tarea extremadamente compleja. Por esta razón, las decisiones CS por lo general contemplan tres niveles de decisión: operativo (programación de operaciones), táctico (planificación de la producción) y estratégico (diseño). La planificación de la producción y la programación de operaciones constituyen una parte crucial de los niveles de decisión jerarquizados de la CS completa. Las actividades de planificación y programación tratan de la asignación en el tiempo de los recursos escasos entre actividades que compiten para satisfacer de forma eficiente dichas necesidades. Más concretamente, la función de planificación tiene como objetivo optimizar el rendimiento económico de la empresa, ya que debe hacer coincidir la producción con la demanda de la mejor manera posible. El componente de programación de la producción es de vital importancia ya que es la capa que traduce los imperativos económicos del plan en una secuencia de acciones a ser ejecutadas en la planta, con el fin de ofrecer el rendimiento económico optimizado previsto por el plan de alto nivel. En general, las investigaciones recientes se dirigen a la búsqueda de soluciones que permitan un manejo eficiente y preciso de problemas de gran tamaño y de complejidad cada vez mayor. Sin embargo, queda mucho trabajo por hacer tanto en las mejoras del modelo como en las mejoras en los algoritmos de solución del problema, cuando se trata de abordar de manera rutinaria problemas relevantes para la industria, donde el software producido debe ser utilizado de manera regular por los profesionales en el campo. Además, los nuevos desarrollos académicos son en su mayoría de cierta complejidad, pero relativamente de pequeño tamaño comparados con los problemas industriales incluso de mediano tamaño. Por lo tanto, la aplicación de nuevas estrategias de producción y nuevos enfoques de programación en los estudios industriales en la vida real constituye un reto difícil. Como la mayoría de los desarrollos académicos están demasiado lejos del entorno de aplicabilidad industrial, el objetivo de esta tesis es dar un paso significativo en la reducción del salto existente entre la teoría y la práctica de la planificación y programación mediante la elaboración de enfoques eficaces de programación matemática para la solución

Cette thèse porte sur la planification du personnel en accordant une attention particulière à l'aspect humain et aux facteurs ergonomiques dans le domaine de la production. Un certain nombre de modèles mathématiques sont présentés pour formuler les problèmes d'ordonnancement et de planification du personnel étudié. Concernant les modèles de planification, la productivité du système de fabrication et le bien-être des travailleurs sont ciblés. De cette manière, une méthode d'affectation des travailleurs est présentée pour réduire le temps de production et une méthode d'ordonnancement pour la rotation des tâches est présentée afin d’équilibrer la charge de travail des opérateurs. À cet effet, une analyse ergonomique est effectuée sur les postes de travail du système de production étudié. Cette analyse aboutit à l'évaluation des postes du travail suivant la convention dite des feux de circulation, c'est-à-dire que les postes sont classés dans les niveaux de charge faible, moyen et élevé qui sont représentés respectivement par les couleurs verte, jaune et rouge. Une approche mathématique est développée pour convertir ces résultats en valeurs numériques, car les paramètres quantitatifs sont plus applicables pour l'optimisation de la planification. Une programmation multi-objectifs est proposée pour optimiser les deux objectifs mentionnés du problème d'ordonnancement de tournée du personnel étudié. Les méthodes d'agrégation linéaire et de ε-contrainte sont appliquées pour résoudre ce modèle d'optimisation. En outre, cette thèse présente une nouvelle variante du problème d'affectation appelé problème d'affectation généralisée par séquence qui est défini pour la planification du personnel dans un système combiné constitué des postes de travail en série et en parallèle. Il est prouvé que ce problème d'optimisation combinatoire est NP-difficile et les méthodes exactes ne sont pas capables de résoudre les instances de grande taille. Ainsi, trois méthodes approchées composées de deux approches matheuristiques et une heuristique hybride sont développées pour résoudre ce problème. Les méthodes matheuristiques sont basées sur la décomposition de la formulation pour simplifier le modèle principal en deux ou plusieurs modèles plus petits. La troisième méthode est une heuristique gloutonne combinée à une recherche locale. En outre, dans la dernière étape de cette thèse, la planification des ressources humaines pour un système de soins à domicile est formulée mathématiquement. Selon la structure du système, une intégration des problèmes d'affectation et de tournées de véhicules est présentée. Enfin, une approche matheuristique en trois étapes est proposée pour résoudre ce problème d'optimisation combinatoire
This thesis concerns the human resource planning by paying a special attention to the human aspect and ergonomic factors in the manufacturing domain. A number of mathematical models are presented to formulate the studied workforce scheduling and planning problems. In the planning models, the productivity of the manufacturing system and the well-being of the workers are targeted. In this way, a worker assignment approach is presented to reduce the production time and a job rotation scheduling approach is presented to balance the workloads on the operators. For this purpose, an ergonomic analysis is carried out on the jobs of the studied production system. This analysis results in the traffic light evaluation for the jobs, i.e., the jobs are categorized into the low, medium and high workload levels which are presented respectively by the green, yellow and red colors. A mathematical approach is developed to convert these outputs to the numerical values, because the quantitative parameters are more applicable for the optimization of the planning. A multi-objective programming is proposed to optimize two mentioned objectives of the studied workforce scheduling problem. Both linear aggregation and epsilon-constraint methods are applied to solve this optimization model. Furthermore, this thesis presents a novel variant of the assignment problem called sequencing generalized assignment problem which is defined for workforce scheduling in a combined system consisting of the jobs in series and in parallel. It is proved that this combinatorial optimization problem is NP-hard and the exact methods are not able to solve the large-scale instances. Hence, three approximate methods consisting of two matheuristic and a hybrid heuristic approaches are developed to solve it. The matheuristic methods are based on the decomposition of the formulation to break down and simplify the main model into two or more smaller models. The third method is a greedy heuristic combined with a local search. The efficiency of the three mentioned methods is evaluated by various instances of different sizes. Moreover, in the last step of this thesis, the human resource planning for a home healthcare system is formulated mathematically. According to the structure of the system, an integration of the worker assignment and vehicle routing problems is presented. Finally, a three-steps matheuristic approach is proposed to solve this combinatorial optimization problem

O ambiente competitivo no qual as empresas estão inseridas é caracterizado por mudanças frequentes na demanda de seus produtos e por uma necessidade em reduzir custos. Para obter sucesso frente à concorrência, se faz necessário alcançar resultados através da melhoria do processo produtivo, oferecendo respostas mais rápidas a variações na demanda e com uma utilização adequada dos recursos produtivos. Neste contexto, a utilização de softwares Advanced Planning and Scheduling com regra personalizada de programação possibilita melhoria no planejamento e programação da empresa no sentido dos objetivos citados. A partir disso, este trabalho propõe uma sistemática de desenvolvimento e implantação de regras de programação personalizadas. Após, é apresentada aplicação de um caso prático no qual foram detalhadas todas as etapas propostas na sistemática, desde o entendimento das necessidades da empresa até a avaliação dos resultados obtidos.
The competitive environment in which firms operate is characterized by frequent changes in product demand and a necessity to reduce costs. To succeed against the competition, it is necessary to gain competitive advantage by improving the production process, providing faster responses to changes in demand and proper use of productive resources. In this context, the use of Advanced Planning and Scheduling software with custom programming rule allows improved planning and programming company towards the objectives mentioned. This study proposes a systematic development and deployment of custom programming rules, next it is presented a case study which detail the stages proposed in the systematic, from the understanding of the business requirement until the evaluation of results.

Made available in DSpace on 2016-06-02T19:53:32Z (GMT). No. of bitstreams: 1 PEREZ_MARTINEZ_Karim_2013.pdf: 1435441 bytes, checksum: dc4551ff55ece881790f51193596d2bd (MD5) Previous issue date: 2013-09-27
Financiadora de Estudos e Projetos
This research deals with the production planning and scheduling problem in the molded pulp packing industry, studying particularly a plant of molded pulp packages for eggs. The production process can be subdivided into two processes: molding process and printing process. The main challenge for production planning activities is on the molding process, where products are produced through tooling that have several molds. These tooling are called "Molding Patterns" or " Conformation Patterns". Each one of the molding patterns can contain one, two, until three kind of molds, allowing to produce several products simultaneously. Producing several products at the time can generate large inventory for low demand products and also null inventory for high demand products. Thus, different inventory levels are defined for each product based on their demand behavior, in order to control inventory quantities. In this way, decisions related to the production planning and scheduling in this production process involve deciding which molding patterns should used, how much time they should be used, and how they should be sequenced. All these should be make taking into account a parallel machine system and sequenced-dependent setups time and costs, in order to minimize inventory and setups costs, as well as penalties associated to inventory out of the specified inventory levels of each product. To represent this problem we proposed two formulations: the first one based on the Capacitated Lot Sizing and Scheduling Problem (CLSP), and the second one based on the General Lot Sizing and Scheduling Problem (GLSP). The results from the models were compared in a set of real word instances of a plant, in order to check the adequacy to represent the decisions involved in the studied production process, as well as the main differences between their production plans and performance of the models. The proposed formulations were also adapted for a particular instance, in order to compare their productions plans against the production plan implement by the studied plant. Results show that the proposed models represent rightly decisions involved in the production planning and scheduling in the molded pulp. Furthermore, the solutions obtained by the proposed models represent production plans with costs significantly lower than the schedule implemented by a real plant in this kind of industry.
Este trabalho aborda o problema de planejamento e programação da produção na indústria de embalagens em polpa moldada, considerando particularmente uma fábrica de embalagens para acondicionamento de ovos. O processo de produção pode ser subdividido em dois processos: processo de moldagem e processo de estampagem. O principal desafio para as atividades de planejamento encontra-se no processo de moldagem, em que a obtenção dos produtos depende da utilização de diferentes ferramentais, formados por um conjunto de moldes. Estes ferramentais são chamados de padrões de conformação ou padrões de moldagem , e podem conter um, dois ou até três tipos de moldes, permitindo a produção simultânea de produtos diferentes. Esta produção simultânea de itens pode gerar grandes níveis de estoque de produtos de baixa demanda e estoques nulos para produtos de alta demanda, desta forma, são definidos diferentes níveis de estoque para cada produto com base no comportamento da sua demanda. As decisões envolvidas no planejamento e programação da produção neste tipo de processo envolve a escolha dos padrões de moldagem a serem utilizados, o tempo de produção de cada padrão, e a sequência em que estes devem ser programados, considerando um sistema de linhas paralelas idênticas e tempos e custos de preparação dependentes da sequência. Estas decisões devem ser definidas de modo a minimizar os custos de estocagem, preparação, e penalidades associadas ao desvio do volume do estoque em relação aos níveis estabelecidos para cada produto. Para representar o problema são propostas dois tipos de formulações: a primeira baseada no Problema de Dimensionamento de Lotes Capacitado (CLSP), e a segunda baseada no Problema de Dimensionamento e Sequenciamento de Lotes Geral (GLSP). Os resultados da resolução dos modelos são comparados com base em exemplares reais da fábrica em estudo, a fim de verificar sua adequação para representar as decisões envolvidas no sistema de produção, as principais diferenças nos planos de produção gerados, e o desempenho destes modelos. Os resultados obtidos demonstram que os modelos propostos representam adequadamente as decisões no sistema de produção estudado, e geram planos de produção significativamente melhores que os planos praticados pela fábrica.

In this thesis, and complex real world problem, a sequence dependent scheduling of different product orders on a number of lines is addressed. Changeover costs occur between product orders belonging to different product groups. The operational research cycle is employed exploring different optimization techniques as mathematical modelling and heuristic approaches. The identification, implementation and demonstration of the techniques are supported with numerical results from experiments. One combination of different solution techniques is put forward. Some suggestions are done for reducing cost and increasing productivity.

The single-stage simultaneous lot sizing and scheduling problem was the object of study in this work. The problem aims to minimize the total inventory and backlog costs associated with producing N products on M parallel machines over T time-period. This thesis presented an extensive literature review on the differences found when modelling and implementing lot sizing and scheduling systems. We observed several studies used metaheuristics successfully to address large instances of these problems achieving near, and sometimes, optimal results. However, little has been found to demonstrate the capabilities of Evolutionary Algorithms in this field. A description of the methodology used to s problem : is given in terms of a Hybrid Evolutionary Algorithm which represents the problem using two novel ideas, i.e., sets of products are modelled as alleles of the solution encoded, and the use of a decoder process performing a Linear Programming, guides the solution towards overall optimality.

Within manufacturing, increasing interest in being placed in the possibilities of integrated process planning and scheduling. Separating these two related tasks can impose constraints, on the final schedule, which are both undesirable and unnecessary. These constraints arise from premature decisions regarding the allocation of manufacturing resources. By making use of flexible process plans, these decisions can be delayed until the most appropriate time: during scheduling. The decisions can then be made on the basis of objectives common to both tasks (such as the minimisation of manufacturing cost). This thesis outlines an approach to manufacturing planning which is based on a highly general formulation of the problem. This integrated process planning/scheduling problem can be viewed as a generalisation of process plan optimisation, a task which is also considered in detail. A novel approach to plan optimisation is proposed, which in turn forms the basis for integrated planning and scheduling. Some research into integrated planning/scheduling has been reported in the literature. However, researchers differ in the way they formulate the integrated task. This thesis therefore attempts to outline a general framework for the characterisation of integrated process planning and scheduling problems. This considers both the degree and representation of process plan flexibility, and also the level of detail at which the shop floor is modelled. This framework forms a basis for a comparison of solution approaches. Published solution approaches are mostly based on the use of dispatching rules, but attempts have been made to use optimal search. The use of dispatching rules is essentially an ad hoc approach and, although relatively easy to apply in practice, produces solutions of mediocre quality. However, new research using simulated annealing suggests that neighbourhood search may offer a valuable alternative. This observation is supported by ambitious research published on the use of genetic algorithms. Because of the extreme combinatorial complexity of the combined task, optimal search methods are unlikely to be usable in practice. Furthermore, such methods exhibit a severe lack of generality because they make highly specific assumptions about problem formulation. Neighbourhood search techniques have inherent properties which give them a much higher level of generality. Although it is not an optimal search method, simulated annealing has been shown to provide solutions of significantly higher quality than those achieved by dispatching rule techniques. Also, and unlike optimal search techniques, it appears able to handle the immense complexity of the integrated planning/scheduling task. For the above reasons, it is argued that neighbourhood search techniques, such as simulated annealing, provide the best compromise available between solution quality and practical applicability.

The present study describes a pragmatic approach to the implementation of production planning and scheduling techniques in foundries of all types and looks at the use of `state-of-the-art' management control and information systems. Following a review of systems for the classification of manufacturing companies, a definitive statement is made which highlights the important differences between foundries (i.e. `component makers') and other manufacturing companies (i.e. `component buyers'). An investigation of the manual procedures which are used to plan and control the manufacture of components reveals the inherent problems facing foundry production management staff, which suggests the unsuitability of many manufacturing techniques which have been applied to general engineering companies. From the literature it was discovered that computer-assisted systems are required which are primarily `information-based' rather than `decision based', whilst the availability of low-cost computers and `packaged-software' has enabled foundries to `get their feet wet' without the financial penalties which characterized many of the early attempts at computer-assistance (i.e. pre-1980). Moreover, no evidence of a single methodology for foundry scheduling emerged from the review. A philosophy for the development of a CAPM system is presented, which details the essential information requirements and puts forward proposals for the subsequent interactions between types of information and the sub-system of CAPM which they support. The work developed was oriented specifically at the functions of production planning and scheduling and introduces the concept of `manual interaction' for effective scheduling. The techniques developed were designed to use the information which is readily available in foundries and were found to be practically successful following the implementation of the techniques into a wide variety of foundries. The limitations of the techniques developed are subsequently discussed within the wider issues which form a CAPM system, prior to a presentation of the conclusions which can be drawn from the study.

This research is concerned with scheduling production over a finite planning horizon in a capacitated manufacturing facility. It is assumed that a second source of supply is available by means of subcontracting and that the demand varies over time. The problem is to establish the production level in the facility and/or the ordering quantity from the subcontractor for each period in the planning horizon. Firstly, the cost functions are analyzed and two types of realistic production cost models are identified. Then mathematical models are developed for two different problems. One is a single criterion problem aimed at minimizing the total production and inventory costs. The other is a bicriterion problem which seeks the efficient frontier with respect to the total cost and the number of subcontractings, both to be minimized, over the planning horizon. For each of the above, two methods, namely, a general dynamic programming approach and an improved dynamic programming approach (Shortest path method) are presented. Several results are obtained for reducing the computations in solving these problems. Based on these results, algorithms are developed for both problems. The computational complexity of these algorithms are also analyzed. Two heuristic rules are then suggested for obtaining near-optimal solutions to the first problem with lesser computation. Both rules have been tested extensively and the results indicate advantages of using them. One of these rules is useful for solving the uncapacitated problem faster without losing optimality. The above results are then extended to other cases where some of the assumptions in the original problem are relaxed. Finally, we studied the multi-item lot-sizing problem with the subcontracting option and proposed a heuristic for solving the problem by the Lagrangean relaxation approach. We demonstrated that with an additional capacity constraint in the dual problem the feasible solution and the lower bound obtained during each iteration converge much faster than without it. After testing some randomly generated problems we found that most of the solutions obtained from the heuristic are very close to the best lower bound obtained from the dual problem within a limited number of iterations.

Thesis (Ph. D.)--Hong Kong University of Science and Technology, 2003.
Includes bibliographical references (leaves 146-154). Also available in electronic version. Access restricted to campus users.

The majority of the commercially available systems developed for capacity planning have been designedf or organisationsw hich are involved with make-to-stockm anufacturingT. heses ystemsa re difficult to implementi n bespokem anufacturing( make-to-ordero) rganisationss ince they are unable to accommodateth e requirementso f the volatile productione nvironment. This thesisi dentifies the uniqueo peratingc haracteristicos f the manufacturinge nvironmenta ssociated with bespokem anufacturingw hich caused ifficulty with the implementationo f commerciallya vailable systemsT. he findings from this investigationa re usedt o formulatea design for a capacityp lanning systemw hich fulfils the unique requirementso f the bespokem anufacturinge nvironment. The proposed system executes the capacity planning function at two separate levels of detail by integrating rough cut capacity planning with finite capacity planning. The two planning mechanisms are also integrated with a shop floor data collection system which has been designed for the assembly environment. Data interaction is achieved between the capacity planning modules and the shop floor data collection system via an Interface ManagemenSt ystem which ensurest hat the scheduled ata containedi n the individual systemsr emainsi n synchronisationa t all times. The capacity planning system also includes the design and development of a large scale display facility which is able to accommodateth e large volume of scheduled ata required to be viewed for finite capacity planning. This facility has been designed using multiple co-ordinated screens which are linked by a local area network. A data interface and parallel processing facility is incorporated in the design which enable the processing of a software application to be distributed over multiple nodes.

O setor industrial produtor de papel e celulose tem aumentado sua relevância comercial nas últimas décadas devido à demanda constantemente crescente. O aumento na competitividade do setor gerado pela economia globalizada e a dificuldade de desenvolvimento de bons planos de produção em ambientes produtivos cada vez mais complexos têm motivado a pesquisa por novas e efetivas ferramentas de auxílio à tomada de decisão. Considerando estas dificuldades, abordamos neste trabalho o problema de dimensionamento e sequenciamento de lotes com foco em empresas com processo integrado de produção de celulose e de papel. Trata-se de um problema de planejamento de médio a curto prazo, geralmente com maior enfoque no curto prazo por considerar o planejamento detalhado da produção em horizontes de planejamento que não superam 30 dias. No processo integrado de celulose e papel, foram consideradas as decisões de produção do digestor, evaporador, caldeira de recuperação e de múltiplas máquinas produtoras de papel, além do controle de estoque de produtos intermediários e finais. Modelos matemáticos da literatura foram modificados e estendidos para incorporar características adicionais do problema como, por exemplo, processos com múltiplas máquinas de papel. Além disso, foram desenvolvidas heurísticas construtivas, heurísticas de melhoria, abordagens de solução híbridas baseadas em algoritmos genéticos combinadas com ferramentas comerciais de solução exata, além de combinações entre os métodos. As abordagens desenvolvidas foram testadas computacionalmente e as melhores combinações de métodos foram definidas. De forma geral, os resultados dessas abordagens foram superiores aos obtidos por ferramentas de solução comerciais puras. Ademais, a variação proposta da heurística de melhoria fixe-e-otimize com mudanças na função objetivo se destacou com relação aos demais métodos, obtendo os melhores resultados, independentemente da qualidade da solução inicial utilizada. As principais contribuições desta tese são a apresentação de modelos matemáticos para representar apropriadamente o problema estudado, e o desenvolvimento de métodos de solução efetivos para resolver o problema.
The pulp and paper industry has been increasing the commercial importance in recent decades due to the constant growing demand. The increasing competitiveness of this sector generated by the globalized economy and the difficulty to develop good production plans in complex production environments have motivated the search for new and effective decision support systems. Given these difficulties, in this thesis we address the lot sizing and scheduling problem focused on integrated pulp and paper mills. This is a problem of medium to short term planning, generally more focused on the short term as it covers detailed production schedules in planning horizons which do not exceed 30 days. In these integrated pulp and paper process the production decisions of digester, evaporator, recovery boiler and multiple paper machines are considered, apart from the inventory control of intermediate and final products. Mathematical models known in the literature were modified and extended to incorporate additional features of the problem, such as processes with multiple paper machines. In addition, constructive and improvement heuristics, and hybrid methods based on genetic algorithms combined with a commercial solver were developed, as well as combinations of these solution approaches. The methods developed were computationally tested and the best combinations of methods were defined. Overall, the results of these methods were superior to the solutions obtained by pure commercial solvers. Moreover, the alternative variation proposed of the improvement heuristic fix-and-optimize with exchanges in the objective function surpassed the other methods, obtaining the best results, regardless of the quality of the initial solution used. The main contribution of this thesis are the presentation of mathematical models that appropriately represents the problem under study, and the development of effective solution methods to deal with the problem.

Thesis (Ph. D.)--Industrial and Systems Engineering, Georgia Institute of Technology, 2007.
Dr. Faiz Al-Khayyal, Committee Co-Chair ; Dr. Paul M. Griffin, Committee Co-Chair ; Dr. Earl Barnes, Committee Member ; Dr. Jye-Chyi Lu, Committee Member ; Dr. John Elton, Committee Member.

This study deals with chocolate production line scheduling. The particular production line allows producing multiple items at the same time. Another distinguishing property affecting the planning methodology is that an item can have different production capacities when produced in different product combinations which are called production patterns in this study. Planning is done on a 12 weeks rolling horizon. There are 21 products and 103 production patterns covering all the production possibilities. The subject of the study is to construct an algorithm that gives 12 weeks&rsquo
production values of each product and to construct the shift based scheduling of the first week of the planning horizon. The first part is Master Production Scheduling (MPS) and the objective is minimizing the shortage and overage costs. A mathematical modeling approach is used to solve the MPS problem. The second part is the scheduling part which aims to arrange the production patterns obtained from the MPS module within the shifts for the first week of the planning horizon considering the setup times. The MPS module is a large integer programming model. The challenge is finding a reasonable lower bound whenever possible. If it is not possible, finding a reasonable upper bound and seeking solutions better than that is the main approach. The scheduling part, after solving MPS, becomes a TSP and the setup times are sequence independent. In this part, the challenge is solving TSP with an appropriate objective function.

RFID (Radio Frequency Identification) technology has been widely used in manufacturing companies to support their production decision-makings such as planning and scheduling. Significant benefits have been obtained like real-time data collection, advanced production planning and scheduling (APS), as well as efficient material tracing & tracking. However, these companies are dazed when facing vast amount of RFID data, which could be further processed to obtain some invaluable knowledge for advanced decision-makings. This thesis proposes a holistic RFID-enabled solution for manufacturing companies which are facing typical challenges like paper-based data collection, inefficient planning and scheduling, ineffective work-in-progress (WIP) items visibility and traceability, as well as unsynchronized decision-making procedures. This solution includes several aspects. Firstly, RFID devices are systematically deployed in manufacturing sites (e.g. warehouse and shopfloors) to create an RFID-enabled ubiquitous production environment, where typical resources are converted into smart manufacturing objects (SMOs) which are able to sense and interact with each other. Thus, production logics could be carried out adaptively. Secondly, a real-time production planning and scheduling model is worked out for suiting the RFID-enabled ubiquitous manufacturing environment. This model uses several key concepts like hybrid flow shop scheduling (HFS), real-time job pool, and hierarchical decision-making principle to integrate production planning and scheduling level interactively. A real-time Kanban is proposed to coordinate these two levels. Thus, production decisions achieve a real-time fashion. Thirdly, in order to make full use of the RFID-captured real-time shopfloor production data, a data mining approach is introduced to excavate invaluable information and knowledge for APS decision-makings. Standard operation times (SOTs) and decision rules are mined for this purpose. Fourthly, an RFID-enabled real-time APS model is proposed for production decision-making. The resulting APS model is based on a hierarchical production decision-making principle to formulate planning and scheduling levels. An RFID-event driven mechanism is adopted to integrate these two levels for collaborative decision-making with the data mining approach. An RFID-enabled real-time advanced production planning and scheduling shell (RAPShell) is developed by using the concepts and models proposed in this thesis. Some cutting-edge technologies are implemented within RAPShell such as service-oriented architecture (SOA), Software as a Service (SaaS), and XML-based (re)configuration. A case study from a real-life automotive manufacturer is presented for demonstrating how RAPShell is able to facilitate the production activities and decision-making procedures. Benefits from quantitative and qualitative aspects in this case are summarized and discussed. Some innovative contributions are significant. Firstly, an affordable and systematic RFID deployment scheme is proposed to create an RFID-enabled ubiquitous manufacturing environment. Secondly, an entire data mining approach is worked out for discovering the invaluable information and knowledge from vast amount of RFID production data. Thirdly, an APS model using RFID-event driven and data mining technique is proposed to achieve ultimate APS within the ubiquitous manufacturing. Finally, insights and lessons learnt from this research and implementations are generated as managerial implications which could be referred by both academics and practitioners when contemplating the RFID-enabled solution.
published_or_final_version
Industrial and Manufacturing Systems Engineering
Doctoral
Doctor of Philosophy

The work presented in this dissertation has been focused on exploiting the branch-and-price (BNP) method for the solution of various stochastic mixed integer programming problems (MIPs). In particular, we address the stochastic generalized assignment problem (SGAP), a hospital staff scheduling problem (HSSP), a stochastic hospital staff scheduling problem (SHSSP), and a stochastic short-term personnel planning problem (SSTPP). The BNP method has been developed in concert with the dual stabilization technique and other enhancements of this method for each of these problems. In view of an excessive number of scenarios that arise for these problems, we also implement the Monte Carlo method within the BNP scheme. The superiority of the BNP-based method over the branch-and-cut (BNC) method is demonstrated for all of these problems. The first problem that we address is the SGAP for which the processing time of a job on a machine is assumed to be stochastic. Even though the generalized assignment problem (GAP) has been solved using the BNP method, yet no study has been reported in the literature on the use of the BNP method for the solution of the SGAP. Our work has been motivated by the desire to fill this gap. We begin by showing that it is better to solve the SGAP as a stochastic program in contrast to solving it by using the expected values of the times required to process the jobs on the machines. Then, we show that the stochastic model of the SGAP is a complete recourse model â a useful property which permits the first stage decisions to produce feasible solutions for the recourse problems. We develop three BNP-based methods for the solution of the SGAP. The first of these is BNP-SGAP, which is a combination of branch-and-bound and column generation methods. The pricing problem of BNP-SGAP is separable with regard to each machine, and it is a multiple-constraint knapsack problem. The second method is BNP-SGAP implemented in concert with the dual stabilization technique (DST), and it is designated as BNPDST-SGAP. We have introduced a new DST by modifying the Boxstep method of Pigatti et al. [76]. We have shown that our method performs better than the method of Pigatti et al. [76] resulting in over two-fold savings in cpu times on average. The third method that we develop for the solution of the SGAP is BNPDST-SGAP implemented with an advanced start to obtain an initial feasible solution. We use a greedy heuristic to obtain this solution, and this heuristic is a modification of a similar method used for the knapsack problem. It relies on the information available at a node of the underlying branch-and-bound tree. We have shown that this procedure obtains an initial feasible solution, if it exists at that node. We designate this method as BNPDSTKP-SGAP. We have also developed a BNC method to solve the SGAP using CPLEX 9.0. We have compared the performances of the BNP and BNC methods on various problem instances obtained by varying the number of machines, the ratio of the number of machines to the number of jobs, the machine capacity, and the penalty cost per unit of extra resource required at each machine. Our results show that all BNP-based methods perform better than the BNC method, with the best performance obtained for BNPDSTKP-SGAP. An issue with the use of the scenario-based methods that we have employed for the solution of the SGAP is that the number of scenarios generally grows exponentially in problem parameters, which gives rise to a large-size problem. To overcome the complexity caused by the presence of a large number of scenarios for the solution of the SGAP, we introduce the use of the Monte Carlo method (MCM) within the BNP scheme. We designate this method as BNPDSTKP-SGAP with MCM. It affords the use of a small subset of scenarios at a time to estimate the â trueâ optimal objective function value. Replications of the subsets of scenarios are carried out until the objective function value satisfies a stopping criterion. We have established theoretical results for the use of the MCM. These pertain to determining unbiased estimates of: (i) lower and upper bounds of the â trueâ optimal objective function value, (ii) the â trueâ optimal solution, and (iii) the optimality gap. We have also provided the 100(1-ï ¡) confidence interval on the optimality gap. Our experimental investigation has shown the efficacy of using this method. It obtains almost optimal solutions, with the objective function value lying within 5% of the â trueâ optimal objective function value, while giving almost ten-fold savings in cpu time. Our experimentation has also revealed that an increment in the number of scenarios in each replication makes a greater impact on the quality of the solution obtained than an increment in the number of replications. We have also observed the impact of a change in the variance of a processing time distribution on cpu time. As expected, the optimal objective function value increases with increment in processing time variability. Also, by comparing the results with the expected value solution, it is observed that the greater the variability in the data, the better it is to use the stochastic program. The second problem that we study is the hospital staff scheduling problem. We address the following three versions of this problem: HSSP (General): Implementation of schedule incorporating the four principal elements, namely, surgeons, operations, operating rooms, and operation times; HSSP (Priority): Inclusion of priority for some surgeons over the other surgeons regarding the use of the facility in HSSP (General); HSSP (Pre-arranged): Implementation of a completely pre-fixed schedule for some surgeons. The consideration of priority among the surgeons mimics the reality. Our BNP method for the solution of these problems is similar to that for the SGAP except for the following: (i) a feasible solution at a node is obtained with no additional assignment, i.e., it consists of the assignments made in the preceding nodes of that node in the branch-and-bound tree; (ii) the columns with positive reduced cost are candidates for augmentation in the CGM; and (iii) a new branching variable selection strategy is introduced, which selects a fractional variable as a branching variable by fixing a value of which we enforce the largest number of variables to either 0 or 1. The priority problem is separable in surgeons. The results of our experimentation have shown the efficacy of using the BNP-based method for the solution of each HSSP as it takes advantage of the inherent structure of each of these problems. We have also compared their performances with that of the BNC method developed using CPLEX. For the formulations HSSP (General), HSSP (Priority), and HSSP (Pre-arranged), the BNP method gives better results for 22 out of 30, 29 out of 34, and 20 out 32 experiments over the BNC method, respectively. Furthermore, while the BNC method fails to obtain an optimal solution for 15 experiments, the BNP method obtains optimal solutions for all 96 experiments conducted. Thus, the BNP method consistently outperforms the BNC method for all of these problems. The third problem that we have investigated in this study is the stochastic version of the HSSP, designated as the Stochastic HSSP (SHSSP), in which the operation times are assumed to be stochastic. We have introduced a formulation for this formulation, designated as SHSSP2 (General), which allows for overlapping of schedules for surgeons and operating rooms, and also, allows for an assignment of a surgeon to perform an operation that takes less than a pre-arranged operation time, but all incurring appropriate penalty costs. A comparison of the solution of SHSSP2 (General) and its value with those obtained by using expected values (the corresponding problem is designated as Expected-SHSSP2 (General)) reveals that Expected-SHSSP2 (General) may end up with inferior and infeasible schedules. We show that the recourse model for SHSSP2 (General) is a relatively complete recourse model. Consequently, we use the Monte Carlo method (MCM) to reduce the complexity of solving SHSSP2 (General) by considering fewer scenarios. We employ the branch-and-cut (BNC) method in concert with the MCM for solving SHSSP2 (General). The solution obtained is evaluated using tolerance ratio, closeness to optimality, length of confidence interval, and cpu time. The MCM substantially reduces computational effort while producing almost optimal solutions and small confidence intervals. We have also considered a special case of SHSSP2 (General), which considers no overlapping schedules for surgeons and operating rooms and assigns exactly the same operation time for each assignment under each scenario, and designate it as SHSSP2 (Special). With this, we consider another formulation that relies on the longest operation time among all scenarios for each assignment of a surgeon to an operation in order to avoid scheduling conflicts, and we designate this problem as SHSSP (Longest). We show SHSSP (Longest) to be equivalent to deterministic HSSP, designated as HSSP (Equivalent), and we further prove it to be equivalent to SHSSP (General) in terms of the optimal objective function value and the optimal assignments of operations to surgeons. The schedule produced by HSSP (Equivalent) does not allow any overlap among the operations performed in an operating room. That is, a new operation cannot be performed if a previous operation scheduled in that room takes longer than expected. However, the schedule generated by HSSP (Equivalent) may turn out to be a conservative one, and may end up with voids due to unused resources in case an operation in an operating room is completed earlier than the longest time allowed. Nevertheless, the schedule is still a feasible one. In such a case, the schedule can be left-shifted, if possible, because the scenarios are now revealed. Moreover, such voids could be used to perform other procedures (e.g., emergency operations) that have not been considered within the scope of the SHSSP addressed here. Besides, such a schedule can provide useful guidelines to plan for resources ahead of time. The fourth problem that we have addressed in this dissertation is the stochastic short-term personnel planning problem, designated as Stochastic STPP (SSTPP). This problem arises due to the need for finding appropriate temporary contractors (workers) to perform requisite jobs. We incorporate uncertainty in processing time or amount of resource required by a contractor to perform a job. Contrary to the SGAP, the recourse model for this problem is not a relatively complete recourse model. As a result, we cannot employ a MCM method for the solution of this problem as it may give rise to an infeasible solution. The BNP method for the SSTPP employs the DST and the advanced start procedure developed for the SGAP, and due to extra constraints and presence of binary decision variables, we use the branching variable selection strategy developed for the HSSP models. Because of the distinctive properties of the SSTPP, we have introduced a new node selection strategy. We have compared the performances of the BNC-based and BNP-based methods based on the cpu time required. The BNP method outperforms the BNC method in 75% of the experiments conducted, and the BNP method is found to be quite stable with smaller variance in cpu times than those for the BNC method. It affords solution of difficult problems in smaller cpu times than those required for the BNC method.
Ph. D.

The research presented in this dissertation addresses the Multi-Mode Resource-Constrained Project Scheduling Problem (MMRCPSP) in the presence of resource unavailability. This research is motivated by the scheduling of engineering design tasks in automotive product development to minimize the project completion time, but addresses a general scheduling situation that is applicable in many contexts. The current body of MMRCPSP research typically assumes that, 1) individual resource units are available at all times when assigning tasks to resources and, 2) before assigning tasks to resources, there must be enough resource availability over time to complete the task without interruption. In many situations such as assigning engineering design tasks to designers, resources are not available over the entire project-planning horizon. In the case of engineering designers and other human resources, unavailability may be due to several reasons such as vacation, training, or being scheduled to do other tasks outside the project. In addition, when tasks are scheduled they are often split to accommodate unavailable resources and are not completed in one continuous time segment. The objectives of this research are to obtain insight into the types of project scheduling situations where task splitting may result in significant makespan improvements, and to develop a fast and effective scheduling heuristic for such situations. A designed computational experiment was used to gain insight into when task splitting may provide significant makespan improvements. Problem instances were randomly generated using a modification of a standard problem generator, and optimally solved with and without task splitting using a branch and bound algorithm. In total 3,880 problem instances were solved with and without task splitting. Statistical analysis of the experimental data reveals that high resource utilization is the most important factor affecting the improvements obtained by task splitting. The analysis also shows that splitting is more helpful when resource unavailability occurs in multiple periods of short duration versus fewer periods of long duration. Another conclusion from the analysis indicates that the project precedence structure and the number (not amount) of resources used by tasks do not significantly affect the improvements due to task splitting. Using the insights from the computational testing, a new heuristic is developed that can be applied to large problems. The heuristic is an implementation of a simple priority rule-based heuristic with a new parameter used to control the number of task splits. It is desirable to obtain the majority of task splitting benefits with the smallest number of split tasks. Computational experiments are conducted to evaluate its performance against known optimal solutions for small sized problems. A deterministic version of the heuristic found optimal solutions for 33% of the problems and a stochastic version found optimal solutions for over 70%. The average percent increase in makespan compared to optimal was 7.58% for the deterministic heuristic and less than 2% for the stochastic versions demonstrating acceptable performance.
Graduation date: 2003