A genetic algorithm/mathematical programming approach to solve a two-level soft drink production problem

This study applies a genetic algorithm embedded with mathematical programming techniques to solve a synchronized and integrated two-level lot sizing and scheduling problem motivated by a real-world problem that arises in soft drink production. The problem considers a production process compounded by raw material preparation/storage and soft drink bottling. The lot sizing and scheduling decisions should be made simultaneously for raw material preparation/storage in tanks and soft drink bottling in several production lines minimizing inventory, shortage and setup costs. The literature provides mixed-integer programming models for this problem, as well as solution methods based on evolutionary algorithms and relax-and-fix approaches. The method applied by this paper uses a new approach which combines a genetic algorithm (GA) with mathematical programming techniques. The GA deals with sequencing decisions for production lots, so that an exact method can solve a simplified linear programming model, responsible for lot sizing decisions. The computational results show that this evolutionary/mathematical programming approach outperforms the literature methods in terms of production costs and run times when applied to a set of real-world problem instances provided by a soft drink company.     

Planning production using mathematical programming: The case of a woodturning company

Herein we present a case of production planning in a woodturning company. The company wishes to plan the turning of various types of products of different radii in a set of parallel machines (lathes) and with the following principal conditions: for each type of product there is a minimum production lot size; some lathes cannot manufacture every type of product; the production capacity of a lathe depends on the lathe itself and the type of product to be manufactured; the products are classified into families according to radius; and there is an intra-family setup time (for manufacturing different products that have the same radius) and an inter-family setup time (for consecutively manufacturing products that have different radii), which is longer; part of the production can be subcontracted; each type of product can be manufactured on different lathes and/or subcontracted; and the operators can work overtime, during which additional time they can simultaneously operate multiple lathes. The goal is to meet the demand at minimum cost, which includes the cost of any overtime plus that of any subcontracting. The problem was modelled and solved by mixed-integer linear programming (MILP). The company considers the results to be satisfactory.     

An optimal policy for a single-vendor and a single-buyer integrated system with setup cost reduction and process-quality improvement

The single-vendor single-buyer integrated production inventory system has been an object of study for a long time, but little is known about the effect of investing in reducing setup cost reduction and process-quality improvement for an integrated inventory system in which the products are sold with free minimal repair warranty. The purpose of this article is to minimise the integrated cost by optimising simultaneously the number of shipments and the shipment quantity, the setup cost, and the process quality. An efficient algorithm procedure is proposed for determining the optimal decision variables. A numerical example is presented to illustrate the results of the proposed models graphically. Sensitivity analysis of the model with respect to key parameters of the system is carried out. The paper shows that the proposed integrated model can result in significant savings in the integrated cost.     

A simulated annealing with multiple‐search paths and parallel computation for a comprehensive flowshop scheduling problem

Recent studies have demonstrated that the performance of a simulated annealing algorithm can be improved by following multiple‐search paths and parallel computation. In this paper, we use these strategies to solve a comprehensive mathematical model for a flexible flowshop lot streaming problem. In the flexible flowshop environment, a number of jobs will be processed in several consecutive production stages, and each stage may involve a certain number of parallel machines that may not be identical. Each job has to be split into several unequal sublots by following the concept of lot streaming. The sublots are to be processed in the order of the stages, and sublots of certain products may skip some stages. This complex problem also incorporates sequence‐dependent setup times, the anticipatory or nonanticipatory nature of setups, release dates for machines, and machine eligibility. Numerical examples are presented to demonstrate the effectiveness of lot streaming in hybrid flowshops, the performance of the proposed simulated annealing algorithm, and the improvements achieved using parallel computation.     

A bi-objective possibilistic programming model for open shop scheduling problems with sequence-dependent setup times, fuzzy processing times, and fuzzy due dates

