蚁群遗传算法求解能力约束的柔性作业车间调度问题

提出一种主、从递阶结构的蚁群遗传求解算法。算法中,主级为蚁群算法,完成工件组合和加工路径选择;从级为遗传算法,完成主级约束下的设备排产。分别以工件延迟时间和设备可用能力为启发式信息,设计蚂蚁工件间和设备间的转移概率;以设备空闲时间最小为目标,设计从级染色体选择、多点交叉和多点变异3类遗传操作。从级染色体适应值取其代表调度方案中工件流通时间的倒数,从蚂蚁游历值取其对应从级染色体种群的最优适应值。最后,通过仿真和比较实验,验证了该算法的有效性     

基于面向对象遗传算法的柔性车间调度研究

针对柔性车间作业调度问题,基于面向对象思想设计了一种遗传算法。该算法将实际操作封装成基因类,工件封装成工件类,机床封装成机床类,调度方案封装成染色体类,基于堆栈思想设计了染色体的创建方式,提出了全新的染色体解码方式及变异方式。通过仿真实例证明了该算法的有效性和实用性。     

基于面向对象遗传算法的柔性车问调度研究

针对柔性车间作业调度问题,基于面向对象思想设计了一种遗传算法.该算法将实际操作封装成基因类,工件封装成工件类,机床封装成机床类,调度方案封装成染色体类,基于堆栈思想设计了染色体的创建方式,提出了全新的染色体解码方式及变异方式.通过仿真实例证明了该算法的有效性和实用性.     

基于并行协同进化遗传算法的多协作车间计划调度

为求解多协作车间的计划调度问题,提出了并行协同进化遗传算法。该算法采用基于工序的染色体编码方案。在遗传操作过程中,首先利用提出的基于工序约束的基因调整算法进行交叉操作和变异操作,保证了新个体满足工序约束。在解码操作过程中,采用考虑设备能力空间的解码算法,使得解码产生的调度为活动调度。此外,运用协同进化的思想,提出了协同适应值计算的算法,使协作环境的变化能灵敏地反映在个体的适应值上,从而有效地指导种群的进化。实例表明,该算法能够满足多协作车间并行协同调度的要求。     

考虑工件移动和成本的多目标柔性作业车间调度问题优化研究

针对考虑工件移动时间约束的柔性作业车间调度问题,构建了以加工总成本和最大加工时间最小为目标的数学模型并用改进遗传算法求解。针对柔性作业车间调度问题(FJSP)特性,算法中采用基于工序的集成编码操作,实现工序排序和机器匹配的内在关联并由此产生可行的调度方案;根据编码结构设计了有效的交叉和变异操作,从而避免了非法调度解的出现;为克服遗传算法的早熟收敛和减少调度开销,用贪婪解码算法生成主动调度、设计了自适应变异规则并采用混合子代产生模式提高染色体适应值。最后通过测试问题的求解及数值分析,证明了算法和模型的有效性及鲁棒性。     

用遗传算法解决作业车间的调度优化问题

用遗传算法对作业车间的生产周期这一目标进行优化调度。首先针对优化目标,在得到关键路径的基础上进行染色体编码,然后再通过交叉、变异等遗传操作,得到目标的最优或次优值。最后给出了算法运行结果,并作了简要分析     

求解柔性作业车间调度的遗传算法综述

柔性作业车间调度(FJSP)是一类具有广泛应用背景的调度问题,作为求解FJSP最受欢迎的算法之一,遗传算法引起了广泛关注。针对求解FJSP的遗传算法,特别是5类主要染色体编码方法以及相关的交叉和变异算子进行全面综述,并从编码可行性、编码空间与解空间的映射关系、染色体存储空间、解码复杂性、编码完备性、遗传操作复杂性和遗传操作多样性7个维度综合评价了5类编码方法。结果表明,MSOS-I编码是遗传算法求解FJSP较好的染色体编码方法,其染色体结构简单,并可选用较多类型的交叉和变异算子。     

基于遗传算法的作业车间双向调度优化问题

提出了一种基于混合遗传算法的双向调度算法，用来解决以关键工件交货期和生产周期为优化目标的作业车间调度问题。在算法中，遗传算法在全局范围内搜索最优调度染色体，双向调度算法根据得到的染色体进行调度。按照订单的要求，作业车间的工件可分为两类，即关键工件和一般工件。因此，车间调度与可分为前向调度和反向调度两个步骤，对于关键工度，利用剩余的车间资源，尽可能早完工。仿真结果表明该算法是可行的，与传统的调度算法相比，其优越性是明显的。     

