A hybrid VNS approach for the short-term production planning and scheduling: A case study in the pulp and paper industry

Mathematical formulations for production planning are increasing complexity, in order to improve their realism. In short-term planning, the desirable level of detail is particularly high. Exact solvers fail to generate good quality solutions for those complex models on medium- and large-sized instances within feasible time. Motivated by a real-world case study in the pulp and paper industry, this paper provides an efficient solution method to tackle the short-term production planning and scheduling in an integrated mill. Decisions on the paper machine setup pattern and on the production rate of the pulp digester (which is constrained to a maximum variation) complicate the problem. The approach is built on top of a mixed integer programming (MIP) formulation derived from the multi-stage general lotsizing and scheduling problem. It combines a Variable Neighbourhood Search procedure which manages the setup-related variables, a specific heuristic to determine the digester's production speeds and an exact method to optimize the production and flow movement decisions. Different strategies are explored to speed-up the solution procedure and alternative variants of the algorithm are tested on instances based on real data from the case study. The algorithm is benchmarked against exact procedures.     

A hierarchical/relational approach to modeling

We describe a hierarchical/relational approach to math programming modeling. The approach transforms free-form generic modeling constructs into linear and nonlinear models which are independent of end-user data structures. The underlying relationships with graph-based interfaces and the inherent aggregation/disaggregation capabilities of the approach are also discussed.The modeling approach will be illustrated with several process industry applications including distribution planning, operations planning, and production scheduling.     

Dynamic scheduling in flexible assembly system based on timed Petri nets model

This paper investigates a scheduling model for optimal production sequencing in a flexible assembly system. The system features a set of machines working together in the same workspace, with each machine performing a subset of operations. Three constraints are considered: (1) the precedence relation among the operations specified by the assembly tree; (2) working space that limits concurrent operations; and (3) the variation of process time. The objective is to find both a feasible assignment of operations to machines and schedule tasks in order to minimize the completion time for a single product or a batch of products. The assembly process is modeled using timed Petri nets and task scheduling is solved with a dynamic programming algorithm. The method calculates the time required precisely. A detailed case study is discussed to show the effectiveness of the model and algorithm.     

An Integrated Method for Planning and Scheduling to Minimize Tardiness

We combine mixed integer linear programming (MILP) and constraint programming (CP) to minimize tardiness in planning and scheduling. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. We consider two objectives: minimizing the number of late tasks, and minimizing total tardiness. Our main theoretical contribution is a relaxation of the cumulative scheduling subproblem, which is critical to performance. We obtain substantial computational speedups relative to the state of the art in both MILP and CP. We also obtain much better solutions for problems that cannot be solved to optimality.     

An application to support the temporal and spatial distributed decision-making process in supply chain collaborative planning

In the context of supply chains operations planning, mathematical programming models have been mainly used for centralised decision-making. However, the supply chain (SC) members not always agree on the alignment of individual decisions to SC-wide objectives and are usually reluctant to share all the required SC-wide information. For these reasons, SC decentralised decision making, in which different decisional units have to be coordinated to achieve a certain level of SC performance, is the most usual situation. In this collaborative planning (CP) context, spatial and temporal integration among the different SC decisional parts has to be considered. This paper aims to develop an application which supports the integrated modelling and execution of the CP decision-making process in SCs made up of several decisional centres (DCs) which make decisions based on mathematical programming models (as in Advanced Planning Systems) under temporal and spatial integration. The described application has been used to assist the CP of a real ceramic SC. The results are also reported.     

A Hybrid Method for the Planning and Scheduling

We combine mixed integer linear programming (MILP) and constraint programming (CP) to solve planning and scheduling problems. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. Tasks assigned to a facility may run in parallel subject to resource constraints (cumulative scheduling). We solve minimum cost problems, as well as minimum makespan problems in which all tasks have the same release date and deadline. We obtain computational speedups of several orders of magnitude relative to the state of the art in both MILP and CP.     

Integrated process planning and scheduling in a supply chain

This paper deals with the integration of process planning and scheduling, which is one of the most important functions in a supply chain to achieve high quality products at lower cost, lower inventory, and high level of performance. Solving the problem is essential for the generation of flexible process sequences with resource selection and for the decision of the operation schedules that can minimize makespan. We formulate a mixed integer programming model to solve this problem of integration. This model considers alternative resources: sequences and precedence constraints. To solve the model, we develop a new evolutionary search approach based on a topological sort. We use the topological sort to generate a set of feasible sequences in the model within a reasonable computing time. Since precedence constraints between operations are handled by the topological sort, the developed evolutionary search approach produces only feasible solutions. The experimental results using various sizes of problems provide a way to demonstrate the efficiency of the developed evolutionary search approach.     

考虑装置运行惯性的炼油过程生产作业优化研究

针对炼油过程生产装置运行的大惯性特性,研究了装置生产方案切换作业的调度优化问题。通过分析装置运行惯性及其产生的方案切换过渡过程,给出了调度优化的作业时间、方案切换和物料加工特点,利用逻辑命题进行了模型化描述。在此基础上,基于连续时间表达,建立了炼油过程生产作业调度优化模型,实现生产利润最大化。通过一个炼油厂生产实例验证了模型的可行性和有效性。     