We are concerned with an open shop scheduling problem having sequence-dependent setup times. A novel bi-objective possibilistic mixed-integer linear programming model is presented. Sequence-dependent setup times, fuzzy processing times and fuzzy due dates with triangular possibility distributions are the main constraints of this model. An open shop scheduling problem with these considerations is close to the real production scheduling conditions. The objective functions are to minimize total weighted tardiness and total weighted completion times. To solve small-sized instances for Pareto-optimal solutions, an interactive fuzzy multi-objective decision making (FMODM) approach, called TH method proposed by Torabi and Hassini, is applied. Using this method, an equivalent auxiliary single-objective crisp model is obtained and solved optimally by the Lingo software. For medium to large size examples, a multi-objective particle swarm optimization (MOPSO) algorithm is proposed. This algorithm consists of a decoding procedure using a permutation list to reduce the search area in the solution space. Also, a local search algorithm is applied to generate good initial particle positions. Finally, to evaluate the effectiveness of the MOPSO algorithm, the results are compared with the ones obtained by the well-known SPEA-II, using design of experiments (DOE) based on some performance metrics.     

Scheduling Flexible Flow Shop in Labeling Companies to Minimize the Makespan

In the competitive global marketplace, production scheduling plays a vital role in planning in manufacturing. Scheduling deals directly with the time to output products quickly and with a low production cost. This research examines case study of a Radio-Frequency Identification labeling department at Avery Dennison. The main objective of the company is to have a method that allows for the sequencing and scheduling of a set of jobs so it can be completed on or before the customer’s due date to minimize the number of late orders. This study analyzes the flexible flow shop scheduling problem with a sequence dependent setup by modifying the processing time and setup time to minimize the makespan on multiple machines. Based on the defined mathematical model, this study includes an alternative approach and application of heuristic algorithm with the input being big data. Both optimization programs are used in this study and compared to determine which method can better solve the company’s problems. The proposed algorithm is able to improve machine utilization with large-scale problems.     

An algorithm for production planning in a flexible production system

In this paper, we consider the problem of determining the production rate, production batch size, and production sequence when production rate, setup cost, and unit processing cost are sequence-dependent. Using a standard lot sizing model with backorder, a tabu search algorithm for solving this problem is proposed. The algorithm is tested on some random test problems and its performance is compared with random sequencing. Computational results show that the proposed algorithm is very efficient.     

The production scheduling problem in a multi-page invoice printing system

This paper addresses the production scheduling problem in a multi-page invoice printing system. The system comprises three stages: the stencil preparation stage, the page printing stage and the invoice assembly stage. Since each page can be considered as a component and the invoice as the finished product, the production system for multi-page invoices can be treated as an assembly-type flowshop with parallel machines at the last two stages. Moreover, two types of sequence-dependent setup operations are considered at the second stage. The objective is to minimize the makespan for all the invoice orders. We first formulate this problem into a mixed-integer linear programming (MILP). Then a hybrid genetic algorithm (HGA) is proposed for solving it due to its NP-hardness. To evaluate the performance of the HGA heuristic, a lower bound for the makespan is developed. Numerical experiment indicates that our algorithm can solve the problem efficiently and effectively.     

Capacitated lot-sizing and scheduling with sequence-dependent,period-overlapping and non-triangular setups

In production planning, sequence dependent setup times and costs are often incurred for switchovers from one product to another. When setup times and costs do not respect the triangular inequality, a situation may occur where the optimal solution includes more than one batch of the same product in a single period—in other words, at least one sub tour exists in the production sequence of that period. By allowing setup crossovers, flexibility is increased and better solutions can be found. In tight capacity conditions, or whenever setup times are significant, setup crossovers are needed to assure feasibility. We present the first linear mixed-integer programming extension for the capacitated lot-sizing and scheduling problem incorporating all the necessary features of sequence sub tours and setup crossovers. This formulation is more efficient than other well known lot-sizing and scheduling models.     

A priori reformulations for joint rolling-horizon scheduling of materials processing and lot-sizing problem

In many production processes, a key material is prepared and then transformed into different final products. The lot sizing decisions concern not only the production of final products, but also that of material preparation in order to take account of their sequence-dependent setup costs and times. The amount of research in recent years indicates the relevance of this problem in various industrial settings. In this paper, facility location reformulation and strengthening constraints are newly applied to a previous lot-sizing model in order to improve solution quality and computing time. Three alternative metaheuristics are used to fix the setup variables, resulting in much improved performance over previous research, especially regarding the use of the metaheuristics for larger instances.     

On the solution of mixed-integer nonlinear programming models for computer aided molecular design

