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.     

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.     

On the solution of scheduling problems for multi-purpose batch chemical plants

A solution strategy for solving the scheduling problem in the case of multi-purpose batch chemical plants is described. The plant may contain several identical examples of any of the types of process unit. The problem is characterized by requirements such as —branching in batch and device —maintenance of a fixed time regime in the production of one batch —changeover times when products are changed, etc. The centre of the heuristic strategy of solution is an exact algorithm which examines whether or not a batch with a given starting time can be scheduled. The appropriate subprogram can be easily incorporated into programs realizing known heuristic scheduling principles, which were developed for solving simpler problems. Examples with 68 process units, 600 shits and 350 batches have been computed on a EC 1040 computer in 10–15 minutes.     

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.     

A simpler better slot-based continuous-time formulation for short-term scheduling in multipurpose batch plants

Short-term scheduling of multipurpose batch plants is a challenging problem for which several formulations exist in the literature. In this paper, we present a new, simpler, more efficient, and potentially tighter, mixed integer linear programming (MILP) formulation using a continuous-time representation with synchronous slots and a novel idea of several balances (time, mass, resource, etc.). The model uses no big-M constraints, and is equally effective for both maximizing profit and minimizing makespan. Using extensive, rigorous numerical evaluations on a variety of test problems, we show that in contrast to the best model in the literature, our model does not decouple tasks and units, but still has fewer binary variables, constraints, and nonzeros, and is faster.     

Molecular Sticker Model Stimulation on Silicon for a Maximum Clique Problem

Molecular computers (also called DNA computers), as an alternative to traditional electronic computers, are smaller in size but more energy efficient, and have massive parallel processing capacity. However, DNA computers may not outperform electronic computers owing to their higher error rates and some limitations of the biological laboratory. The stickers model, as a typical DNA-based computer, is computationally complete and universal, and can be viewed as a bit-vertically operating machine. This makes it attractive for silicon implementation. Inspired by the information processing method on the stickers computer, we propose a novel parallel computing model called DEM (DNA Electronic Computing Model) on System-on-a-Programmable-Chip (SOPC) architecture. Except for the significant difference in the computing medium—transistor chips rather than bio-molecules—the DEM works similarly to DNA computers in immense parallel information processing. Additionally, a plasma display panel (PDP) is used to show the change of solutions, and helps us directly see the distribution of assignments. The feasibility of the DEM is tested by applying it to compute a maximum clique problem (MCP) with eight vertices. Owing to the limited computing sources on SOPC architecture, the DEM could solve moderate-size problems in polynomial time.     

Optimal scheduling and minimum storage tank capacities in a process system with parallel batch units

It is first presumed that a chemical process system is operated continuously as a whole, but some part of the system is composed of a parallel batch section and intermediate storage tanks. The problem of determining the scheduling of the parallel batch operations and the tank capacities is discussed here. For the case where a batch section is composed of parallel identical units, optimal scheduling is obtained analytically. Then the case in which each batch section has different operation times is dealt with. For this case, it is shown that the search domain necessary can be reduced to an extremely small size.     

A novel constraint programming model for large-scale scheduling problems in multiproduct multistage batch plants: Limited resources and campaign-based operation

This contribution introduces an efficient constraint programming (CP) model that copes with large-scale scheduling problems in multiproduct multistage batch plants. It addresses several features found in industrial environments, such as topology constraints, forbidden product-equipment assignments, sequence-dependent changeover tasks, dissimilar parallel units at each stage, limiting renewable resources and multiple-batch orders, among other relevant plant characteristics. Moreover, the contribution deals with various inter-stage storage and operational policies. In addition, multiple-batch orders can be handled by defining a campaign operating mode, and lower and upper bounds on the number of batches per campaign can be fixed. The proposed model has been extensively tested by means of several case studies having various problem sizes and characteristics. The results have shown that the model can efficiently solve medium and large-scale problems with multiple constraining features. The approach has also rendered good quality solutions for problems that consider multiple-batch orders under a campaign-based operational policy.     

Multidimensional non-orthogonal wavelet-sigmoid basis function neural network for dynamic process fault diagnosis

