Genetic algorithm for large-size multi-stage batch plant scheduling

This paper presents a heuristic approach based on genetic algorithm (GA) for solving large-size multi-stage multi-product scheduling problem (MMSP) in batch plant. The proposed approach is suitable for different scheduling objectives, such as total process time, total flow time, etc. In the algorithm, solutions to the problem are represented by chromosomes that will be evolved by GA. A chromosome consists of order sequences corresponding to the processing stages. These order sequences are then assigned to processing units according to assignment strategies such as forward or backward assignment, active scheduling technique or similar technique, and some heuristic rules. All these measures greatly reduce unnecessary search space and increase the search speed. In addition, a penalty method for handling the constraints in the problem, e.g., the forbidden changeovers, is adopted, which avoids the infeasibility during the GA search and further greatly increases the search speed.     

A novel MILP formulation for short-term scheduling of multi-stage multi-product batch plants with sequence-dependent constraints

This paper presents a continuous-time mixed-integer linear programming (MILP) model for short-term scheduling of multi-stage multi-product batch plants. The model determines the optimal sequencing and the allocation of customer orders to non-identical processing units by minimizing the earliness and tardiness of order completion. This is a highly combinatorial problem, especially when sequence-dependent relations are considered such as the setup time between consecutive orders. A common approach to this scheduling problem relies on the application of tetra-index binary variables, i.e. (order, order, stage, unit) to represent all the combinations of order sequences and assignments to units in the various stages. This generates a huge number of binary variables and, as a consequence, much time is required for solutions. This paper proposes a novel formulation that replaces the tetra-index binary variables by one set of tri-index binary variables (order, order, stage) without losing the model's generality. By the elimination of the unit index, the new formulation requires considerably fewer binary variables, thus significantly shortening the solution time.     

Batch selection,assignment and sequencing in multi-stage multi-product processes

The scheduling of multi-product, multi-stage batch processes is industrially important because it allows us to utilize resources that are shared among competing products in an optimal manner. Previously proposed methods consider problems where the number and size of batches is known a priori. In many instances, however, the selection and sizing (batching) of batches is or should be an optimization decision. To address this class of problems we develop a novel mixed-integer linear programming (MILP) formulation that involves three levels of discrete decisions: selection of batches, assignment of batches to units and sequencing of batches in each unit. Continuous decision variables include sizing and timing of batches. We consider various objective functions: minimization of makespan, earliness, lateness and production cost, as well as maximization of profit, an objective not addressed by previous multi-stage scheduling methods. To enhance the solution of the proposed MILP model we propose symmetry breaking constraints, develop a preprocessing algorithm for the generation of constraints that reduce the number of feasible solutions, and fix sequencing variables based upon time window information. The model enables the optimization of batch selection, assignment and sequencing decisions simultaneously and is shown to yield solutions that are better than those obtained by existing sequential optimization methods.     

Short-term scheduling and recipe optimization of blending processes

The main objective of this paper is to develop an integrated approach to coordinate short-term scheduling of multi-product blending facilities with nonlinear recipe optimization. The proposed strategy is based on a hierarchical concept consisting of three business levels: Long-range planning, short-term scheduling and process control. Long-range planning is accomplished by solving a large-scale nonlinear recipe optimization problem (multi-blend problem). Resulting blending recipes and production volumes are provided as goals for the scheduling level. The scheduling problem is formulated as a mixed-integer linear program derived from a resource-task network representation. The scheduling model permits recipe changeovers in order to utilize an additional degree of freedom for optimization. By interpreting the solution of the scheduling problem, new constraints can be imposed on the previous multi-blend problem. Thus bottlenecks arising during scheduling are considered already on the topmost long-range planning level. Based on the outlined approach a commercial software system has been designed to optimize the operation of in-line blending and batch blending processes. The application of the strategy and software is demonstrated by a detailed case study.     

Discrete-time mixed-integer programming models and solution methods for production scheduling in multistage facilities

