This dissertation discusses two independent topics: a resource-constrained shortest-path problem (RCSP) and a literature review on scheduling problems involving sequence-dependent setup (SDS) times (costs). RCSP is often used as a subproblem in column generation because it can be used to solve many practical problems. This dissertation studies RCSP with multiple resource constraints on an acyclic graph, because many applications involve this configuration, especially in column genetation formulations. In particular, this research focuses on a dynamic RCSP since, as a subproblem in column generation, objective function coefficients are updated using new values of dual variables at each iteration. This dissertation proposes a pseudo-polynomial solution method for solving the dynamic RCSP by exploiting the special structure of an acyclic graph with the goal of effectively reoptimizing RCSP in the context of column generation. This method uses a one-time “preliminary” phase to transform RCSP into an unconstrained shortest path problem (SPP) and then solves the resulting SPP after new values of dual variables are used to update objective function coefficients (i.e., reduced costs) at each iteration. Network reduction techniques are considered to remove some nodes and/or arcs permanently in the preliminary phase. Specified techniques are explored to reoptimize when only several coefficients change and for dealing with forbidden and prescribed arcs in the context of a column generation/branch-and-bound approach. As a benchmark method, a label-setting algorithm is also proposed. Computational tests are designed to show the effectiveness of the proposed algorithms and procedures. This dissertation also gives a literature review related to the class of scheduling problems that involve SDS times (costs), an important consideration in many practical applications. It focuses on papers published within the last decade, addressing a variety of machine configurations - single machine, parallel machine, flow shop, and job shop - reviewing both optimizing and heuristic solution methods in each category. Since lot-sizing is so intimately related to scheduling, this dissertation reviews work that integrates these issues in relationship to each configuration. This dissertation provides a perspective of this line of research, gives conclusions, and discusses fertile research opportunities posed by this class of scheduling problems. since, as a subproblem in column generation, objective function coefficients are updated using new values of dual variables at each iteration. This dissertation proposes a pseudo-polynomial solution method for solving the dynamic RCSP by exploiting the special structure of an acyclic graph with the goal of effectively reoptimizing RCSP in the context of column generation. This method uses a one-time

Water and energy are very necessary resources for operating any chemical plant and contribute to total costs. Economic reasons notwithstanding, the processing industry has been incentivised to practise sustainable production in which the consumption of energy and water are more efficient, in response to stringent environmental legislation and public perception. Published literature exists for the independent investigation of water and energy optimisation in batch plants. It has been established for the individual problems that, a true optimum can only be obtained if batch production scheduling and water use or energy optimisation are performed simultaneously. However, the simultaneous optimisation of both water and energy within the same production scheduling framework has been largely ignored, due to the potential complexities of such a problem. Additionally, literature addressing the minimisation of water in fixed load problems has usually assumed that the water using operations (washing) are sequence independent. This is unlikely, as equipment units usually perform more than one task in multipurpose batch plants. Since the sequence of tasks in a unit influences both the occurrence and extent of washing in the unit, appropriate consideration of task sequences during production can contribute to wastewater minimisation. This thesis presents a mathematical formulation for the production scheduling of multipurpose batch plants, in which sequence dependent changeover costs are addressed. When compared to an existing formulation, the proposed formulation leads to a smaller sized model with fewer binary variables, continuous variables and constraints for a given case study, although the same objective was obtained. Expanding upon this, a mathematical formulation for simultaneous batch production scheduling and wastewater minimisation, for which the water requirement in a unit is dependent on tasks and their successors, is presented. The effectiveness of the formulation was demonstrated using two case studies. The results show improvements in profit and reduced wastewater generation when the sequence of tasks is taken into consideration. One case study saw water savings of 48% achieved with this method. The formulation was extended to incorporate process integration in the form of direct water reuse, which resulted in a further improvement in profit and water use. The third contribution in this thesis is a simultaneous method for the optimisation of energy and water embedded within a scheduling framework. In addition, opportunities for direct and indirect heat integration as well as direct and indirect water reuse were explored with the objective of improving the profitability of the plant while minimising water and external utility usage. The applicability of the method was demonstrated with three case studies. The developed formulation proved superior to a method that solved the same problem sequentially. / Thesis (PhD)--University of Pretoria, 2017. / Chemical Engineering / PhD / Unrestricted

No description available.

