首页|改进遗传禁忌算法求解含恶化效应和多时间约束的柔性作业车间调度

改进遗传禁忌算法求解含恶化效应和多时间约束的柔性作业车间调度

扫码查看
原文链接
  • 万方数据
  • 维普
研究了在实际工业生产广泛出现的含恶化效应和多时间约束的柔性作业车间调度,考虑机器间的运输时间以及工件到达时间,以最小化最大完工时间为目标建立了整数规划模型,提出了一种改进遗传禁忌算法进行求解.该算法采用了基于工序和机器的区段链编码以及基于恶化效应和时间约束等问题特征的左移插入式主动解码;为提高种群多样性,引入反向学习规则和修正NEH启发式生成初始区段集,进而根据工序区段和机器区段提出基于工件号的改进优先工序交叉、基于机器位的改进多点交叉的混合交叉操作以及基于基因位的组合变异操作以更新区段链;为提高遗传算法的搜索能力,设计了嵌入工件插入/交换邻域解移动规则的禁忌搜索.最后,仿真实验对比了所提算法与CPLEX和一些现有算法,结果说明了所提出的改进遗传禁忌算法的有效性.
An Improved Genetic Tabu Algorithm for Flexible Job-shop Scheduling with Deterioration Effects and Multiple Time Constraints
Flexible job-shop scheduling was studied,which frequently surfaced in real-world industrial production and involved deterioration effects and multiple time constraints.An integer programming model was established to optimize the maximum completion time,considering both transportation times between machines and job arrival times.An improved genetic tabu algorithm was proposed for problem-solving.The algorithm used segment chain encoding based on operations and machines,and the active left-shift insertion decoding informed by problem characteristics such as deterioration effects and time constraints.To increase population diversity,an opposition-based learning rule and a modified NEH heuristic were introduced to generate initial segment sets.Then,according to the operation and machine segments,a mixed crossover operation consisting of an IPOX based on job numbers,an IMPX based on machine positions,and a combination mutation operation based on gene positions were utilized to update the segment chain.To enhance the search ability of the genetic algorithm,a tabu search algorithm that combined with the movement rules of job insertion or exchange for neighborhood solutions was designed.Lastly,simulation experiments compared the proposed algorithm with CPLEX and several existing algorithms.The results demonstrate the effectiveness of the proposed improved genetic tabu algorithm.

flexible job-shop schedulingdeterioration effecttransportation timejob arrival timeimproved genetic tabu algorithm

轩华、蔡舒跃、李冰

展开 >

郑州大学管理学院,河南郑州 450001

柔性作业车间调度 恶化效应 运输时间 工件到达时间 改进遗传禁忌算法

国家自然科学基金资助项目河南省科技攻关计划项目河南省科技攻关计划项目2023年河南省哲学社会科学规划项目

U18041512321023210932321023210262023BJJ085

2024

10.19495/j.cnki.1007-5429.2024.04.019

工业工程与管理
上海交通大学

工业工程与管理

CSTPCD北大核心
影响因子：0.763
ISSN：1007-5429
年,卷(期)：2024.29(4)
  • 8