We address the problem of production scheduling in multi-product multi-stage batch plants. Unlike most of the previous works, which propose continuous-time models, we study discrete-time mixed-integer programming models and solution methods. Specifically, we discuss two models based on network representations of the facility and develop two new models inspired by the Resource-Constrained Project Scheduling Problem. Furthermore, we propose different solution methods, including tightening methods based on processing unit availability, a reformulation based on processing unit occupancy, and an algorithm to refine approximate solutions for large-scale instances. Finally, we present a comprehensive computational study which shows that speedups of up to four orders of magnitude in are observed when our models and methods are compared to existing approaches.     

考虑能耗影响的多产品间歇化工过程优化排序

提出一种用于间歇生产的多产品化工厂排序的多目标优化的混合整数非线性规划(MINLP)模型,其目标函数同时考虑了总生产时间最短和能耗最小的影响,定义了关于过程能耗的影响因子及决策因子,用以对总生产时间和能耗的影响进行权衡。采用改进的模拟退火算法(SA)对具有不同决策因子和能耗影响因子情况下的算例进行了求解,结果表明,该模型能够较好地反映能耗因素在多产品厂排序问题中的影响,使排序结果达到生产时间和能耗影响的综合最优。     

有并行设备的多目的间歇生产调度

针对有并行设备的多目的间歇生产调度问题,建立了以所有订单生产步骤排序和订单各阶段所选用分配规则为决策变量的调度优化模型,并提出了列队竞争算法求解该模型的有效个体表示方法及变异操作策略。实例计算表明:所提出方法的求解效率优于文献中所报道的方法,特别在求解有多台并行设备的调度问题时能得到比文献更好的结果,表现出其求解大规模复杂多目的调度问题的潜力。     

Time representations and mathematical models for process scheduling problems

During the last 15 years, many mathematical models have been developed in order to solve process operation scheduling problems, using discrete or continuous-time representations. In this paper, we present a unified representation and modeling approach for process scheduling problems. Four different time representations are presented with corresponding strengthened formulations that rely on exploiting the non-overlapping graph structure of these problems through maximum cliques and bicliques. These formulations are compared, and applied to single-stage and multi-stage batch scheduling problems, as well as crude-oil operations scheduling problems. We introduce three solution methods that can be used to achieve global optimality or obtain near-optimal solutions depending on the stopping criterion used. Computational results show that the multi-operation sequencing time representation is superior to the others as it allows efficient symmetry-breaking and requires fewer priority-slots, thus leading to smaller model sizes.     

A monolithic approach to vehicle routing and operations scheduling of a cross-dock system with multiple dock doors

Cross-docking is a logistic strategy for moving goods from suppliers to customers via a cross-dock terminal with no permanent storage. The operational planning of a cross-dock facility involves different issues such as vehicle routing, dock door assignment and truck scheduling. The vehicle routing problem seeks the optimal routes for a homogeneous fleet of vehicles that sequentially collects goods at pickup points and delivers them to their destinations. The truck scheduling problem deals with the timing of unloading and reloading operations at the cross-dock. This work introduces a mixed-integer linear programming formulation for the scheduling of single cross-dock systems that, in addition to selecting the pickup/delivery routes, simultaneously decides on the dock door assignment and the truck scheduling at the cross-dock. The proposed monolithic formulation is able to provide near-optimal solutions to medium-size problems involving up to 70 transportation orders, 16 vehicles and 7 strip/stack dock doors at acceptable CPU times.     

Novel continuous-time formulations for scheduling multi-stage batch plants with identical parallel units

Scheduling production optimally in multi-stage multi-product plants is a very difficult problem that has received limited attention. While the case of non-identical parallel units has been addressed, the case of identical parallel units is equally worthy of attention, as many plants are or can be approximated as such. In this paper, we construct and compare several novel MILP formulations for the latter. In contrast to the existing work, we increase solution efficiency by considering each stage as a block of multiple identical units, thereby eliminating numerous binary variables for assigning batches to specific units. Interestingly, a novel formulation using an adjacent pair-wise sequencing approach proves superior to slot-based formulations. Furthermore, we develop heuristic variations of our proposed formulations to address moderate-size problems. A novel heuristic strategy inspired from list scheduling algorithms seems to be efficient for moderate-size problems and scales well with problem size.     

