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.     

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.     

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.     

单机多产品注塑过程的节能调度方法

为减小单机多产品注塑过程的生产总能耗,提出一种基于旅行商算法(TSP)和遗传算法(GA)的节能调度方法。研究了注塑生产总能耗的3个重要组成:产品切换能耗、过渡调整能耗和稳定生产能耗,建立了产品切换过渡的能耗模型。以单产平稳模态为节点、过渡模态为支路,建立了单机多产品过程生产总能耗的有向图模型,将单机多产品能耗优化问题转化为经典的TSP问题。采用基于遗传算法的多目标逐层优化与TSP路径寻优思想,搜索各个单产平稳生产下的最优操作参数以及多产品的最优生产顺序,以期降低生产总能耗。该方法可提高生产效率,降低生产能耗。应用研究结果验证了方法的可行性和有效性。     

The heterogeneous vehicle routing and truck scheduling problem in a multi-door cross-dock system

Cross-docking is a logistics technique applied by many industrial firms to get substantial savings in two warehousing costly functions like storage and order picking. Incoming shipments are unloaded from inbound trucks on a cross-dock terminal with minimal storage space and directly transferred to outbound vehicles that carry them to their destinations. The major decisions at the operational level are the vehicle routing and scheduling, the dock door assignment and the truck scheduling at the cross-dock. Because such decisions are interdependent, all of them are simultaneously considered in the so-called vehicle routing problem with cross-docking (VRPCD). Previous contributions on VRPCD assume that pickup and delivery tasks are accomplished by a homogeneous vehicle fleet, and they mostly ignore the internal transportation of goods through the cross-dock. This work introduces a new rigorous mixed-integer linear programming (MILP) formulation for the VRPCD problem to determine the routing and scheduling of a mixed vehicle fleet, the dock door assignment, the truck docking sequence and the travel time required to move the goods to the assigned stack door all at once. To improve the computational efficiency of the branch-and-cut search, an approximate sweep-based model is developed by also considering a set of constraints mimicking the sweep algorithm for allocating nodes to vehicles. Numerous heterogeneous VRPCD examples involving up to 50 transportation requests and a heterogeneous fleet of 10 vehicles with three different capacities were successfully solved using the proposed approaches in acceptable CPU times.     

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.     

Prior detection of genetic algorithm significant parameters: Coupling factorial design technique to genetic algorithm

This work presents an extension of a previous proposed procedure [Costa, C.B.B., Wolf Maciel, M.R., Maciel Filho, R., 2005. Factorial design technique applied to genetic algorithm parameters in a batch cooling crystallization optimization. Computers and Chemical Engineering 29, 2229-2241] to be adopted as a prior analysis in optimization problems to be solved using genetic algorithm (GA). Chemical engineering problems are commonly highly non-linear and possess a large number of variables, sometimes with significant interactions among them. Such characteristics make the optimization problems really difficult to be solved by deterministic methods. GA is an increasing tool for solving this sort of problems. However, no systematic approach to establish the best set of GA parameters for any problem was found in the literature and a relatively easy to use and meaningful approach is proposed and proved to be of general application. The proposed approach consists of applying factorial design, a well-established statistical technique to identify the most meaningful information about the influences of factors on a specific problem, as a support tool to identify the GA parameters with significant effect on the optimization problem. This approach is very useful in conducting further optimization works, since it discharges GA parameters that are not statistically significant for the evolutionary search for the optimum, saving time and computation burden in evolutionary optimization studies.     

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).     

A binary coding genetic algorithm for multi-purpose process scheduling: A case study

This paper presents a novel genetic algorithm (GA) for the scheduling of a typical multi-purpose batch plant with a network structure. Multi-purpose process scheduling is more difficult to deal with compared to single-stage or multi-stage process scheduling. A large amount of literature on this problem has been published and nearly all of the authors used mathematical programming (MP) methods for solution. In the MP methods, a huge number of binary variables, as well as numerous constraints to consider mass balance and sequencing of batches in space/time dimensions, are needed for the large-size problem, which leads to very long computational time. In the proposed GA, only a small part of the binary variables are selected to code into binary chromosomes, which is realized through the identification of crucial products/tasks/units. Due to the logical heuristics utilized to decode a chromosome into a schedule, only the feasible solution space is searched. Our genetic algorithm has first been devised with particular crossover for makespan minimization and then adjusted for production maximization.     

Novel genetic algorithm for short-term scheduling of sequence dependent changeovers in multiproduct polymer plants

Polymer plants generally operate to produce different grades of product from the same reactor. Such systems commonly require short-term scheduling to meet market demand. One important requirement in continuous-time scheduling of such systems is to satisfy a variety of constraints, including identifying feasible sequences of the predecessor and successor jobs to effectively handle changeovers. In this study, a new genetic algorithm (GA) is proposed to solve such job sequencing problems. The proposed GA uses real-coded chromosome to represent job orders and their sequences in the schedule. The novelty is that the representation ensures that all constraints are satisfied a priori, except the sequence constraint which is handled by penalizing violations. Three important problems relevant to polymer industry are solved to obtain optimal schedules. The first deals with the sequencing constraint between individual product orders, the second with sequencing constraint between groups of product orders, while the third incorporates batching with scheduling.     

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 hybrid heuristic for the inventory routing problem under dynamic regional pricing

