带准备时间的单机调度问题的混合进化算法研究

提出了一种混合进化算法（HEA）用于求解具有序列相关依赖且带准备时间的单机调度问题, 其优化目标为最小化总延迟。该混合进化算法由局部搜索和进化算法框架混合而成。HEA具有一些新的特点, 例如在局部搜索中采用了一种新提出的基于块移动的邻域结构, 这种邻域结构合理地限制了搜索空间, 提高了算法的搜索效率; 在HEA中采用了一种新的组合算子——块顺序交叉算符（BOX）来产生新的子代工作序列。用本算法对当前国际文献中公开的两组共64个算例进行了测试, HEA改进了9个算例在当前文献中的最优解, 表明了所提出的HEA算法的优越性。与之前的国际文献中最好的四个启发式算法进行了详细比较, 表明了HEA算法的优势。     

面向多目标流水车间调度的多种群多目标遗传算法

针对制造型企业普遍存在的流水车间调度问题,建立了以最小化最迟完成时间和总延迟时间为目标的多目标调度模型,并提出一种基于分解方法的多种群多目标遗传算法进行求解.该算法将多目标流水车间调度问题分解为多个单目标子问题,并分阶段地将这些子问题引入到算法迭代过程进行求解.算法在每次迭代时,依据种群的分布情况选择各子问题的最好解及与其相似的个体分别为当前求解的子问题构造子种群,通过多种群的进化完成对多个子问题最优解的并行搜索.通过对标准测试算例进行仿真实验,结果表明所提出的算法在求解该问题上能够获得较好的非支配解集.     

面向柔性工艺的作业车间调度问题混合遗传算法

针对离散制造业的许多产品采用柔性工艺设计增加作业计划调度的复杂性这一问题,对传统的FJSP进行了工序顺序柔性的扩展,将问题抽象为柔性工艺的作业车间调度问题（flexible process Job-Shop scheduling problem,FPJSP）。以缩短生产周期为目标,建立了该问题的整数规划模型,并设计了混合遗传算法。该算法针对FPJSP的特点设计了改进的遗传算法染色体编码方式和遗传算子,并结合变邻域搜索算法,设计了适合求解该问题的四种不同的邻域结构进行动态邻域搜索,以提高遗传算法的邻域搜索性能。通过应用实例验证了所提出的混合遗传算法在求解FPJSP的求解效率和优化性能方面的有效性。     

A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning

A considerable growth in worldwide container transportation needs essential optimization of terminal operations. An operation schedule for berth and quay cranes can significantly affect turnaround time of ships, which is an important objective of all schedules in a port. This paper addresses the problem of determining the berthing position and time of each ship as well as the number of quay cranes assigned to each ship. The objective of the problem is to minimize the sum of the handling time, waiting time and the delay time for every ship. We introduce a formulation for the simultaneous berth and quay crane scheduling problem. Next, we combine genetic algorithm with heuristic to find an approximate solution for the problem. Computational experiments show that the proposed approaches are applicable to solve this difficult but essential terminal operation problem.     

A block-based evolutionary algorithm for flow-shop scheduling problem

Combinatorial problems like flow shop scheduling, travel salesman problem etc. get complicated and are difficult to solve when the problem size increases. To overcome this problem, we present a block-based evolutionary algorithm (BBEA) which will conduct evolutionary operations on a set of blocks instead of genes. BBEA includes the block mining and block recombination approaches. A block mining algorithm is developed to decompose a chromosome into a set of blocks and rest of genes. The block is with a fixed length and can be treated as a building block in forming a new chromosome later on. To guide the block mining process, a gene linkage probability matrix is defined that shows the linkage strength among genes. Therefore the blocks can be further evolved during the evolutionary processes using this matrix. In the block recombination approach, the blocks along with the rest of genes are recombined to form a new chromosome. This new evolutionary approach of BBEA is tested on a set of discrete problems. Experimental results show that BBEA is very competitive when compared with traditional GA, EA or ACGA and HGIA approaches and it can largely improve the performance of evolutionary algorithm and save a fair amount of computational times simultaneously.     

Switching strategy-based hybrid evolutionary algorithms for job shop scheduling problems

Journal of Intelligent Manufacturing - Since production efficiency and costs are directly affected by the ways in which jobs are scheduled, scholars have advanced a number of meta-heuristic...     

柔性作业调度的串并行模型对比与求解

作业处理中的柔性使得作业调度更为灵活,作业中操作的执行顺序满足拓扑排序是作业调度的前提。是否允许没有优先关系的操作在不同的机器上同时执行是区分串行和并行调度的条件。文中以共生进化算法求解一个复杂的作业调度模型为例,给出了算法实现串行调度和并行调度的具体区别,并给出了串行和并行调度的结果。结果表明,并行相对于串行对算法效率的提高与柔性大小相关,与作业的规模成反比。     