Scheduling Model for a Multi‐Product Batch Plant Using a Pre‐Ordering Approach

A scheduling model for a multi‐product, multistage batch plant with parallel units is presented. The objective is to maximize the weighted completion times of orders in every processing stage while imposing a penalty on the slower orders. The proposed model uses the continuous‐time representation mode and describes the allocations of tasks, units and stages by a set of binary variables. In order to reduce the model size and provide a more effective solution to the model, a pre‐ordering approach that sorts the processing sequence of orders is developed. The pre‐ordering approach identifies the infeasible assignments through which the number of binary variables is significantly reduced. Illustrative examples are provided to show that the size of the proposed model is small, and therefore, needs much less computational effort in comparison with the existing models in the literature.     

Long-term scheduling of a single-unit multi-product continuous process to manufacture high performance glass

In this paper we address the long-term scheduling of a real world multi-product single stage continuous process for manufacturing glass. This process features long minimum run lengths, and sequence dependent changeovers of the order of days, with high transition costs. The long-term scheduling involves extended time horizons that lead to large scale mixed-integer linear programming (MILP) scheduling models. In order to address the difficulties posed by the size of the models, three different rolling horizon algorithms based on different models and time aggregation techniques are developed. The models are based on the continuous time slot MILP model, and on the traveling salesman model proposed by Erdirik-Dogan and Grossmann (2008). Due to the particular characteristics of the process under study, several new features, including minimum run lengths and changeovers across due dates, are proposed. The performance and characteristics of the proposed rolling horizon algorithms are discussed for one industrial example.     

新的多产品间歇生产调度的MILP模型

提出了一种新的多产品厂间歇调度问题的连续时间混合整数线性规划 (MILP)模型,该模型的整数变量体系不依赖于时间块(或者事件点)的概念,并且利用了变量物理概念上的对称互补性,使得与传统的建模方法相比不仅整数变量的数目减少了一半以上,而且建模思想、建模理论都有了新的改进.通过对一个算例的考察证实了新模型可以快速地求得全局最优解.     

A rule-based genetic algorithm for the scheduling of single-stage multi-product batch plants with parallel units

This paper presents a heuristic rule-based genetic algorithm (GA) for large-size single-stage multi-product scheduling problems (SMSP) in batch plants with parallel units. SMSP have been widely studied by the researchers. Most of them used mixed-integer linear programming (MILP) formulation to solve the problems. With the problem size increasing, the computational effort of MILP increases greatly. Therefore, it is very difficult for MILP to obtain acceptable solutions to large-size problems within reasonable time. To solve large-size problems, the preferred method in industry is the use of scheduling rules. However, due to the constraints in SMSP, the simple rule-based method may not guarantee the feasibility and quality of the solution. In this study, a random search based on heuristic rules was proposed first. Through exploring a set of random solutions, better feasible solutions can be achieved. To improve the quality of the random solutions, a genetic algorithm-based on heuristic rules has been proposed. The heuristic rules play a very important role in cutting down the solution space and reducing the search time. Through comparative study, the proposed method demonstrates promising performance in solving large-size SMSP.     

Multi-period scheduling of a multi-stage multi-product bio-pharmaceutical process

There have been several works in the literature for scheduling of multi-product continuous processes with significant attention laid on short-term scheduling. This work presents a continuous-time model for multi-period scheduling of a multi-stage multi-product process from bio-pharmaceutical industry. The overall model is a mixed-integer linear programming (MILP) formulation based on state-task-network (STN) representation of the process using unit-specific event-based continuous-time representation. The proposed model is an extension of model by Shaik and Floudas (2007, Industrial & Engineering Chemistry Research, 46, 1764) with several new constraints to deal with additional features such as unit and sequence dependent changeovers, multiple intermediate due dates, handling of shelf-life and waste disposal, and penalties on backlogs and late deliveries. Improved tightening and sequencing constraints have been presented. The validity of the proposed model has been illustrated through an example from the literature.     

用于多产品间歇化工过程排序的模拟退火算法