An optimization approach for the lot sizing and scheduling problem in the brewery industry

This study considers a production lot sizing and scheduling problem in the brewery industry. The underlying manufacturing process can be basically divided into two main production stages: preparing the liquids including fermentation and maturation inside the fermentation tanks; and bottling the liquids on the filling lines, making products of different liquids and sizes. This problem differs from other problems in beverage industries due to the relatively long lead times required for the fermentation and maturation processes and because the “ready” liquid can remain in the tanks for some time before being bottled. The main planning challenge is to synchronize the two stages (considering the possibility of a “ready” liquid staying in the tank until bottling), as the production bottlenecks may alternate between these stages during the planning horizon. This study presents a novel mixed integer programming model that represents the problem appropriately and integrates both stages. In order to solve real-world problem instances, MIP-based heuristics are developed, which explore the model structure. The results show that the model is able to comprise the problem requirements and the heuristics produce relatively good-quality solutions.     

The order fulfillment planning problem considering multi-site order allocation and single-site shop floor scheduling

The order fulfillment planning process in the thin film transistor–liquid crystal display panel industry is analyzed in this study. A two-phase order fulfillment planning structure is proposed, including the multi-site order allocation among module factories and single-site shop floor scheduling in each factory. In the first phase, the order allocation problem is solved using a mathematical programming model considering practical characteristics, including product structures, customer preferences, alternative bill-of-material, and production constraints. In the second phase, a constraint-based simulation scheduling algorithm is developed to address the scheduling problem in each module factory for determining the ideal order release time. Since production planning and scheduling are dealt with different time scales, the major challenge for the integration lies in the large problem size of the optimization model and becomes intractable. Most of the time bucket-based planning methods in the past literature simplify their scheduling models, but in this paper the detailed shop floor operations and processing behaviors are considered, such as changeover time, processing sequence of orders, and machine characteristics. Finally, a practical case in Taiwan will be employed to testify the feasibility of the proposed order fulfillment planning process; meanwhile, through the analysis of experiments, the adaptability and comparison of different planning approaches in an environment of various market demands are discussed.     

Multi-choice multi-objective mathematical programming model for integrated production planning: a case study

This article develops a multi-choice multi-objective linear programming model in order to solve an integrated production planning problem of a steel plant. The aim of the integrated production planning problem is to integrate the planning sub-functions into a single planning operation. The sub-functions are formulated by considering the capacity of different units of the plant, cost of raw materials from various territories, demands of customers in different geographical locations, time constraint for delivery the products, production cost and production rate at different stages of production process. Departure cost is also considered in the formulation of mathematical programming model. Some of the parameters are decided from a set of possible choices, therefore such parameters are considered as multi-choice type. Multi-choice mathematical programming problem cannot be solved directly. Therefore an equivalent multi-objective mathematical programming model is established in order to find the optimal solution of the problem. Computation of the mathematical programming model is performed with the practical production data of a plant to study the methodology.     

Solving two-machine assembly scheduling problems with inventory constraints

This paper considers a scheduling problem with component availability constraints in a supply chain consisting of two manufacturing facilities and a merge-in-transit facility. Three mixed-integer programming (MIP) models and a constraint programming (CP) model are compared in an extensive numerical study. Results show that when there are no components shared among the two manufacturers, the MIP model based on time-index variables is the best for proving optimality for problems with short processing times whereas the CP model tends to perform better than the others for problems with a large range of processing times. When shared components are added, the performance of all models deteriorates, with the time-indexed MIP providing the best results. By explicitly modelling the dependence of scheduling decisions on the availability of component parts, we contribute to the literature on the integration of inventory and scheduling decisions, which is necessary for solving realistic supply chain problems.     

A genetic algorithm-based approach for solving the resource-sharing and scheduling problem

We introduce a heuristic that is based on a unique genetic algorithm (GA) to solve the resource-sharing and scheduling problem (RSSP). This problem was previously formulated as a continuous-time mixed integer linear programming model and was solved optimally using a branch-and-bound (B&B) algorithm. The RSSP considers the use of a set of resources for the production of several products. Producing each product requires a set of operations with precedence relationships among them. Each operation can be performed using alternative modes which define the subset of the resources needed, and an operation may share different resources simultaneously. The problem is to select a single mode for each operation and accordingly to schedule the resources, while minimizing the makespan time. The GA we propose is based on a new encoding schema that adopts the structure of a DNA in nature. In our experiments we compared the effectiveness and runtime of our GA versus a B&B algorithm and two truncated B&B algorithms that we developed on a set of 118 problem instances. The results demonstrate that the GA solved all the problems (10 runs each), and reaches optimality in 75% of the runs, had an average deviation of less than 1% from the optimal makespan, and a runtime that was much less sensitive to the size of the problem instance.     

间歇过程生产调度建模的研究