Enhanced evolutionary algorithms for single and multiobjective optimization in the job shop scheduling problem

Over the past few years, a continually increasing number of research efforts have investigated the application of evolutionary computation techniques for the solution of scheduling problems. Scheduling can pose extremely complex combinatorial optimization problems, which belong to the NP-hard family. Last enhancements on evolutionary algorithms include new multirecombinative approaches. Multiple Crossovers Per Couple (MCPC) allows multiple crossovers on the couple selected for mating and Multiple Crossovers on Multiple Parents (MCMP) do this but on a set of more than two parents. Techniques for preventing incest also help to avoid premature convergence. Issues on representation and operators influence efficiency and efficacy of the algorithm. The present paper shows how enhanced evolutionary approaches, can solve the Job Shop Scheduling Problem (JSSP) in single and multiobjective optimization.     

混合哈里斯鹰算法求解作业车间调度问题

针对哈里斯鹰算法（HHO）求解作业车间调度问题（JSP）时存在寻优能力差、易陷入局部最优等缺点提出了混合哈里斯鹰算法（HHHO）。首先,在种群初始化阶段引入混沌理论增加种群多样性;其次,在HHO搜索前期采用能量非线性递减和量子计算增强算法全局探索能力,在搜索后期采用邻域搜索算法增强算法局部开发能力;最后,选取了FT和LA系列算例测试了算法的性能,并与其他先进元启发式算法对比,验证了HHHO在求解JSP时的有效性和优越性。     

求解车间作业调度问题的混合遗传算法

针对Job-Shop调度问题,将自适应遗传算法与改进的蚂蚁算法融合,提出了自适应遗传算法与蚂蚁算法混合的一种优化算法。首先利用自适应遗传算法产生初始信息素的分布,再运行改进的蚂蚁算法进行求解。该算法既发挥了自适应遗传算法和蚂蚁算法在寻优中的优势,又克服了各自的不足。实验结果表明,该算法在性能上明显优于遗传算法和蚂蚁算法,并且问题规模越大,优势越明显。     

Improved genetic algorithm based on multi-layer encoding approach for integrated process planning and scheduling problem

Integrated process planning and scheduling (IPPS) is of great significance for modern manufacturing enterprises to achieve high efficiency in manufacturing and maximize resource utilization. In this paper, the integration strategy and solution method of IPPS problem are deeply studied, and an improved genetic algorithm based on multi-layer encoding (IGA-ML) is proposed to solve the IPPS problem. Firstly, considering the interaction ability between the two subsystems and the multi-flexibility characteristics of the IPPS problem, a new multi-layer integrated encoding method is designed. The encoding method includes feature layer, operation layer, machine layer and scheduling layer, which respectively correspond to the four sub-problems of IPPS problem, which provides a premise for a more flexible and deeper exploration in the solution space. Then, based on the coupling characteristics of process planning and shop scheduling, six evolutionary operators are designed to change the four-layer coding interdependently and independently. Two crossover operators change the population coding in the unit of jobs, and search the solution space globally. The four mutation operators change the population coding in the unit of gene and search the solution space locally. The six operators are used in series and iteratively optimized to ensure a fine balance between the global exploration ability and the local exploitation ability of the algorithm. Finally, performance of IGA-ML is verified by testing on 44 examples of 14 benchmarks. The experimental results show that the proposed algorithm can find better solutions (better than the optimal solutions found so far) on some problems, and it is an effective method to solve the IPPS problem with the maximum completion time as the optimization goal.     

A hybrid evolutionary algorithm for the resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) is an NP-hard optimization problem. RCPSP is one of the most important and challenging problems in the project management field. In the past few years, many researches have been proposed for solving the RCPSP. The objective of this problem is to schedule the activities under limited resources so that the project makespan is minimized. This paper proposes a new algorithm for solving RCPSP that combines the concepts of negative selection mechanism of the biologic immune system, simulated annealing algorithm (SA), tabu search algorithm (TS) and genetic algorithm (GA) together. The performance of the proposed algorithm is evaluated and compared to current state-of-the-art metaheuristic algorithms. In this study, the benchmark data sets used in testing the performance of the proposed algorithm are obtained from the project scheduling problem library. The performance is measured in terms of the average percentage deviation from the critical path lower bound. The experimental results show that the proposed algorithm outperforms the state-of-the-art metaheuristic algorithms on all standard benchmark data sets.     

A rock-paper-scissors evolutionary algorithm for the TDMA broadcast scheduling problem

In wireless ad-hoc networks, the broadcast scheduling problem (BSP) is commonly viewed as a well-known NP-complete combinatorial optimization problem. The purpose of the BSP is to achieve a transmission schedule with collision-free time slots in a time division multiple access ad-hoc network. The transmission schedule is optimized by minimizing the frame length of the node transmissions and maximizing the utilization of the shared channel. In this work, we propose a new evolutionary algorithm to solve the BSP by adopting the rock-paper-scissors dynamics found in natural systems. We use three types of species with strategies of different levels of intensification and diversification to simulate the rock-paper-scissors dynamics. Based on this evolutionary game, in which the success of one species relies on the behavior of others, the dynamic coexistence of three species can be achieved to control the balance between intensification and diversification. The experimental results demonstrate that our algorithm is efficient and effective at solving large instances of the BSP.     