工件到达时间未知的动态车间滚动重调度

研究工件动态到达且到达时间未知的车间重调度问题,目标是最小化所有工件的拖期和.动态事件频繁的调度环境,对调度算法的计算效率要求很高.在滚动时域分解方法框架下,提出关键工序集的概念,采用混合遗传算法确定关键工序集合及其对应的最优部分调度.在解码过程中,采用混合调度生成器将染色体中的基因转化为部分可行调度,对没有参与遗传进化的工序采用改进的修正交货期(Modified due date,MDD)规则确定其在机器上的加工顺序,以完全调度的目标值评价染色体的适应度.对大量算例的仿真表明基于关键工序集的重调度算法对动态事件的响应速度,大大优于基于完全工序集的重调度算法,并且具有良好的全局性能,兼顾了实际动态Job shop系统对调度性能和计算效率的要求.     

求解多目标混合流水车间调度的改进NSGA-Ⅱ

针对混合流水车间调度问题,以最小化能耗和最小化最大完工时间为求解目标,建立混合整数线性规划模型,提出求解该问题的改进快速非支配排序遗传算法(NSGA-Ⅱ)。算法染色体采用首阶段工件加工顺序码和设备分配码相结合的编码方式,最大程度确保算法在问题的整个解空间搜索Pareto前沿解。针对染色体编码设计了3种不同解码方法,其中两种解码方法与问题目标密切相关,用于引导算法搜寻方向;设计了一种贪婪变异算子,在提高种群多样性的同时兼顾算法的局部搜索能力。为确保Pareto前沿解集的分布性和收敛性,避免算法陷入局部最优,在采用精英保留策略的基础上提出一种全新的选择算子,并通过实验证明了该选择算子的有效性。为进一步节约能源,针对调度方案提出先右移再左移的调整策略,在不改变总完工时间的前提下大大节约了设备的待机和开关机能量。最后通过实验验证了改进NSGA-Ⅱ的有效性。     

基于可行域遗传算法的装配作业调度

为了对装配环境下的车间作业进行调度,提出了一种基于可行域搜索的遗传算法。为保证算法在进化过程中染色体始终保持合法性和可行性,在种群的初始化、交叉和变异等阶段,分别设计实现了首代修复算子、可行域交叉算子和可行域变异算子。可行域交叉算子和可行域变异算子的设计组合实现了算法的可行域搜索,减小了搜索空间,省去了复杂的解码修复操作,提高了求解效率,为解决复杂的装配车间调度问题提供了有价值的参考。通过与简单规则、禁忌搜索、普通遗传算法实验结果的比较,验证了所提算法的合理性和优越性。     

改进遗传算法求解柔性作业车间调度问题

分析柔性作业车间调度问题的特点,提出一种求解该问题的改进遗传算法。在考虑各个机器负荷平衡,所有机器上的总负荷和最大完工时间等性能指标更加合理情况下,设计一种全局搜索、局部搜索和随机产生相结合的初始化方法,提高种群初始解的质量,加快遗传算法的收敛速度。结合问题特点设计合理的染色体编码方式、交叉算子和变异算子,防止遗传操作过程中非法解的产生,避免染色体的修复,提高求解效率。使用文献中相同的实例测试利用初始化方法的改进遗传算法,并将计算结果与文献中其他遗传算法的测试结果进行比较,验证所提出的初始化方法的可行性和有效性。     

A Hybrid-Coded Genetic Algorithm Based Optimisation of Non-Productive Paths in CNC Machining

In order to optimise the non-productive paths in CNC machining under entry or exit constraints (such as in laser engraving and flame cutting), a hybrid-coded genetic algorithm (HCGA) is proposed in this paper. There are two chromosomes in the HCGA. One chromosome, called the master chromosome, uses a natural number-coded mode, and represents the sequence of productive contours. The other chromosome, called the slave chromosome, uses a binary-coded mode, and represents the entry or exit nodes of the productive contours. The two chromosomes use the same evaluation function and selection mechanism, but the crossover and mutation operators are different. The coding and genetic operators for open, closed and mixed productive contours are discussed in detail. The result shows that the HCGA is simple but effective for the optimising of non-productive paths in CNC machining.     

多目标柔性作业车间调度优化研究

