一种适于异构环境的任务调度算法

针对异构环境独立任务调度问题提出两个调度原则,并基于Min-min算法提出优先级最小最早完成时间算法(Priority min-min,PMM).该算法将任务在各处理机上执行时间的标准误差作为任务的优先级.选取最早完成时间较小的k个任务,优先调度其中优先级最高的一个.在实验基础上分析了参数$k$对PMM算法性能的影响. PMM算法克服了min-min算法单纯追求局部最优的局限性,更适合于异构环境.实验数据表明PMM算法能有效地降低调度跨度,其性能比min-min算法有明显提高.     

求解置换流水车间调度问题的混合鸟群算法

针对置换流水车间调度问题（PFSP）,提出了一种混合鸟群算法（HBSA）以更加有效地最小化最大完工时间。首先,为了改善初始种群的质量和多样性,结合一种基于NEH（Nawaz-Enscore-Ham）的启发式算法和混沌映射提出了一种新的种群初始化方法;其次,为了使算法能够处理离散的调度问题,采用最大排序值（LRV）规则将连续的位置值转换为离散的工件排序;最后,为了强化算法对解空间的探索能力,借鉴变邻域搜索（VNS）和迭代贪婪（IG）算法的思想针对个体最佳工件排序和种群最佳工件排序分别提出了局部搜索方法。针对广泛使用的Rec标准测试集进行了仿真测试,并与目前有效的元启发式算法——刘等提出的混合差分进化算法（L-HDE）、混合共生生物搜索算法（HSOS）、离散狼群算法（DWPA）、多班级教学优化算法（MCTLBO）相比较,结果表明,HBSA取得的最佳相对误差（BRE）、平均相对误差（ARE）的平均值比上述四种算法至少下降了73.3%、76.8%,从而证明HBSA具有更强的寻优能力和更好的稳定性。尤其是针对测试算例Rec25和Rec27,仅HBSA的求解结果达到了目前已知最优解,进一步证明了其优越性。     

A competitive memetic algorithm for the distributed two-stage assembly flow-shop scheduling problem

This article addresses the distributed two-stage assembly flow-shop scheduling problem (DTSAFSP) with makespan minimisation criterion. A mixed integer linear programming model is presented, and a competitive memetic algorithm (CMA) is proposed. When designing the CMA, a simple encoding scheme is proposed to represent the factory assignment and the job processing sequence; and a ring-based neighbourhood structure is designed for competition and information sharing. Moreover, some knowledge-based local search operators are developed to enhance the exploitation ability. The influence of parameter setting on the CMA is investigated using the analysis of variance method. Extensive computational tests and comparisons are carried out, which demonstrate the effectiveness of the proposed CMA in solving the DTSAFSP.     

带驻留与重入约束的集束型设备调度算法

为有效地解决集束型设备加工过程中存在的驻留与重入约束问题,构建了带驻留与重入约束的集束型设备调度算法。首先进行调度问题域的描述,以系统Makespan最小为优化目标,建立了数学模型。在此基础上,提出一种搜索可行机械手运行路径的调度方法,结合驻留与重入约束的特征,构建了三个加工腔的集束型设备调度启发式算法。最后对算法进行了仿真实验,结果表明了该算法的有效性和可行性。     

大规模无等待流水调度问题的邻域迭代搜索算法

在分析大规模无等待流水调度问题特点的基础上,提出了利用相邻工件间完工时间距离求最小化完工时间的方法;通过研究工件插入和工件对的交换对最小化完工时间的影响,提出一种邻域迭代搜索算法,该算法降低了求解完工时间的时间复杂度,大大提高了算法效率;为避免算法在邻域搜索过程中陷入局部最优,将变邻域结构算法的思想应用于其中.仿真结果表明,所提出的算法能高效率解决大规模无等待流水调度问题,所得结果令人满意.     

基于新型邻域结构的混合算法求解作业车间调度

