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 precedence-based and heuristic approach for short-term scheduling of multipurpose batch plants

Many continuous-time formulations have been proposed during the last decades for short-term scheduling of multipurpose batch plants. Although these models establish advantages over discrete-time representations, they are still inefficient in solving moderate-size problems, such as maximization of profit in long horizon, and minimization of makespan. Unlike existing literature, this paper presents a new precedence-based mixed integer linear programming (MILP) formulation for short-term scheduling of multipurpose batch plants. In the new model, multipurpose batch plants are described with a modified state-task network (STN) approach, and binary variables express the assignments and sequences of batch processing and storing. To eliminate the drawback of precedence-based formulations which commonly include large numbers of batches, an iterative procedure is developed to determine the appropriate number of batch that leads to global optimal solution. Moreover, four heuristic rules are proposed to selectively prefix some binary variables to 0 or 1, thereby reducing the overall number of binary variables significantly. To evaluate model performance, our model and the best models reported in the literature (S&K model and I&F model) are utilized to solve several benchmark examples. The result comparison shows that our model is more effective to find better solution for complex problems when using heuristic rules. Note that our approach not only can handle unlimited intermediate storage efficiently as well as the I&F model, but also can solve scheduling problems in limited intermediate storage more quickly than the S&K model.     

Global optimization for scheduling refinery crude oil operations

In this work we present an outer-approximation algorithm to obtain the global optimum of a nonconvex mixed-integer nonlinear programming (MINLP) model that is used to represent the scheduling of crude oil movement at the front-end of a petroleum refinery. The model relies on a continuous time representation making use of transfer events. The proposed algorithm focuses on effectively solving a mixed-integer linear programming (MILP) relaxation of the nonconvex MINLP to obtain a rigorous lower bound (LB) on the global optimum. Cutting planes derived by spatially decomposing the network are added to the MILP relaxation of the original nonconvex MINLP in order to reduce the solution time for the MILP relaxation. The solution of this relaxation is used as a heuristic to obtain a feasible solution to the MINLP which serves as an upper bound (UB). The lower and upper bounds are made to converge to within a specified tolerance in the proposed outer-approximation algorithm. On applying the proposed technique to test examples, significant savings are realized in the computational effort required to obtain provably global optimal solutions.     

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.     

A tighter continuous time formulation for the cyclic scheduling of a mixed plant

In this paper, based on the cyclic scheduling formulation of Schilling and Pantelides [Schilling, G., & Pantelides, C. (1999). Optimal periodic scheduling of multipurpose plants. Computers& Chemical Engineering, 23, 635–655], we propose a continuous time mixed integer linear programming (MILP) formulation for the cyclic scheduling of a mixed plant, i.e. a plant composed of batch and continuous tasks. The cycle duration is a variable of the model and the objective is to maximize productivity. By using strengthening techniques and the analysis of small polytopes related to the problem formulation, we strengthen the initial formulation by tightening some initial constraints and by adding valid inequalities. We show that this strengthened formulation is able to solve moderate size problems quicker than the initial one. However, for real size cases, it remains difficult to obtain the optimal solution of the scheduling problem quickly. Therefore, we introduce MILP-based heuristic methods in order to solve these larger instances, and show that they can provide good feasible solutions quickly.     

A novel search framework for multi‐stage process scheduling with tight due dates

This article improves the original genetic algorithm developed by He and Hui (Chem Eng Sci. 2007; 62:1504–1527) and proposes a novel global search framework (GSF) for the large‐size multi‐stage process scheduling problems. This work first constructs a comprehensive set of position selection rules according to the impact factors analysis presented by He and Hui (in this publication in 2007), and then selects suitable rules for schedule synthesis. In coping with infeasibility emerging during the search, a penalty function is adopted to force the algorithm to approach the feasible solutions. The large‐size problems with tight due dates are challenging to the current solution techniques. Inspired by the gradient used in numerical analysis, we treat the deviation existing among the computational tests of the algorithm as evolutionary gradient. Based on this concept, a GSF is laid out to fully utilize the search ability of the current algorithm. Numerical experiments indicate that the proposed search framework solves such problems with satisfactory solutions. © 2010 American Institute of Chemical Engineers AIChE J, 2010     

An improvement-based MILP optimization approach to complex AWS scheduling

The automated wet-etch station (AWS) is one of the most critical stages of a modern semiconductor manufacturing system (SMS), which has to simultaneously deal with many complex constraints and limited resources. Due to its inherent complexity, industrial-sized automated wet-etch station scheduling problems are rarely solved through full rigorous mathematical formulations. Decomposition techniques based on heuristic, meta-heuristics and simulation-based methods have been traditionally reported in literature to provide feasible solutions with reasonable CPU times.This work introduces an improvement MILP-based decomposition strategy that combines the benefits of a rigorous continuous-time MILP (mixed integer linear programming) formulation with the flexibility of heuristic procedures. The schedule generated provides enhanced solutions over time to challenging real-world automated wet etch station scheduling problems with moderate computational cost. This methodology was able to provide more than a 7% of improvement in comparison with the best results reported in literature for the most complex problem instances analyzed.     