提出了一种适用于多产品间歇化工过程排序的改进模拟退火算法 ,该算法采用了非平衡、多次退火策略及多个相邻解产生方法 .通过对无限中间储罐 (UIS)类问题的研究表明 ,同已有的方法相比 ,该方法求解精度高 ,计算速度快 ,适合于求解多产品间歇化工过程的排序问题 .     

Nonlinear scheduling with time-variable electricity prices using sensitivity-based truncations of wavelet transforms

We propose an algorithm for scheduling subject to time-variable electricity prices using nonlinear process models that enables long planning horizons with fine discretizations. The algorithm relies on a reduced-space formulation and enhances our previous work (Schäfer et al., Comput Chem Eng, 2020;132:106598) by a sensitivity-based refinement procedure. We therein expose the coefficients of the wavelet transform of the time series of independent process variables to the optimizer. The problem size is reduced by truncating the transform and iteratively adjusted using Lagrangian multipliers. We apply the algorithm to the scheduling of a multi-product air separation unit. The nonlinear power consumption characteristic is replaced by an artificial neural network trained on data from a rigorous model. We demonstrate that the proposed algorithm reduces the number of optimization variables by more than one order of magnitude, whilst furnishing feasible schedules with insignificant losses in objective values compared to solutions considering the full dimensionality.     

Integrated process design,scheduling, and model predictive control of batch processes with closed-loop implementation

Simultaneous evaluation of multiple time scale decisions has been regarded as a promising avenue to increase the process efficiency and profitability through leveraging their synergistic interactions. Feasibility of such an integral approach is essential to establish a guarantee for operability of the derived decisions. In this study, we present a modeling methodology to integrate process design, scheduling, and advanced control decisions with a single mixed-integer dynamic optimization (MIDO) formulation while providing certificates of operability for the closed-loop implementation. We use multi-parametric programming to derive explicit expressions for the model predictive control strategy, which is embedded into the MIDO using the base-2 numeral system that enhances the computational tractability of the integrated problem by exponentially reducing the required number of binary variables. Moreover, we apply the State Equipment Network representation within the MIDO to systematically evaluate the scheduling decisions. The proposed framework is illustrated with two batch processes with different complexities.     

A hybrid system of heuristics and simulated annealing for large size scheduling problems of batch processes with pipeless intermediate storage

This paper describes a new scheduling solution for large number multi-product batch processes with complex intermediate storage system. Recently many batch chemical industries have turned their attention to a more efficient system known as a pipeless batch system. But existing plants need to change their systems to pipeless systems, piece by piece. In this case, current systems are changed to pipeless systems by way of non critical process operations such as through the use of intermediate storage. We have taken the conventional batch plant with a pipeless storage system as an objective process. Although the operation of a pipeless storage system becomes more complex, its efficiency is very high. With this system, all of the storage should be commonly used by any batch unit. For this reason, solving the optimal scheduling problem of this system with a mathematical method is very difficult. Despite the attempts of many previous researches, there has been no contribution which solves the scheduling of intermediate storage for complex batch processes. In this paper, we have developed a hybrid system of heuristics and Simulated Annealing (SA) for large multi-product processes using a pipeless storage system. The results of this study show that the performance and computational time of this method are superior to that of SA and Rapid Access Extensive Search (RAES) methods.     

Simultaneous planning and scheduling of single-stage multi-product continuous plants with parallel lines

In this paper we present a multi-period mixed integer linear programming model for the simultaneous planning and scheduling of single-stage multi-product continuous plants with parallel units. While effective for short time horizons, the proposed scheduling model becomes computationally expensive to solve for long time horizons. In order to address this problem, we propose a bi-level decomposition algorithm in which the original problem is decomposed into an upper level planning and a lower level scheduling problem. For the representation of the upper level, we propose an MILP model which is based on a relaxation of the original model, but accounts for the effects of scheduling by incorporating sequencing constraints, which results in very tight upper bounds. In the lower level the simultaneous planning and scheduling model is solved for a subset of products predicted by the upper level. These sub-problems are solved iteratively until the upper and lower bounds converge. A number of examples are presented that show that the planning model can often obtain the optimal schedule in one single iteration.