Dealing with multidimensional problems has been the “bottle-neck” for implementing wavenets to process systems engineering. To tackle this problem, a novel multidimensional wavelet (MW) is presented with its rigorously proven approximation theorems. Taking the new wavelet function as the activation function in its hidden units, a new type of wavenet called multidimensional non-orthogonal non-product wavelet-sigmoid basis function neural network (WSBFN) model is proposed for dynamic fault diagnosis. Based on the heuristic learning rules presented by authors, a new set of heuristic learning rules is presented for determining the topology of WSBFNs. The application of the proposed WSBFN is illustrated in detail with a dynamic hydrocracking process.     

Multiobjective optimization of multipurpose batch plants using superequipment class concept

We present a novel approach for solving different design problems related to single products in multipurpose batch plants: the selection of one production line out of several available, additional investment into an existing line or plant, and grass-root design of a new plant. Multiple objectives are considered in these design problems. Pareto-optimal solutions are generated by means of a Tabu Search algorithm. In the novel approach the concept of superequipment has been defined as an abstract equipment model, which is capable of performing any physico-chemical batch operation. Each superequipment is transformed into a real equipment unit, for example a reactor, during or after the optimization in order to evaluate performance parameters of a design. This novel concept uses an implicit definition of a superstructure and essentially optimizes on the transfers between different equipment units in a design.On the basis of case studies we demonstrate that the application of the superequipment concept offers a number of advantages for the investigated design problems. For example, in the evaluation of investment into single equipment pieces to be added to existing plants or production lines only the maximum number of additional equipment, each represented as a superequipment, has to be specified instead of a list consisting of a higher number of explicit units. Similar advantages arise for grass-root design problems or for the selection of a production line or plant out of several that are available for the production of a specified chemical.The comparison with optimization results obtained with a conventional Tabu Search algorithm revealed that the superequipment approach is capable of identifying the Pareto-optimal solutions in significantly reduced computation time.     

Interior-point decomposition approaches for parallel solution of large-scale nonlinear parameter estimation problems

Multi-scenario optimization is a convenient way to formulate and solve multi-set parameter estimation problems that arise from errors-in-variables-measured (EVM) formulations. These large-scale problems lead to nonlinear programs (NLPs) with specialized structure that can be exploited by the NLP solver in order to obtained more efficient solutions. Here we adapt the IPOPT barrier nonlinear programming algorithm to provide efficient parallel solution of multi-scenario problems. The recently developed object oriented framework, IPOPT 3.2, has been specifically designed to allow specialized linear algebra in order to exploit problem specific structure. This study discusses high-level design principles of IPOPT 3.2 and develops a parallel Schur complement decomposition approach for large-scale multi-scenario optimization problems. A large-scale case study example for the identification of an industrial low-density polyethylene (LDPE) reactor model is presented. The effectiveness of the approach is demonstrated through the solution of parameter estimation problems with over 4100 ordinary differential equations, 16,000 algebraic equations and 2100 degrees of freedom in a distributed cluster.     

Financial and financial engineering considerations in supply chain and product development pipeline management

Enterprise-wide decision problems are receiving increasing attention in the process systems engineering literature. In particular, the supply chain and product development pipeline management components of this general class of problems have been subjects of intensive research in both their deterministic and their stochastic forms. The supply chain management (SCM) problem has seen work largely focused on the process operations and logistics components while for the product development pipeline management (PDPM) problem much of the attention has been on MILP formulations addressing the consequences of product failure during its development. In their full realization, both are recognized as challenging stochastic multi-stage decision problems. In this paper we discuss three important aspects of these problems that require further research: the realistic representation of the financial components and appropriate criteria for this class of problems, strategic management of supplier and customer relationships through inventory management and option contracts, and innovative approaches to suitably value and integrate a broader range of decisions available to management. We highlight and extend relevant contributions and case examples drawn from the recent literature that are emerging on these topics and use this work to point out further challenges.     

Design of robust,reliable sensor networks using constraint programming

Various criteria have been considered in the literature for selection of optimal sensor networks. Amongst these, maximization of network reliability is an important criterion. While there are several approaches for designing maximum reliability networks, uncertainty in the available sensor reliability data has not been considered in these designs. In this article we present two novel formulations that incorporate robustness to uncertainties in the reliability data. Towards this end the sensor network design problem for maximizing reliability is formulated as explicit-optimization (MINLP) problem using failure rates of sensors which have better scaling properties instead of sensor reliabilities. Constraint programming (CP) has been used for solving the resulting optimization problems. Use of CP also enables easy generation of pareto front characterizing trade-offs between performance, cost and robustness for various uncertainty scenarios. The utility of the proposed approach is demonstrated on a case study taken from the literature.     