Design,synthesis and scheduling of multipurpose batch plants via an effective continuous-time formulation

Design, synthesis and scheduling issues are considered simultaneously for multipurpose batch plants. An earlier proposed continuous-time formulation for scheduling is extended to incorporate design and synthesis. Processing recipes are represented by the State-Task Network (STN). The superstructure of all possible plant designs is constructed according to the potential availability of all processing/storage units. The proposed model takes into account the trade-offs between capital costs, revenues and operational flexibility. Computational studies are presented to illustrate the effectiveness of the proposed formulation. Both linear and nonlinear models are included, resulting in MILP and mixed-integer nonlinear programming (MINLP) problems, respectively. The MILP problems are solved using a branch and bound method. Globally optimal solutions are obtained for the nonconvex MINLP problems based on a key property that arises due to the special structure of the resulting models. Comparisons with earlier approaches are also presented.     

Multi-bucket optimization for integrated planning and scheduling in the perishable dairy supply chain

This paper considers a dairy industry problem on integrated planning and scheduling of set yoghurt production. A mixed integer linear programming formulation is introduced to integrate tactical and operational decisions and a heuristic approach is proposed to decompose time buckets of the decisions. The decomposition heuristic improves computational efficiency by solving big bucket planning and small bucket scheduling problems. Further, mixed integer linear programming and constraint programming methodologies are combined with the algorithm to show their complementary strengths. Numerical studies using illustrative data with high demand granularity (i.e., a large number of small-sized customer orders) demonstrate that the proposed decomposition heuristic has consistent results minimizing the total cost (i.e., on average 8.75% gap with the best lower bound value found by MILP) and, the developed hybrid approach is capable of solving real sized instances within a reasonable amount of time (i.e., on average 92% faster than MILP in CPU time).     

Rolling horizon based planning and scheduling integration with production capacity consideration

The rolling horizon method has been proposed to address the integrated production planning and scheduling optimization problem. Since the method can generally result in small-scale optimization model and fast solution, it has been used in a number of applications in realistic industrial planning and scheduling problems. In this paper, it is first pointed out that the incorporation of valid production capacity information into the planning model can improve the solution quality in the rolling horizon solution framework. A novel method is then proposed to derive the production capacity information representing the detail scheduling model based on parametric programming technique. A heuristic process network decomposition strategy is further applied to reduce the computational effort needed for larger and more complex process networks. Several case studies have been studied, which illustrate the efficiency of the proposed methodology in improving the solution quality of rolling horizon method for integrated planning and scheduling optimization.     

多目标进化算法求解过程综合中的混合整数线性规划(MILP)与混合整数非线性规划问题(MINLP)

Steady-state non-dominated sorting genetic algorithm (SNSGA), a new form of multi-objective genetic algorithm, is implemented by combining the steady-state idea in steady-state genetic algorithms (SSGA) and the fitness assignment strategy of non-dominated sorting genetic algorithm (NSGA). The fitness assignment strategy is improved and a new self-adjustment scheme of crame is proposed. This algorithm is proved to be very efficient both computationally and in terms of the quality of the Pareto fronts produced with five test problems including GA difficult problem and GA deceptive one. Finally, SNSGA is introduced to solve multi-objective mixed integer linear programming (MILP) and mixed integer non-linear programming (MINLP) problems in process synthesis.     

An improved artificial bee colony algorithm for steelmaking–refining–continuous casting scheduling problem

Steelmaking–refining–Continuous Casting(SCC) scheduling is a worldwide problem, which is NP-hard. Effective SCC scheduling algorithms can help to enhance productivity, and thus make significant monetary savings. This paper develops an Improved Artificial Bee Colony(IABC) algorithm for the SCC scheduling. In the proposed IABC, charge permutation is employed to represent the solutions. In the population initialization, several solutions with certain quality are produced by a heuristic while others are generated randomly. Two variable neighborhood search neighborhood operators are devised to generate new high-quality solutions for the employed bee and onlooker bee phases, respectively. Meanwhile, in order to enhance the exploitation ability, a control parameter is introduced to conduct the search of onlooker bee phase. Moreover, to enhance the exploration ability,the new generated solutions are accepted with a control acceptance criterion. In the scout bee phase, the solution corresponding to a scout bee is updated by performing three swap operators and three insert operators with equal probability. Computational comparisons against several recent algorithms and a state-of-the-art SCC scheduling algorithm have demonstrated the strength and superiority of the IABC.     

改进的自适应模拟退火算法及其在过程综合中的应用

为有效解决化工过程综合中的MINLP问题，针对连续变量的模拟退火算法搜索慢的缺点，提出了一种改进的自适应模拟退火算法（Adaptive Simulated Algorithms,ASA)，采取自适应调整温度和搜索步长两种策略，大大加快搜索速度，提高最优解的质量。实算结果充分体现了所提出算法的优点，并很好地应用于化工过程综合问题。     