Just-In-Time (JIT) production systems is a popular area for researchers but real-world issues such as sequence dependent setups are often overlooked. This research investigates an approach for determining stability and an approach for mixed product sequencing in production systems with sequence dependent setups and buffer thresholds which signal replenishment of a given buffer. Production systems in this research operate under JIT pull production principles by producing only when demand exists and idle when no demand exists. In the first approach, an iterative method is presented to determine stability for a multi-product production system that operates with replenishment signals and may have sequence dependent setups. In this method, a network of nodes representing machine states and arcs representing the buffer inventory levels is used to find a stable trajectory for the production system via an iterative procedure. The method determines suitable buffer levels for the production system that ensure that a trajectory originating from any point within a buffer region will always map to a point contained on another buffer region for all future mappings. This iterative method for determining the stability of a production system was implemented using an algorithm to calculate the buffer inventory regions for all arcs in a given arc-node network. The algorithm showed favorable results for two and three product systems in which sequence dependent setups may exist. In the second approach, a product sequencing algorithm determines a product sequence for a production system based on system parameters – setup times, buffer levels, usage rates, production rates, etc. The algorithm selects a product by evaluating the goodness of each product that has reached the replenishment threshold at the current time. The algorithm also incorporates a lookahead function that calculates the goodness for some time interval into the future. The lookahead function considers all branches of the tree of potential sequences to prevent the sequence from travelling down a dead-end branch in which the system will be unable to avoid a depleted buffer. The sequencing algorithm allows the user to weight the five terms of the goodness equations (current and lookahead) to control the behavior of the sequence.

Cellular manufacturing, which is also referred to as group technology among researchers, has primarily been used as a means to increase productivity, efficiency and flexibility. Under group technology, similar jobs, which have similar shape, material, and processing operations are assigned to the same group. Moreover, dissimilar machines are assigned to the same cell to meet the processing requirements of jobs in a group or multiple groups. Group scheduling problems have been studied extensively in the past as implementation of group technology became more prevalent in industry. However, most of the work that has been done has focused on single-criterion optimization. A bi-criteria group scheduling problem in a flow shop with sequence-dependent setup time is investigated in this research. Cellular manufacturing and flow shop are two popular scenarios in industry. To mimic real industry practice, dynamic job releases and dynamic machine availabilities are assumed. The goal is to minimize the weighted sum of total weighted completion time and total weighted tardiness, which satisfy the producer and customer goals separately. Normalized weights are assigned to both criteria to describe the trade-off between the two goals. Two different initial solution finding mechanisms are proposed, and a tabu-search based two-level search algorithm is developed to find near optimal solutions for the problem. An example problem is used to demonstrate the applicability of the search algorithm. A mathematical model is developed and implemented to evaluate the quality of the solutions obtained from the heuristics in small problem instances. Further, to uncover the difference in performance of initial solution finding mechanisms and heuristics, a detailed experimental design is performed. The results show that different heuristics have different performance in solving problems generated with different parameters. / Graduation date: 2012