This paper addresses the efficient solution of computer aided molecular design (CAMD) problems, which have been posed as mixed-integer nonlinear programming models. The models of interest are those in which the number of linear constraints far exceeds the number of nonlinear constraints, and with most variables participating in the nonconvex terms. As a result global optimization methods are needed. A branch-and-bound algorithm (BB) is proposed that is specifically tailored to solving such problems. In a conventional BB algorithm, branching is performed on all the search variables that appear in the nonlinear terms. This translates to a large number of node traversals. To overcome this problem, we have proposed a new strategy for branching on a set of linear branchingfunctions, which depend linearly on the search variables. This leads to a significant reduction in the dimensionality of the search space. The construction of linear underestimators for a class of functions is also presented. The CAMD problem that is considered is the design of optimal solvents to be used as cleaning agents in lithographic printing.     

Mixed-integer linear programming models for batch sterilization of packaged-foods plants

Batch sterilization with individual retorts is a common mode of operation in many food-canning plants. Although high-speed processing with continuous rotary or hydrostatic retort systems is used in very large canning factories, such systems are not economically feasible in the majority of small- to medium-sized canneries. In such canneries, sterilization is carried out in a battery of retorts as a batch process. Although the unloading and reloading operations for each retort are labor intensive, a well-designed and managed plant can operate with surprising efficiency if it has the optimum number of retorts and scheduling of retort operation. The objective of this research was to present two mathematical models for sterilization scheduling in food-canning plants. The first model developed is for the case where given amount of different canned food products with specific quality requirements would be sterilized within a minimum plant operation time in an autoclave of given capacity. The second model addresses the problem of maximizing the amount of sterilized products in an autoclave of given capacity for given plant operation time. The developed models were based on mixed-integer linear programming and incorporated the possibility of simultaneous sterilization. Simultaneous sterilization applies mainly to small canneries with few retorts. In these situations, retorts often operate with only partial loads because of the small lot sizes, and they are severely under-utilized. In order to demonstrate the feasibility of the mixed-integer linear programming (MILP) models, several examples involving the sterilization of different products were included in this research. The methodology proposed in this study is of special relevance for small- and medium-sized food-canning plants that normally work with many different products at the same time.     

New mixed integer approach to solve a multi-level capacitated disassembly lot-sizing problem with defective items and backlogging

The disassembly process has attracted mounting interest due to growing green concerns. This paper addresses the capacitated dynamic lot-sizing problem with external procurement, defective and backordered items, setup times, and extra capacity. The problem is to determine how many end-of-life products to disassemble during each period. We propose a new mixed-integer programming (MIP) approach to formulate the problem under study in order to maximize the disassembly-process gain, which is obtained as the difference between the revenue achieved by resale of the items recovered after disassembly and the costs tied to operating the disassembly tasks. Several numerical tests using the well-known CPLEX solver proved that this new model can find the optimal disassembly schedule for most test instances within an acceptable computational time. Furthermore, we led sensitivity studies on disassembly capacity, setup time and procurement cost. Test results validate the power of the suggested model and provide helpful insights for industry practitioners.     

Solving an extended multi-row facility layout problem with fuzzy clearances using GA

Multi-row facility layout problem (MRFLP) is a class of facility layout problems, which decides upon the arrangement of facilities in some fixed numbers of rows in order to minimize material handling cost. Nowadays, according to the new layout requirements, the facility layout problems (FLPs) have many applications such as hospital layout, construction site layout planning and layout of logistics facilities. Therefore, we study an extended MRFLP, as a novel layout problem, with the following main assumptions: 1) the facilities are arranged in a two-dimensional area and without splitter rows, 2) multiple products are available, 3) distance between each pair of facilities, due to inaccurate and flexible manufacturing processes and other limitations (such as WIPs, industrial instruments, transportation lines and etc.), is considered as fuzzy number, and 4) the objective function is considered as minimizing the material handling and lost opportunity costs. To model these assumptions, a nonlinear mixed-integer programming model with fuzzy constraints is presented and then converted to a linear mixed-integer programming model. Since the developed model is an NP-hard problem, a genetic algorithm approach is suggested to find the best solutions with a minimum cost function. Additionally, three different crossover methods are compared in the proposed genetic algorithm and finally, a sensitivity analysis is performed to discuss important parameters.     

制造系统的递阶滚动优化调度模型