针对作业车间调度问题(Job shop scheduling problem,JSP),以优化最大完工时间为目标,提出一种融合新型邻域结构的混合求解方法。混合算法由具有全局搜索能力的遗传算法和基于邻域结构的邻域搜索算法构成。在邻域结构的设计中,研究了基于甘特图的工序头尾长度计算方法,以及关键工序查找方法。通过分析已有各种邻域结构及相关理论性质,指出邻域结构的根本在于引导关键工序对机器空闲时间进行利用,并将利用方式分为两种情况:直接利用和间接利用。综合两种利用方式,科学指导关键工序的移动,根据关键工序的类型定义相应的移动操作,使其移动范围突破了工序块的内部、紧前、紧后位置限制,扩大了有效移动范围。结合43个基准算例进行测试分析,验证了所提算法具有良好的求解性能。此外,所设计的邻域结构可以进一步融合其他智能算法求解JSP问题。     

Visibility enhancement of fog-degraded image using adaptive total variation minimisation

Images degraded due to bad weather conditions affect the quality of vision-based security systems, as the distortions obscure contrasts in the frames of the images. In this paper, we present a novel approach that uses adaptive total variation minimisation to retain the object and reduce the noise from a single image, thereby enhancing fog-degraded images. Representative experimental results show that our proposed algorithm is effective for contrast and saturation enhancement of fog-degraded images.     

基于动态关键路径的云工作流调度算法

为了提高资源行为动态异构的云环境中工作流任务的调度效率,提出了一种基于动态关键路径的工作流调度算法CWS-DCP。算法将工作流任务结构定义为有向无循环图DAG模型,改进了传统关键路径的一次性搜索模式,结合云资源可用性动态可变的特征,以动态自适应方式搜索关键路径,并确定关键任务。同时,在关键任务调度后,局部DAG的关键路径搜索根据资源可用性再次迭代更新,从而动态决策任务与资源间的调度方案。通过仿真实验,构建了三种不同类型的工作流结构作为测试数据源,并与其他六种同类型的启发式和元启发式算法进行了性能比较。实验结果表明,在资源可用性动态改变和工作流规模不断增大的情况下,CWS-DCP算法在多数工作流结构中均能得到执行跨度更好的调度方案和更少的调度开销。     

变量块内部迭代算法求解零空闲流水车间问题

零空闲流水车间问题（NIFSP）是流水车间问题中带有约束条件的典型NP-hard问题,在大多数现实场景下,零空闲约束是对机器的基本要求。而目前关于NIFSP问题提出的算法对于较大规模算例、综合性能及参数调整的灵活性较差。为此,以最小化最大完工时间为目标,提出了一种可变内部迭代算法VIIA。在VIIA的初始化阶段,使用改进的FRB5产生初始解,提高了FRB5的效率,在保证算法性能的同时极大地缩短了CPU消耗时间。在破坏重建阶段,通过增加对移除工件块数量的内部迭代,从而灵活调整参数值。VIIA增大了邻域搜索,以适应不同规模的算例。为了验证VIIA算法的性能,将该算法与在流水车间调度问题中表现优秀的几种算法进行了比较。实验结果证明了VIIA在NIFSP问题求解上性能的优越性,并且在最优解的搜索上,性能明显优于对比算法。     

求解混合流水车间调度问题的离散布谷鸟算法

为求解混合流水车间调度问题,提出一种离散布谷鸟算法。针对常规解码方法难以获得最优解的缺点,提出一种改进的解码方法,基于工件数与并行机数,按概率随机分配机器;根据标准布谷鸟算法中莱维飞行和巢寄生行为两种位置更新策略的核心思想,提出基于位置交叉和个体距离的离散莱维飞行,设计基于最优插入和最优交换的巢寄生策略。最后算例对比实验结果显示,采用基于改进解码方法的离散布谷鸟算法求解所得结果的平均值最小,验证了改进解码方法能提高解的质量;实例测试所得结果均获得了当前最优解,验证了离散布谷鸟算法求解该类问题的优越性。