We consider the stochastic economic lot scheduling problem (SELSP) with lost sales and random demand, where switching between products is subject to sequence-dependent setup times. We propose a solution based on simulation optimization using an iterative two-step procedure which combines global policy search with local search heuristics for the traveling salesman sequencing subproblem. To optimize the production cycle, we compare two criteria: minimizing total setup times and evenly distributing setups to obtain a more regular production cycle. Based on a numerical study, we find that a policy with a balanced production cycle leads to lower cost than other policies with unbalanced cycles. (authors' abstract)

The motivation of this research investigation stems from a particular job shop production environment at a large international communications and information technology company in which electro-mechanical assemblies (EMAs) are produced. The production environment of the EMAs includes the continuous arrivals of the EMAs (generally called jobs), with distinct due dates, degrees of importance and routing sequences through the production workstations, to the job shop. Jobs are processed in batches at the workstations, and there are incompatible families of jobs, where jobs from different product families cannot be processed together in the same batch. In addition, there are sequence-dependent setups between batches at the workstations. Most importantly, it is imperative that all product deliveries arrive on time to their customers (internal and external) within their respective delivery time windows. Delivery is allowed outside a time window, but at the expense of a penalty. Completing a job and delivering the job before the start of its respective time window results in a penalty, i.e., inventory holding cost. Delivering a job after its respective time window also results in a penalty, i.e., delay cost or emergency shipping cost. This presents a unique scheduling problem where an earlinesstardiness composite objective is considered. This research approaches this scheduling problem by decomposing this complex job shop scheduling environment into bottleneck and non-bottleneck resources, with the primary focus on effectively scheduling the bottleneck resource. Specifically, the problem of scheduling jobs with unique due dates on a single workstation under the conditions of batching, sequence-dependent iii setups, incompatible job families in order to minimize weighted earliness and tardiness is formulated as an integer linear program. This scheduling problem, even in its simplest form, is NP-Hard, where no polynomial-time algorithm exists to solve this problem to optimality, especially as the number of jobs increases. As a result, the computational time to arrive at optimal solutions is not of practical use in industrial settings, where production scheduling decisions need to be made quickly. Therefore, this research explores and proposes new heuristic algorithms to solve this unique scheduling problem. The heuristics use order review and release strategies in combination with priority dispatching rules, which is a popular and more commonly-used class of scheduling algorithms in real-world industrial settings. A computational study is conducted to assess the quality of the solutions generated by the proposed heuristics. The computational results show that, in general, the proposed heuristics produce solutions that are competitive to the optimal solutions, yet in a fraction of the time. The results also show that the proposed heuristics are superior in quality to a set of benchmark algorithms within this same class of heuristics

Wine companies face two important challenges in their supply chain: the international shipping temperatures and their effect on the perceived quality of the wine and the optimization of the bottling schedule. The wine maker takes special care in producing the best quality product, which is then shipped to the importer/distributor or consumer, generally in non-refrigerated containers at the mercy of the prevailing environmental conditions. The contributions of this work is that it is the first to measure, for a significant period of time, the temperatures along the international wine supply chain and to link them to the specific supply chain processes. This is also the first work that analyzes the effect of shipping temperature on the perceived quality of the product by those who make the purchase decision for importers, restaurants and supermarkets. Results indicate that the wine is very likely to have been exposed to extreme temperatures during shipping. For white wines, tasters are able to detect differences in wines which have been exposed to shipping temperatures and show a preference towards them. For red wines, they are unable to detect differences. Our contribution to the second challenge was the development of a model that produces solutions for the wine bottling lot sizing and scheduling problem with sequence dependent setup times, in an adequate time-frame, which can be implemented by large wineries. We have developed a model and algorithm that produces fast, good and robust solutions for the winery lot sizing and scheduling problem with sequence dependent setup times. We implemented an effective decomposition algorithm that uses the structure of the problem, that can be applied to other families of sequence dependent scheduling and lot sizing problem. Results indicate that the model achieves reductions of 30\% in the total plan costs.

Simultaneous lot-sizing and scheduling problem is the problem to decide what products to be produced on which machine and in which order, as well as the quantity of each product. Problems of this type are hard to solve. Therefore, they were studied for years, and a considerable number of papers is published to solve different lotsizing and scheduling problems, specifically real-case problems. This work proposes a Real-Coded Genetic Algorithm (RCGA) with a new chromosome representation to solve a non-identical parallel machine capacitated lot-sizing and scheduling problem with sequence dependent setup times and costs, machine cost and backlogging. Such a problem can be found in real world production line at furniture manufacturer in Sweden. Backlogging is an important concept in this problem, and it is often ignored in the literature. This study implements three different types of crossover; one of them has been chosen based on numerical experiments. Four mutation operators have been combined together to allow the genetic algorithm to scan the search area and maintain genetic diversity. Other steps like initializing of the population and a reinitializing process have been designed carefully to achieve the best performance and to prevent the algorithm from trapped into the local optimum. The proposed algorithm is implemented and coded in MATLAB and tested for a set of standard medium to large-size problems taken from the literature. A variety of problems were solved to measure the impact of different characteristics of problems such as the number of periods, machines, and products on the quality of the solution provided by the proposed RCGA. To evaluate the performance of the proposed algorithm, the average deviation from the lower bound and runtime for the proposed RCGA are compared with three other algorithms from the literature. The results show that, in addition to its high computational speed, the proposed RCGA outperforms the other algorithms for non-identical parallel machine problems, while it is outperformed by the other algorithms for problems with the more identical parallel machine. The results show that the different characteristics of problem instances, like increasing setup cost, and size of the problem influence the quality of the solutions provided by the proposed RCGA negatively.

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