The inventory routing problem (IRP) seeks to meet the demands of customers during consecutive time periods. Because of the geographical distribution of customers and variations in willingness to pay of the consumers in distinct locations and time, regional and time-based pricing are powerful ways to improve profitability. In this study, a quadratic mixed-integer programming model for single product, multi-period Inventory Routing under the dynamic regional pricing problem (IRDRP) has been proposed. A hybrid heuristic approach is developed to solve it. This algorithm comprises five phases: initialization, demand generation, demand adjustment, inventory routing, and neighborhood search, which are embedded in a simulated annealing framework. Experimental results indicate as the problem size increases, the difference between CPLEX and the proposed heuristic algorithm optimality gap exhibits an upward trend and that the heuristic outperforms CPLEX. A sensitivity analysis demonstrates that by intensifying the scarce capacity, approaching an optimal solution will be more difficult.     

遗传-分布估计算法求解化工生产中一类带多工序的异构并行机调度问题

针对化工生产中广泛存在的一类带多工序的异构并行机调度问题,即部分产品需多工序加工,同时不同产品间带序相关设置时间的异构并行机调度问题（heterogeneous parallel machine scheduling problem with multiple operations and sequence-dependent setup times, HPMSP_MOSST）,提出了一种遗传-分布估计算法（genetic algorithm-estimation of distribution algorithm, GA-EDA）,用于优化最早完工时间（makespan）。首先,提出了一种基于GA的概率模型训练机制,用来提高概率模型在算法进化初期的信息积累量,进而提高搜索的效率;其次,设计了一种有效的GA与EDA混合策略,使得算法的全局探索和局部开发能力得到合理平衡。计算机模拟验证了GA-EDA的有效性和鲁棒性。     

多目标零等待间歇生产过程多任务调度

间歇生产过程已经成为化工生产制造技术的基础和关键,该过程生产出大量产品来满足日常生活需要。然而经济全球化使得传统的化工生产过程产业面临严重的挑战。为了保持竞争力,每个企业必须优化生产技术,加强管理。其中调度是化工企业生产管理的核心技术。针对化工过程自身的多目标和零等待等特性,研究了间歇生产过程中的多目标零等待多任务调度,并提出该问题的模型和优化方法。通过将该问题分解成两个子问题来解决：采用非延迟非秩序混合方法来解决时间表分配问题以及用带存储的完全局部搜索解决排序问题。此外多目标占优采用基于SPEA2中的策略。通过大量算例的仿真实验证明了该算法的可行性和有效性。     

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.     

Efficient multi-product multi-BOM batch scheduling for a petrochemical blending plant with a shared pipeline network

We present an effective scheduling heuristic for realistic production planning in a petrochemical blending plant. The considered model takes into account orders spanning a multi-product portfolio with multiple bills of materials per product, that need to be scheduled on shared production facilities including a complex pipeline network. Capacity constraints, intermediate storage restrictions, due dates, and the dedication of resources to specific product families have to be respected. The primary objective of the heuristic is to minimize the total order tardiness. Secondary objectives include the minimization of pipeline cleaning operations, the minimization of lead times, and the balanced utilization of filling units.The developed algorithm is based on a dynamic prioritization-based greedy search that schedules the orders sequentially. The proposed method can schedule short to mid-term operations and evaluate different plant configurations or production policies on a tactical level. We demonstrate its performance on various real-world inspired scenarios for different scheduling strategies.Our heuristic was used during the construction phase of a new blending plant and was instrumental in the optimal design of the plant.     

一种改进的遗传算法在间歇化工过程设计中的应用

将遗传算法（Genetic Algorithm，GA）和回溯法相结合建立起数学模型对间歇化工过程进行设计，来达到减少设备投资并且提高设备利用率的目的。与一般的启发式方法相比，该模型的搜索范围大，精度高，更适合解决复杂的问题。并且引入自我优化机制和惩罚操作及时修正种群中出现的劣质基因，使种群能够顺利繁衍下去。结果表明，该模型在计算结果、收敛速度和计算速度方面得到了进一步优化。     

改进的生物地理学优化算法在混合流水车间调度中的应用

调度问题是将有限的资源分配给各项不同任务的决策过程,其目的是优化一个或多个目标,它广泛存在于当今大多数的制造和生产系统中。混合流水车间调度问题是一般流水车间调度问题的推广,更接近实际的生产过程。采用一种新型的算法--生物地理学优化算法求解混合流水车间调度问题,通过引入改进策略,增强了算法的全局搜索能力和局部搜索能力,并提高了算法的收敛速度。通过10个标准调度算例的仿真研究,并与遗传算法进行对比,验证了改进后的生物地理学优化算法在求解混合流水车间调度问题方面的优越性。     

一种改进的差分进化算法及其在补料分批式生化反应器动态优化中的应用

动态优化是生物化工过程中的重要课题,求解动态优化问题通常有两种方法:解析法和数值法。基于智能进化算法的数值方法在动态优化中的应用越来越广泛,但是这些方法局部寻优能力不强,容易陷入局部最优,并且求解速度相对较慢。针对这些方法的不足,提出了一种改进的差分进化算法,设计了新的局部寻优算子来增强算法的局部寻优能力,并且采用一种新的控制策略表示方法来求解动态优化问题。通过求解补料分批式生化反应器的动态优化实例,证明了算法的有效性和鲁棒性。通过与其他几种方法进行对比,实验结果表明,所提出的方法在优化结果和计算代价方面都有优势。