应用模拟植物生长算法求解置换流水车间调度问题*

针对置换流水车间调度问题,提出了一种基于模拟植物生长的调度算法。该算法利用置换流水车间调度的有向图表示,提出了可交换节点集概念,并将其融入模拟植物生长算法中,解决置换流水车间调度问题。采用所提算法对置换流水车间调度问题的基准数据进行测试,并比对标准遗传算法,结果表明算法的有效性。     

置换流水车间调度的蚁群优化算法

提出了一种求解置换流水车间调度的蚁群优化算法。该算法的要点是结合了NEH启发式算法和蚁群优化方法。理论论证和对置换流水车间调度问题的基准测试表明了该算法的有效性。     

PFSP 问题的混和CHIO算法优化

在冠状病毒群体免疫优化算法基础上进行了改进形成了一种求解置换流水车间调度问题的混合算法. 在群体免疫进化阶段使用了动态改变扩展速率的策略平衡了算法探索能力与开发能力, 在重生阶段后增加基于差分进化的交叉阶段以增强最优解的挖掘能力; 采用基于最小位置值的方式实现置换流水车间调度问题解的编码与解码. 以最小化最大完工时间为求解目标, 在21个Reeves测试实例上进行了实验, 实验结果表明了提出算法在求解置换流水车间调度问题上的有效性.     

有限等待置换流水车间调度问题的IGA算法

在对经典遗传算法进行研究的基础上,针对具有等待时间置换流水车间调度问题,以最小化最大完成时间为优化目标建立整数规划模型,并提出一种解决该问题的IGA算法;算法中部分染色体的初始种群由原问题所转化而成的具有等待时间两台机器的置换流水车间调度问题的解所组成;交叉方法采用基于顺序和位置相结合的OPX方法;通过对Taillard算例中置换流水车间调度问题基准数据的测试,并对仿真实验的结果进行了分析,验证所提出IGA算法的有效性和可行性.     

基于演化策略算法的置换流水车间调度优化研究

采用演化策略算法求解置换流水车间调度问题,提出了一种基于工件次序的二维实数编码方法.设计了一种基于父代个体两点交叉互换的重组算子来生成子代个体,针对个体编码,采用局部基因随机重新生成的变异算子.计算结果说明,演化策略算法能够有效地对置换流水车间调度问题进行优化,其优化性能好于遗传算法和NEH启发式算法以及粒子群算法.     

基于智能水滴算法的学习效应生产调度研究

论文介绍了新兴仿生群智能优化算法—智能水滴算法,并且分析了智能水滴算法的仿生原理。论文针对具有学习效应的置换流水车间调度问题的特点,对算法进行了相应的变化,利用 Matlab 编程仿真计算得到结果,验证了智能水滴算法对于置换流水车间调度等优化组合问题的可行性和有效性。     

直觉模糊集相似度遗传算法求解多目标车间调度问题

为了提高高维多目标置换流水车间调度问题的求解质量,提出基于直觉模糊集相似度的遗传算法(similarity of intuitionistic fuzzy sets GA,SIFS_GA).算法中分别将参考解和Pareto解映射为参考解直觉模糊集和Pareto解直觉模糊集.计算两个集合之间的直觉模糊相似度,用以判断Pareto解的优劣.以直觉模糊集相似度值引导多目标遗传算法进化.对6个CEC标准测试集与10个流水车间调度测试实例进行仿真实验,结果表明SIFS_GA算法性能优于常用的多目标优化算法,且可以有效解决多目标置换流水车间调度问题,尤其在解决规模较大的问题上是一种有效方法.     

多构造蚁群优化求解置换流水车间调度问题

针对置换流水车间调度问题,提出了一种多构造蚁群优化求解算法。在该算法中,蚁群采用两种方式构造解,分别是基于NEH(Nawaz-Enscore-Ham,NEH)启发式算法和Rajendran启发式算法,并根据解的质量,自适应地调整两种构造方式在蚁群中所占的比例。对置换流水车间调度问题的基准问题测试表明,提出的算法是有效的。     

一种求解混合零空闲置换流水车间调度禁忌分布估计算法

结合混合零空闲置换流水车间调度问题MNPFSP(Mixed no-idle permutation flowshop scheduling problem)的特性,运用基于概率模型的分布估计算法解决该问题。算法将启发式算法融入分布估计算法中提高了初始解的质量。为了避免算法陷入局部最优,将禁忌算法融入分布估计算法中,提出一种禁忌分布估计算法求解混合零空闲置换流水车间问题。为了提高种群的多样性,加入了三种邻域搜索。实例测试结果显示,该算法求解混合零空闲置换流水车间问题具有很好的优势。     

求解PFSP的双种群协同学习算法

在人工蜜蜂群算法的基础上, 提出一种双种群协同学习算法.该算法根据个体适应度高低把蜜蜂群划分为 两个子群, 并重新定义子群的学习交流机制.在10个常用的基准测试函数上与其他4个常用的群体智 能算法进行比较, 比较结果表明, 所提出算法的性能有明显改进.采用双种群协同学习算法求解置换流水车间调度问题, 在一 些著名的中大规模测试问题包括21个Reeves实例和40个Taillard实例上进行 测试, 结果表明, 所提出的算法优于其他算法, 能有效解决置换流水车间调度问题.     

