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.     

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.     

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.     

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.     

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.     

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

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

Scheduling multistage, multiproduct batch plants with nonidentical parallel units and unlimited intermediate storage

Scheduling production optimally in multistage multiproduct plants with nonidentical parallel units is a very difficult but routine problem that has received limited attention. In this paper, we construct, analyze, and rigorously compare a variety of novel mixed-integer linear programming formulations using unit-slots, stage-slots, process-slots, a variety of slot arrangements and sequence-modeling techniques, 4-index and 3-index binary variables, etc. While two of our 4-index models are an order of magnitude faster than existing models on 22 test problems of varying sizes, we find that no single model performs consistently the best for all problems. Our work suggests that the best strategy for solving difficult scheduling problems may be to use a set of competitive models in parallel and terminate them all, when one of them achieves the desired solution. We also develop several heuristic models based on our formulations and find that even a heuristic based on an inferior model can surpass others based on superior models. Thus, it may not always be wise to just aim for a single best model for a given scheduling problem, but a host of novel and competitive models, as we have done in this paper.     

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.     

Global optimization of non-convex nonlinear programs using Line-up Competition Algorithm

A global optimization algorithm of simulating evolutionary process, called Line-up Competition Algorithm (LCA), was recently proposed. In the LCA, all families are independent and parallel during evolution. According to the value of their objective function, all families are ranked a line-up and are allocated different search spaces based on their positions in the line-up. The preceding excellent families in the line-up gain less search space, which is favorable for local search, accelerating to find optimal point, while the latter worse families gain larger search space, which is helpful for global search. Through the competition of two levels of inside a family and between families, the first family in the line-up is continually replaced by other families, or the value of objective function of the first family is updated continually. As a result, the optimal solution is approached rapidly. In this paper, the superior performances of the LCA were demonstrated in detail by solving some difficult non-convex nonlinear programming problems constrained and unconstrained.     

Genetic algorithm for short-term scheduling of make-and-pack batch production process

This paper considers a scheduling problem in industrial make-and-pack batch production process. This process equips with sequence-dependent changeover time, multipurpose storage units with limited capacity, storage time, batch splitting, partial equipment connectivity and transfer time. The objective is to make a production plan to satisfy al constraints while meeting demand requirement of packed products from various product fam-ilies. This problem is NP-hard and the problem size is exponentially large for a realistic-sized problem. Therefore, we propose a genetic algorithm to handle this problem. Solutions to the problems are represented by chromo-somes of product family sequences. These sequences are decoded to assign the resource for producing packed products according to forward assignment strategy and resource selection rules. These techniques greatly reduce unnecessary search space and improve search speed. In addition, design of experiment is carefully utilized to de-termine appropriate parameter settings. Ant colony optimization and Tabu search are also implemented for com-parison. At the end of each heuristics, local search is applied for the packed product sequence to improve makespan. In an experimental analysis, al heuristics show the capability to solve large instances within reason-able computational time. In al problem instances, genetic algorithm averagely outperforms ant colony optimiza-tion and Tabu search with slightly longer computational time.     

Simultaneous subtour elimination model for single-stage multiproduct parallel batch scheduling with sequence dependent changeovers

In this paper a mixed-integer linear programming (MILP) model is presented to minimize makespan of single-stage multiproduct parallel batch production with sequence dependent changeovers. The computational inefficiency and suboptimal problems are addressed by the tight and rigorous formulation of the proposed model. Subtours (subcycles) are eliminated simultaneously so that the optimal solution is obtained in one step. The proposed model is tested with two examples. The results show that the model obtains the global optimal solutions with significant improvement in solution time.     

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.     

Optimal scheduling of single stage batch plants with direct heat integration

This paper addresses the multi-objective optimization problem arising in the operation of heat integrated batch plants, where makespan and utility consumption are the two conflicting objectives. A new continuous-time MILP formulation with general precedence variables is proposed to simultaneously handle decisions related to timing, product sequencing, heat exchanger matches (selected from a two-stage superstructure) and their heat loads. It features a complex set of timing constraints to synchronize heating and cooling tasks, derived from Generalized Disjunctive Programming. Through the solution of an industrial case study from a vegetable oil refinery, we show that major savings in utilities can be achieved while generating the set of Pareto optimal solutions through the ɛ-constraint method.     

Greedy algorithm for scheduling batch plants with sequence‐dependent changeovers