提出了一种集成权重系数变化法和小生境技术的混合遗传算法,建立了包括时间、成本、交货期满意度和设备利用率在内的多目标优化模型。采用基于工序的编码方式和“间隙挤压法”活动化解码方法;遗传算子包括选择、交叉、变异3种类型;选择操作采用轮盘赌选择方式。为了保证解的收敛性和多样性,采用了精英保留策略和小生境技术。交叉操作采用线性次序交叉方式;变异操作采用互换操作变异方法。染色体的适应度是各个目标函数的随机加权和。仿真实验证明,提出的混合遗传算法可以有效解决柔性作业车间多目标调度优化问题。     

A novel hybrid genetic algorithm to solve the sequence-dependent permutation flow-shop scheduling problem

Flow-shop scheduling problem (FSP) deals with the scheduling of a set of jobs that visit a set of machines in the same order. The FSP is NP-hard, which means that there is no efficient algorithm to reach the optimal solution of the problem. To minimize the make-span of large permutation flow-shop scheduling problems in which there are sequence-dependent setup times on each machine, this paper develops one novel hybrid genetic algorithms (HGA). Proposed HGA apply a modified approach to generate the population of initial chromosomes and also use an improved heuristic called the iterated swap procedure to improve them. Also the author uses three genetic operators to make good new offspring. The results are compared to some recently developed heuristics and computational experimental results show that the proposed HGA performs very competitively with respect to accuracy and efficiency of the solutions.     

基于改进遗传算法的柔性作业车间调度方法研究

针对柔性作业车间调度问题,提出了一种自适应的遗传机制,构造出自适应的适值函数定义方法,设计了相应的自适应选择、交叉和变异3种算子。为了解决同一工序的不同机器的负荷平衡,提出了表征机器加工能力的能力系数。通过轮换方法实现了相同工序不同机器之间的调度。仿真实验结果表明,该调度算法具有可行性。     

A novel hybrid genetic algorithm for the open shop scheduling problem

In this paper, a hybrid genetic algorithm is proposed for the open shop scheduling problem with the objective of minimizing the makespan. In the proposed algorithm, a specialized crossover operator is used that preserves the relative order of jobs on machines and a strategy is applied to prevent from searching redundant solutions in the mutation operator. Moreover, an iterative optimization heuristic is employed which uses the concept of randomized active schedules, a dispatching index based on the longest remaining processing time rule and a lower bound to further decrease the search space. Computational results show that the proposed algorithm outperforms other genetic algorithms and is very competitive with well-known metaheuristics available in the literature.     

A new parallel genetic algorithm for solving multiobjective scheduling problems subjected to special process constraint

This study presents a multiobjective scheduling model on parallel machines (MOSP). Compared with other scheduling problems on parallel machines, the MOSP is distinct for the following characteristics: (1) parallel machines are nonidentical, (2) the type of jobs processed on each machine can be restricted, and (3) the multiobjective scheduling problem includes minimizing the maximum completion time among all the machines (makespan) and minimizing the total earliness/tardiness penalty of all the jobs. To solve the MOSP, a new parallel genetic algorithm (PIGA) based on the vector group encoding method and the immune method is proposed. For PIGA, its three distinct characteristics are as follows: Firstly, individuals are represented by a vector group, which can effectively reflect the virtual scheduling policy. Secondly, an immune operator is adopted and studied in order to guarantee diversity of the population. Finally, a local search algorithm is applied to improve the quality of the population. Numerical results show that it is efficient, can better overcome drawbacks of the general genetic algorithm, and has better parallelism.     

基于遗传算法的贴片机贴装顺序优化

元件贴装顺序是决定贴片机生产效率的关键问题。针对拱架型贴片机，采用了一种遗传算法。该遗传算法有其独特的染色体编码解码方式和交叉算子。算法中的染色体根据被贴装的印刷电路板由一条或多条子链组成，染色体的一个基因代表一个取贴循环。实验结果表明，该算法可以有效解决元件贴装顺序问题。同时，分析比较了三种传统交叉算子和该交叉算子的优化结果，表明这些传统交叉算子不能有效解决该问题。     

Scheduling flowshops with condition-based maintenance constraint to minimize expected makespan

Flexible job-shop scheduling problem (FJSP) is an extended traditional job-shop scheduling problem, which more approximates to practical scheduling problems. This paper presents a multi-objective genetic algorithm (MOGA) based on immune and entropy principle to solve the multi-objective FJSP. In this improved MOGA, the fitness scheme based on Pareto-optimality is applied, and the immune and entropy principle is used to keep the diversity of individuals and overcome the problem of premature convergence. Efficient crossover and mutation operators are proposed to adapt to the special chromosome structure. The proposed algorithm is evaluated on some representative instances, and the comparison with other approaches in the latest papers validates the effectiveness of the proposed algorithm.