生产调度是为实现某一目的而对共同使用的资源进行时间上的分配.调度中存在大量的模糊因素,将模糊的思想运用到调度领域可以帮助决策者进行有效决策.本文提出一种基于模糊规划的间歇过程生产调度建模方法及其模糊优化的新算法.应用模糊集合论的方法,在已有模糊规划模型的基础上,针对间歇生产过程,分析调度中存在的模糊信息以及出现的形式和方式,将确定型生产调度模型的约束条件和目标方程中的参数模糊化,采用非精确的量化形式,以隶属函数来表示,建立基于模糊参数的生产调度模糊线性规划模型MIFCLP.通过对一个调度问题实例进行了仿真,仿真结果证明,采用模糊模型更容易得到可行解,采用模糊线性规划解决间歇生产调度问题是一种有效方法.     

Lot sizing and furnace scheduling in small foundries

A lot sizing and scheduling problem prevalent in small market-driven foundries is studied. There are two related decision levels: (1) the furnace scheduling of metal alloy production, and (2) moulding machine planning which specifies the type and size of production lots. A mixed integer programming (MIP) formulation of the problem is proposed, but is impractical to solve in reasonable computing time for non-small instances. As a result, a faster relax-and-fix (RF) approach is developed that can also be used on a rolling horizon basis where only immediate-term schedules are implemented. As well as a MIP method to solve the basic RF approach, three variants of a local search method are also developed and tested using instances based on the literature. Finally, foundry-based tests with a real-order book resulted in a very substantial reduction of delivery delays and finished inventory, better use of capacity, and much faster schedule definition compared to the foundry's own practice.     

智能RGV动态调度多目标规划模型

智能轨道式自动引导车(Rail Guided Vehicle,RGV)的动态调度模型及其算法研究是一个热门的加工规划问题。针对智能RGV的动态调度问题的不同情形,建立线性加权情况下时间函数与相对稳定性的多目标规划模型,并使用多段遗传编码的遗传算法进行求解。用多组序机器在一定加工件数内最小完成时间与单组序机器最小完成时间之比验证模型。根据加工系统作业参数均值以及与两种调度方案所需时间进行对比,与传统算法相比时间平均缩短13%,证明算法优化的执行具有可行性,在保证加工时间的同时提高了加工系统的稳定性。     

A constraint programming approach to tool allocation and production scheduling in flexible manufacturing systems

This paper presents a constraint programming (CP) methodology to deal with the scheduling of flexible manufacturing systems (FMSs). The proposed approach, which consists of both a model and a search strategy, handles several features found in industrial environments, such as limitations on number of tools in the system, lifetime of tools, as well as tool magazine capacity of machines. In addition, it tackles the problem in a integrated way by considering tool planning and allocation, machine assignment, part routing, and task timing decisions altogether in the approach. The formulation, which is able to take into account a variety of objective functions, has been successfully applied to the solution of test problems of various sizes and degrees of difficulty.     

Genetic algorithms in integrated process planning and scheduling

Process planning and scheduling are actually interrelated and should be solved simultaneously. Most integrated process planning and scheduling methods only consider the time aspects of the alternative machines when constructing schedules. The initial part of this paper describes a genetic algorithm (GA) based algorithm that only considers the time aspect of the alternative machines. The scope of consideration is then further extended to include the processing capabilities of alternative machines, with different tolerance limits and processing costs. In the proposed method based on GAs, the processing capabilities of the machines, including processing costs as well as number of rejects produced in alternative machine are considered simultaneously with the scheduling of jobs. The formulation is based on multi-objective weighted-sums optimization, which are to minimize makespan, to minimize total rejects produced and to minimize the total cost of production. A comparison is done w ith the traditional sequential method and the multi-objective genetic algorithm (MOGA) approach, based on the Pareto optimal concept.     

Comparative study of the applicability of fuzzy multi-objective linear programming models through cost-effective analysis for mold manufacturing

The mold-manufacturing process consists of prototype design, production, assembly, and testing. As products tend to vary, have short due dates, and life cycles, are highly precise and must be responsiveness to customers, production system planning is complex and the relationship between outsourcing capability and in-house capacity is crucial to mold-manufacturing. Differentiation of core operations vs. non-core operations in internal vs. external environments and time control are essential for mold manufacturing when planning production systems. To analyze the cost-effectiveness of capacity planning and its relationship to suppliers, this work applies a novel fuzzy multi-objective linear programming model. Considered factors are order quantity allocation, due dates, manufacturing quantity, capacity, defect rates, back-log, and the purchasing discount. The applicability of three fuzzy theories is assessed using total costs, punishment costs, and crashing costs. Implementation results demonstrate the potentials for cost-effective capacity planning and outsourcing, and identify the applicability of these fuzzy theories to a specific mold-manufacturing case.     

求解炼钢连铸生产调度问题的改进算法

将炼钢连铸生产调度问题抽象为混和流水车间调度,建立了0-1型混合整数线性规划模型,并提出了一种遗传和线性规划相结合的求解方法。该模型通过优化钢水传搁时间来满足钢水的温度要求,通过最小化浇次开浇提前/拖期惩罚来协调连铸与热轧间的生产节奏。在算法设计中,给出了一种染色体编码来表示炉次设备指派与炉次在设备上的加工顺序方案,并探讨了相应的遗传操作。最后,仿真实验的结果表明了该算法的有效性。