流水车间调度问题的快速多目标混合进化算法

针对最大完工时间最小和总流经时间最小的双目标流水车间调度问题,提出一种快速多目标混合进化算法。算法将矢量评价遗传算法的采样策略与一种新的基于Pareto支配与被支配关系的适应度函数的采样策略进行了融合。新的采样策略弥补了矢量评价遗传算法(VEGA)采样策略的不足。VEGA善于搜索Pareto前沿面的边缘区域,但却忽略了Pareto前沿面的中心区域,而新的采样策略则倾向于Pareto前沿面的中心区域。这两种机制的融合保证了混合算法能够快速平稳地向Pareto前沿区域收敛。此外,由于混合采样策略不需要考虑距离,使得算法效率也得到了很大的提升。在对Taillard基准测试集进行的仿真实验结果显示,相对于非支配排序遗传算法(NSGA-Ⅱ)和强度Pareto进化算法(SPEA2),该快速多目标混合进化算法在收敛性和分布性两方面都有所提高,并且算法的效率也得到了改进。所提出的混合算法能够更好地解决双目标的流水车间调度问题。     

求解作业车间调度问题的混合帝国主义竞争算法

针对最小化最大完工时间的作业车间调度问题（JSP）,提出一种结合帝国主义竞争算法（ICA）和禁忌搜索（TS）算法的混合算法。混合算法以帝国主义竞争算法为基础,在同化操作中融入遗传算法中的杂交算子和变异算子,使算法全局搜索能力更强。为了克服帝国主义竞争算法局部搜索能力弱的缺点,引入禁忌搜索算法进一步优化同化操作后的后代。禁忌搜索算法采用混合邻域结构和新型选择策略,使得算法能够更有效地搜索邻域解。混合算法兼具全局搜索能力和局部搜索能力,通过对13个经典的Benchmark调度问题进行仿真测试,并与近年4种新型混合算法进行对比分析,实验结果表明了所提算法求解Job Shop调度问题的有效性和稳定性。     

Mathematical modeling and evolutionary algorithm-based approach for integrated process planning and scheduling

Traditionally, process planning and scheduling were performed sequentially, where scheduling was implemented after process plans had been generated. Considering their complementarity, it is necessary to integrate these two functions more tightly to improve the performance of a manufacturing system greatly. In this paper, a mathematical model of integrated process planning and scheduling has been formulated. And, an evolutionary algorithm-based approach has been developed to facilitate the integration and optimization of these two functions. To improve the optimized performance of the approach, efficient genetic representation and operator schemes have been developed. To verify the feasibility and performance of the proposed approach, experimental studies have been conducted and comparisons have been made between this approach and some previous works. The experimental results show that the integrated process planning and scheduling is necessary and the proposed approach has achieved significant improvement.     

A Kriging-assisted multiobjective evolutionary algorithm

A surrogate-assisted (SA) evolutionary algorithm for Multiobjective Optimization Problems (MOOPs) is presented as a contribution to Soft Computing (SC) in Artificial Intelligence (AI). Such algorithm is grounded on the cooperation between a “pure” evolutionary algorithm and a Kriging based algorithm featuring the Expected Hyper-Volume Improvement (EHVI) metric. Comparison with state-of-art pure and Kriging-assisted algorithms over two- and three-objective test functions have demonstrated that the proposed algorithm can achieve high performance in the approximation of the Pareto-optimal front mitigating the drawbacks of its parent algorithms.     

Hierarchical multistrategy genetic algorithm for integrated process planning and scheduling

Journal of Intelligent Manufacturing - To adapt to the flexibility characteristics of modern manufacturing enterprises and the dynamics of manufacturing subsystems, promote collaboration in...     

A knowledge-based evolutionary algorithm for the multiobjective vehicle routing problem with time windows

This paper addresses the multiobjective vehicle routing problem with time windows (MOVRPTW). The objectives are to minimize the number of vehicles and the total distance simultaneously. Our approach is based on an evolutionary algorithm and aims to find the set of Pareto optimal solutions. We incorporate problem-specific knowledge into the genetic operators. The crossover operator exchanges one of the best routes, which has the shortest average distance, the relocation mutation operator relocates a large number of customers in non-decreasing order of the length of the time window, and the split mutation operator breaks the longest-distance link in the routes. Our algorithm is compared with 10 existing algorithms by standard 100-customer and 200-customer problem instances. It shows competitive performance and updates more than 1/3 of the net set of the non-dominated solutions.