具有机器可利用性的双目标置换流水车间调度  

Bi-objective Permutation Flow Shop Scheduling with Machine Availability

作　　者：轩华 李海云 李冰 XUAN Hua;LI Haiyun;LI Bing(School of Management,Zhengzhou University,Zhengzhou 450001,China)

机构地区：[1]郑州大学管理学院,河南郑州450001

出　　处：《郑州大学学报（工学版）》2022年第5期17-23,共7页Journal of Zhengzhou University（Engineering Science）

基　　金：国家自然科学基金联合项目(U1804151);河南省科技攻关计划项目(202102310310)。

摘　　要：研究了具有机器可利用性的置换流水车间调度问题,引入CDS启发式算法和局域搜索构造出改进遗传算法,用于同时最小化总加权完成时间和总加权拖期。应用CDS启发式算法产生40%初始工件加工序列群,其余60%的初始工件加工序列群则通过随机程序产生,以此来提高初始工件加工序列群的质量。针对交叉和变异之后的工件加工序列,设计基于两两交换、单工件插入和多工件插入3种邻域解生成机制的局域搜索,以提高解的搜索空间。将所提出的改进遗传算法与基于遗传算法的3种启发式算法进行仿真实验,结果表明:所提算法在平均77.65 s内相对于其他算法的目标改进率分别为5.05%、3.09%、7.33%,这也说明了所提算法在较短的时间内能得到更好的目标值;随着问题规模的增大,改进效果更佳。A permutation flow shop scheduling problem with machine availability was studied.An improved genetic algorithm was proposed by introducing CDS heuristic algorithm and local search so that the total weighted completion time and total weighted tardiness were minimized.To improve the quality of the initial job processing sequence group,the CDS heuristic algorithm is applied to generate 40%of the group and the remaining 60%of the initial job processing sequence group was yielded by random procedure.For the job processing sequence after crossover and mutation,three generation schemes of neighborhood solutions based on pair-wise exchange,single-job insertion and multiple-job insertion were designed to carry out local search in order to extend the search space.The proposed improved genetic algorithm was tested with three genetic algorithm based heuristic algorithms.The results showed that the target improvement rate of the proposed algorithm was 5.05%,3.09%and 7.33%in the average 77.65 s,compares with other algorithms.It also showed that the proposed algorithm could obtain better target values in a shorter time.With the increase of the problem scale,the improvement effect was better.

关 键 词：双目标置换流水车间 机器可利用性 释放时间 改进遗传算法 邻域解生成机制 

分 类 号：TB49[一般工业技术]