A hybrid variable neighborhood search algorithm for solving the limited-buffer permutation flow shop scheduling problem with the makespan criterion

This paper investigates the limited-buffer permutation flow shop scheduling problem (LBPFSP) with the makespan criterion. A hybrid variable neighborhood search (HVNS) algorithm hybridized with the simulated annealing algorithm is used to solve the problem. A method is also developed to decrease the computational effort needed to implement different types of local search approaches used in the HVNS algorithm. Computational results show the higher efficiency of the HVNS algorithm as compared with the state-of-the-art algorithms. In addition, the HVNS algorithm is competitive with the algorithms proposed in the literature for solving the blocking flow shop scheduling problem (i.e., LBPFSP with zero-capacity buffers), and finds 54 new upper bounds for the Taillard's benchmark instances.     

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

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

A genetic algorithm for permutation flow shop scheduling under make to stock production system

The permutation flow shop scheduling is a well-known combinatorial optimization problem that arises in many manufacturing systems. Over the last few decades, permutation flow shop problems have widely been studied and solved as a static problem. However, in many practical systems, permutation flow shop problems are not really static, but rather dynamic, where the challenge is to schedule n different products that must be produced on a permutation shop floor in a cyclical pattern. In this paper, we have considered a make-to-stock production system, where three related issues must be considered: the length of a production cycle, the batch size of each product, and the order of the products in each cycle. To deal with these tasks, we have proposed a genetic algorithm based lot scheduling approach with an objective of minimizing the sum of the setup and holding costs. The proposed algorithm has been tested using scenarios from a real-world sanitaryware production system, and the experimental results illustrates that the proposed algorithm can obtain better results in comparison to traditional reactive approaches.     

An improved particle swarm optimization algorithm for flowshop scheduling problem

The flowshop scheduling problem has been widely studied and many techniques have been applied to it, but few algorithms based on particle swarm optimization (PSO) have been proposed to solve it. In this paper, an improved PSO algorithm (IPSO) based on the “alldifferent” constraint is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan. It combines the particle swarm optimization algorithm with genetic operators together effectively. When a particle is going to stagnate, the mutation operator is used to search its neighborhood. The proposed algorithm is tested on different scale benchmarks and compared with the recently proposed efficient algorithms. The results show that the proposed IPSO algorithm is more effective and better than the other compared algorithms. It can be used to solve large scale flow shop scheduling problem effectively.     

A hybrid TP+PLS algorithm for bi-objective flow-shop scheduling problems

This paper presents a new, carefully designed algorithm for five bi-objective permutation flow shop scheduling problems that arise from the pairwise combinations of the objectives (i) makespan, (ii) the sum of the completion times of the jobs, and (iii) both, the weighted and non-weighted total tardiness of all jobs. The proposed algorithm combines two search methods, two-phase local search and Pareto local search, which are representative of two different, but complementary, paradigms for multi-objective optimization in terms of Pareto-optimality. The design of the hybrid algorithm is based on a careful experimental analysis of crucial algorithmic components of these two search methods. We compared our algorithm to the two best algorithms identified, among a set of 23 candidate algorithms, in a recent review of the bi-objective permutation flow-shop scheduling problem. We have reimplemented carefully these two algorithms in order to assess the quality of our algorithm. The experimental comparison in this paper shows that the proposed algorithm obtains results that often dominate the output of the two best algorithms from the literature. Therefore, our analysis shows without ambiguity that the proposed algorithm is a new state-of-the-art algorithm for the bi-objective permutation flow-shop problems studied in this paper.     

Solving a bi-criteria permutation flow-shop problem using shuffled frog-leaping algorithm

Flow shop problems as a typical manufacturing challenge have gained wide attention in academic fields. In this paper, we consider a bi-criteria permutation flow shop scheduling problem, where the weighted mean completion time and the weighted mean tardiness are to be minimized simultaneously. Due to the complexity of the problem, it is very difficult to obtain optimum solution for this kind of problems by means of traditional approaches. Therefore, a new multi-objective shuffled frog-leaping algorithm (MOSFLA) is introduced for the first time to search locally Pareto-optimal frontier for the given problem. To prove the efficiency of the proposed algorithm, various test problems are solved and the reliability of the proposed algorithm, based on some comparison metrics, is compared with three distinguished multi-objective genetic algorithms, i.e. PS-NC GA, NSGA-II, and SPEA-II. The computational results show that the proposed MOSFLA performs better than the above genetic algorithms, especially for the large-sized problems.     

解决具有混合约束柔性流水车间调度问题的粒子群优化算法

针对既存在阻塞限制工件又存在无等待约束工件的柔性流水车间调度问题, 提出了一种离散粒子群优化的求解方法。该方法采用基于排列的编码形式, 设计了推进—迭代算法进行解码并计算问题目标值, 利用离散粒子群优化算法进行全局优化, 利用迭代贪婪(iterated greedy, IG)算法提高种群个体的局部搜索能力。此外, 根据问题特点, 提出最早释放优先(first release first, FRF)和最早完工优先(first complete first, FCF)两种机器分配策略。仿真结果表明, 所提出的方法求解混合约束下柔性流水车间调度问题是可行的、有效的。