This article presents a new algorithm for scheduling multistage batch plants with a large number of orders and sequence‐dependent changeovers. Such problems are either intractable when solved with full‐space approaches or poor solutions result. We use decomposition on the entire set of orders and derive the complete schedule in several iterations, by inserting a couple of orders at a time. The key idea is to allow for partial rescheduling without altering the main decisions in terms of unit assignments and sequencing (linked to the binary variables) so that the combinatorial complexity is kept at a manageable level. The algorithm has been implemented for three alternative continuous‐time mixed integer linear programing models and tested through the solution of 10 example problems for different decomposition settings. The results show that an industrial‐size scheduling problem with 50 orders, 17 units distributed over six stages can effectively be solved in roughly 6 min of computational time. © 2010 American Institute of Chemical Engineers AIChE J, 2011     

Heat integration of intermittently available continuous streams in multipurpose batch plants

Presented in this paper is a mathematical technique for simultaneous heat integration and process scheduling in multipurpose batch plants. Taking advantage of the intermittent continuous behavior of process streams during transfer from one processing unit to another, as determined by the recipe, the presented formulation aims to maximize the coincidence of availability of hot and cold stream pairs with feasible temperature driving forces, while taking into consideration process scheduling constraints. Contrary to similar contributions in published literature, time is treated as one of the key optimization variables instead of a parameter fixed a priori. Heat integration during stream transfer has the added benefit of shortened processing time, which invariably improves throughput, as more batches are likely to be processed within a given time horizon, compared to conventional heating and cooling in situ. Application of the proposed model to a case study shows improvements of more than 30% in energy savings and up to 15% in product output.     

基于特定单元事件点的改进间歇生产调度模型

建立有效的间歇调度模型一直是生产调度问题调度研究的热点,而连续时间模型是优化短期间歇生产调度问题的有效工具。基于特定单元事件点的概念,建立一种改进的间歇调度连续时间混合整数线性规划(MILP)模型。该调度模型引入了新变量,使模型处理物料在不同设备间的传输过程更加灵活。结果表明,提出的改进模型只需要较少的事件点,就可以快速有效处理无限中间存储(UIS)间歇调度问题。     

不确定条件下中间存储时间有限多产品间歇生产过程调度

针对产品处理时间不确定条件下中间存储时间有限多产品间歇生产过程调度问题, 采用三角模糊数描述处理时间的不确定性, 通过一种模糊排序的方法建立了以最小化模糊最大完工时间的值以及不确定度作为调度目标的数学模型, 提出一种基于改进粒子群和分布估计的混合算法(IPSO-EDA)。IPSO-EDA算法在粒子群更新公式中引入基于所有粒子自身最优位置的优质个体分布信息, 提高了算法的全局搜索能力, 同时采用NEH初始化获得理想的初始解, 采用NEH局部搜索提高算法的局部搜索能力。通过正交实验设计对算法的参数进行调节, 仿真结果表明了所提出算法的有效性和优越性。     

Multiobjective optimization of multiproduct batch plants scheduling under environmental and economic concerns

In batch process scheduling, production trade‐offs arise from the simultaneous consideration of different objectives. Economic goals are expressed in terms of plant profitability and productivity, whereas the environmental objectives are evaluated by means of metrics originated from the use of life cycle assessment methodology. This work illustrates a novel approach for decision making by using multiobjective optimization. In addition, different metrics are proposed to select a possible compromise based on the distance to a nonexistent utopian solution, whose objective function values are all optimal. Thus, this work provides a deeper insight into the influence of the metrics selection for both environmental and economic issues while considering the trade‐offs of adopting a particular schedule. The use of this approach is illustrated through its application to a case study related to a multiproduct acrylic fiber production plant, special attention is put to the influence of product changeovers. © 2010 American Institute of Chemical Engineers AIChE J, 57: 2766–2782, 2010     

Solving mixed integer nonlinear programming problems with line-up competition algorithm

Line-up competition algorithm (LCA), a global optimization algorithm proposed recently, is applied to the solution of mixed integer nonlinear programming (MINLP) problems. Through using alternative schemes to handle integer variables, the algorithm reported previously for solving NLP problems can be extended expediently to the solution of MINLP problems. The performance of the LCA is tested with several non-convex MINLP problems published in the literature, including the optimal design of multi-product batch chemical processes and the location-allocation problem. Testing shows that the LCA algorithm is efficient and robust in the solution of MINLP problems.     

Optimal design of batch mass exchange networks with multipurpose exchange units

A novel mathematical model for simultaneous optimization of batch mass exchange networks with multipurpose mass exchange units that can be shared by more than one match in different periods is presented in this work. It can be shown that both utility cost and capital investment can be reduced simultaneously with the use of multipurpose mass exchangers and mass storage tanks. Specifically, state-space superstructure that does not contain any structural simplification is proposed to capture the entire characteristics of the network configuration and a mixed-integer nonlinear optimization model is then formulated accordingly to generate the optimal batch operating policies and the corresponding flowsheet. Two examples are presented in this paper to demonstrate the validity and advantages of the proposed approach.