Optimal scheduling of continuous plants with energy constraints

This work addresses the scheduling of continuous single stage multiproduct plants with parallel units and shared storage tanks. Processing tasks are energy intensive and we consider time-dependent electricity pricing and availability together with multiple intermediate due dates, handled as hard constraints. A new discrete-time aggregate formulation is proposed to rapidly plan the production levels. It is combined with a continuous-time model for detailed scheduling as the essential part of a rolling-horizon algorithm. Their computational performance is compared to traditional discrete and continuous-time full-space formulations with all models relying on the Resource-Task Network (RTN) process representation. The results show that the new models and algorithm can generate global optimal schedules much more efficiently than their counterparts in problems involving unlimited power availability. Under restricted power, the aggregate model underestimates the electricity cost, which may cause the rolling-horizon approach to converge to a suboptimal solution, becoming the discrete-time model a better approach.     

Planning production on a single processor with sequence-dependent setups part 1: determination of campaigns

Production planning of processors located within in a facility or distributed across facilities is a routine and crucial industrial activity. So far, most attempts at this have treated planning horizon as a decision variable, and have limited their scope to sequence-independent setups. In this two-part paper, we present a new and improved methodology for solving the single machine economic lot scheduling problem (ELSP) with sequence-dependent setups and a given planning horizon. We decompose the entire complex problem into two subproblems; one involving lot sizing and the other involving lot sequencing and scheduling. In this part, we present a novel mixed integer nonlinear programming (MINLP) formulation for the lot-sizing problem. Using a multi-segment separable programming approach, we transform this MINLP into a MILP and propose one rigorous and two heuristic algorithms for the latter. Based on a thorough numerical evaluation using randomly simulated large problems, we find that our best heuristic gives solutions within 0.01% of the optimal on an average and in much less time than the optimal algorithm. Furthermore, it works equally well on problems with sequence-independent setups. Overall, our methodology is well suited for real-life large-scale industrial problems.     

Synthesis and sizing of batch/semicontinuous processes: single product plants

An approach is reported for the preliminary design of single product batch/semicontinuous plants. The methodology consists of two components: a new approximate sizing procedure, which determines the number of units in parallel at each stage as well as the sizes of the batch and semicontinuous units and a set of synthesis rules, which serve to select structural features such as consecutive tasks that should be merged or split and tasks that should be separated by intermediate storage. The sizing procedure can accommodate both new plant design as well as some simple forms of retrofitting applications. The effectiveness of the approach is demonstrated with comparisons to designs obtained using nonlinear programming formulations solved by using a generalized reduced-gradient algorithm.     

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 pattern matching method for large‐scale multipurpose process scheduling

This article proposes a novel pattern matching method for the large‐scale multipurpose process scheduling with variable or constant processing times. For the commonly used mathematical programming models, large‐scale scheduling with long‐time horizons implies a large number of binary variables and time sequence constraints, which makes the models intractable. Hence, decomposition and cyclic scheduling are often applied to such scheduling. In this work, a long‐time horizon of scheduling is divided into two phases. Phase one is duplicated from a pattern schedule constructed according to the principle that crucial units work continuously, in parallel and/or with full load as possible, exclusive of time‐consuming optimization. Phase two involves a small‐size subproblem that can be optimized easily by a heuristic method. The computational effort of the proposed method does not increase with the problem size. The pattern schedule can be not only used for production/profit maximization but also for makespan estimation and minimization. © 2010 American Institute of Chemical Engineers AIChE J, 2011     

A hybrid optimization strategy for simultaneous synthesis of heat exchanger network

The heat exchanger network synthesis problem often leads to large-scale non-convex mixed integer nonlinear programming formulations that contain many discrete and continuous variables, as well as nonlinear objective function or nonlinear constraints. In this paper, a novel method consisting of genetic algorithm and particle swarm optimization algorithm is proposed for simultaneous synthesis problem of heat exchanger networks. The simultaneous synthesis problem is solved in the following two levels: in the upper level, the network structures are generated randomly and reproduced using genetic algorithm; and in the lower level, heat load of units and stream-split heat flows are optimized through particle swarm optimization algorithm. The proposed approach is tested on four benchmark problems, and the obtained solutions are compared with those published in previous literature. The results of this study prove that the presented method is effective in obtaining the approximate optimal network with minimum total annual cost as performance index.