研究的对象是只有一台不可靠（failure-prone)机器的非完全柔性制造系统，该系统能生产多种产品，但在同一时刻只能生产一种产品，并且当机器由生产一种产品向生产另一种产品切换时，需要考虑setup时间及其成本，待决策变量是setup序列及产品生产率，本文基于非完全柔性制造系统的特点，引入递阶层控的思想，采用新的递阶结构框架和阈值控制策略，对问题进行分解，建立了考虑setup时间及成本的递阶流率控制最优化调度模型，并给出了递阶的滚动优化算法，仿真结果表明，这种调度策略更易于工程实现。     

Predictive models with endogenous variables for quality control in customized scenarios affected by multiple setups

The crescent demand for customized products has challenged industries with reduced lot sizes. As a result, frequent product model changing and short series of observable variables decreased the performance of many traditional tools used in process control. This paper proposes the use of endogenous variables in predictive models aimed at overcoming the multiple setup and short production runs problems found in customized manufacturing systems. The endogenous variables describe the type/model of manufactured products, while the response variable predicts a product quality characteristic. Three robust predictive models, ARIMA, structural model with stochastic parameters fitted by Kalman filter, and Partial Least Squares (PLS) regression, are tested in univariate time series relying on endogenous variables. The PLS modeling yielded better predictions in real manufacturing data, while the structural model led to more robust results in simulated data.     

Annual production budget in the beverage industry

Driven by a real-world application in the beverage industry, this paper provides a design of a new VNS variant to tackle the annual production budget problem. The problem consists of assigning and scheduling production lots in a multi-plant environment, where each plant has a set of filling lines that bottle and pack drinks. Plans also consider final product transfers between the plants. Our algorithm fixes setup variables for family of products and determines production, inventory and transfer decisions by solving a linear programming (LP) model. As we are dealing with very large problem instances, it is inefficient and unpractical to search the entire neighborhood of the incumbent solution at each iteration of the algorithm. We explore the sensitivity analysis of the LP to guide the partial neighborhood search. Dual-reoptimization is also used to speed-up the solution procedure. Tests with instances from our case study have shown that the algorithm can substantially improve the current business practice, and it is more competitive than state-of-the-art commercial solvers and other VNS variants.     

Optimising multi-product multi-chance-constraint inventory control system with stochastic period lengths and total discount under fuzzy purchasing price and holding costs

While the usual assumptions in multi-periodic inventory control problems are that the orders are placed at the beginning of each period (periodic review) or depending on the inventory level they can happen at any time (continuous review), in this article, we relax these assumptions and assume that the periods between two replenishments of the products are independent and identically distributed random variables. Furthermore, assuming that the purchasing price are triangular fuzzy variables, the quantities of the orders are of integer-type and that there are space and service level constraints, total discount are considered to purchase products and a combination of back-order and lost-sales are taken into account for the shortages. We show that the model of this problem is a fuzzy mixed-integer nonlinear programming type and in order to solve it, a hybrid meta-heuristic intelligent algorithm is proposed. At the end, a numerical example is given to demonstrate the applicability of the proposed methodology and to compare its performance with one of the existing algorithms in real world inventory control problems.     

Multiple lot-sizing decisions with an interrupted geometric yield and variable production time

This study examines a multiple lot-sizing problem for a single-stage production system with an interrupted geometric distribution, which is distinguished in involving variable production lead-time. In a finite number of setups, this study determined the optimal lot-size for each period that minimizes total expected cost. The following cost items are considered in optimum lot-sizing decisions: setup cost, variable production cost, inventory holding cost, and shortage cost. A dynamic programming model is formulated in which the duration between current time and due date is a stage variable, and remaining demand and work-in-process status are state variables. This study then presents an algorithm for solving the dynamic programming problem. Additionally, this study examines how total expected costs of optimal lot-sizing decisions vary when parameters are changed. Numerical results show that the optimum lot-size as a function of demand is not always monotonic.     

基于异步时间段的原油混输调度连续时间建模研究

采用严格的数学规划方法对沿海炼厂的原油混输调度问题进行了建模和求解,提出了一个基于异步时间段的连续时间混合整数非线性规划(MINLP)数学模型。该模型具有整型变量少,求解快的优点。采用求解一系列MILP来近似求解非凸的MINLP,避免了原油混输MILP模型产生的浓度不一致问题。文中采用提出的新模型和算法对文献中的9个实例进行了计算,相同计算条件的4个实例比离散时间模型效率提高86％-1011％。