A decomposition approach for the scheduling of a steel plant production

In this paper we present a decomposition strategy for solving large scheduling problems using mathematical programming methods. Instead of formulating one huge and unsolvable MILP problem, we propose a decomposition scheme that generates smaller programs that can often be solved to global optimality. The original problem is split into subproblems in a natural way using the special features of steel making and avoiding the need for expressing the highly complex rules as explicit constraints. We present a small illustrative example problem, and several real-world problems to demonstrate the capabilities of the proposed strategy, and the fact that the solutions typically lie within 1–3% of the global optimum.     

An improved genetic algorithm based on a novel selection strategy for nonlinear programming problems

Genetic algorithm is a heuristic population-based search method that incorporates three primary operators: crossover, mutation and selection. Selection operator plays a crucial role in finding optimal solution for constrained optimization problems. In this paper, an improved genetic algorithm (IGA) based on a novel selection strategy is presented to handle nonlinear programming problems. Each individual in selection process is represented as a three-dimensional feature vector composed of objective function value, the degree of constraints violations and the number of constraints violations. We can distinguish excellent individuals through two indices according to Pareto partial order. Additionally, IGA incorporates a local search (LS) process into selection operation so as to find feasible solutions located in neighboring areas of some infeasible solutions. Experimental results over a set of benchmark problems demonstrate that proposed IGA has better robustness, effectiveness and stableness than other algorithm reported in literature.     

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.     

Optimal management of logistic activities in multi-site environments

The new emerging area of Enterprise Wide Optimization (EWO) has focused the attention in effectively solving the combined production/distribution scheduling problem. The importance of logistic activities performed in multi-site environments comes from the relative magnitude of the associated transportation costs and the good chance of getting large savings on such expenses. This paper first develops an exact MILP mathematical formulation for the multiple vehicle time-window-constrained pickup and delivery (MVPDPTW) problem. The approach is able to account for many-to-many transportation requests, pure pickup and delivery tasks, heterogeneous vehicles and multiple depots. Optimal solutions for a variety of benchmark problems with cluster/random distributions of pickup and delivery locations and limited sizes in terms of customer requests and vehicles have been discovered. However, the computational cost exponentially grows with the number of requests. For large-scale m-PDPTW problems, a local search improvement algorithm steadily providing a better solution through two evolutionary steps is also presented. A neighborhood structure around the starting solution is generated by first allowing multiple request exchanges among nearby trips and then permitting the reordering of nodes on every individual route. If a better set of routes is found, both steps are repeated until no improved solution is discovered. Compact MILP mathematical formulations for both sub-problems have been developed and solved through an efficient branch-and-bound algorithm. A significant number of large-scale m-PDPTW benchmark problems, some of them including up to 100 transportation requests, were successfully solved in reasonable CPU times.     

Rule-based scheduling of multi-stage multi-product batch plants with parallel units

A novel rule-based model for multi-stage multi-product scheduling problem (MMSP) in batch plants with parallel units is proposed. The scheduling problem is decomposed into two sub-problems of order assignment and order sequencing. Firstly, hierarchical scheduling strategy is presented for solving the former sub-problem, where the multi-stage multi-product batch process is divided into multiple sequentially connected single process stages, and then the production of orders are arranged in each single stage by using forward order assignment strategy and backward order assignment strategy respectively according to the feature of scheduling objective. Line-up competition algorithm (LCA) is presented to find out optimal order sequence and order assignment rule, which can minimize total flow time or maximize total weighted process time. Computational results show that the proposed approach can obtain better solutions than those of the literature for all scheduling problems with more than 10 orders. Moreover, with the problem size increasing, the solutions obtained by the proposed approach are improved remarkably. The proposed approach has the potential to solve large size MMSP.     

全局优化搜索新算法──列队竞争算法(Ⅱ)解网络综合问题

本文给出了列队竞争算法解组合优化问题的框架和确定变异领域的两条原则 .对管路网络综合问题和换热网络综合问题确定了相应的变异领域 ,用列队竞争算法分别解这两个网络综合问题 ,所得到的最优解优于文献报道的结果 .     

一种求解阻塞型流水车间调度的离散人工蜂群算法(英文)

A discrete artificial bee colony algorithm is proposed for solving the blocking flow shop scheduling problem with total flow time criterion. Firstly, the solution in the algorithm is represented as job permutation. Secondly, an initialization scheme based on a variant of the NEH (Nawaz-Enscore-Ham) heuristic and a local search is designed to construct the initial population with both quality and diversity. Thirdly, based on the idea of iterated greedy algorithm, some newly designed schemes for employed bee, onlooker bee and scout bee are presented. The performance of the proposed algorithm is tested on the well-known Taillard benchmark set, and the computational results demonstrate the effectiveness of the discrete artificial bee colony algorithm. In addition, the best known solutions of the benchmark set are provided for the blocking flow shop scheduling problem with total flow time criterion.