求解混合流水车间调度的改进贪婪遗传算法

针对最小化最大完工时间的带有不相关并行机的混合流水车间调度问题,提出了改进贪婪遗传算法。首先,该算法染色体编码采用基于工件加工顺序的编码,解码提出了两种设备分配方案,并考虑到不同阶段加工设备配置不同对算法的影响,采用了正序解码和逆序解码加再调度并用的解码策略。其次,提出贪婪交叉算子和贪婪变异算子,这些算子不仅承担改进种群,增加种群多样性的功能,同时还具有较强的局部搜索能力。最后通过正交实验确定算法的参数设置,与已有算法对已知案例的求解结果进行了比较,说明了该算法的有效性。同时实验表明了正序和逆序解码策略的必要性以及正序或逆序解码的时机。     

A Modified Differential Evolution for Uniform Parallel Machines Scheduling Problem with Minimizing Makespan

The problem of scheduling jobs on uniform parallel machines with makespan (Cmax) minimization objective was studied.Due to its non-deterministic polynomial-time (N) hard nature,it is difficult to achie...     

一类P／Sij／Cmax问题的LS算法分析

提出一类有准备时间的排序问题；分析了ＬＳ算法解此问题的最坏情况；个性了ＬＰＴ算法，使最差性能指标由４－２／ｍ改进到８／３－２／３ｍ。     

树状网络中最短接通时间的快速算法

针对文件分配问题,提出了一种求解树状网络中最短接通时间的快速算法.基于边着色和标号的思想,结合网络拓扑,将原来的网络分解为一系列更小规模的子网络进行处理.子网络对应的最优解逼近原始网络的最优解.理论分析和实验结果表明,在最短接通时间的计算精度略微降低的情况下,本文算法的计算复杂度为O(n).     

平行批排序最小化最大完工时间在线算法的一个注记

讨论单机、平行批、批容量无界、最小化最大完工时间的在线排序问题.对该排序问题,Zhang等人(G.Zhang,X.Cai and C.K.Wong,On-line algorithms for minimizing makespan on batch processing machines,NavalResearch Logistics,48(2001),241-258.)和Deng等人(X.Deng,C.K.Poon and Y.Z.Zhang,Approximation algo-rithms in batch processing,Journal of Combinatorial Optimization,7(2003),247-257.)两组作者分别独立地给出了同一个竞争比为(5 1)/2的在线算法,并证明该在线算法是最佳可能的.在他们的算法中,在每一批中的加工时间最大的工件,不妨设其准备时间为r而加工时间为p,将被滞后到(1 α)r αp时刻以后加工,其中α=(5-1)/2.对同一问题设计了一个修订的在线算法,其中加工时间为p的工件只需要滞后到αp时刻.该在线算法仍然是最佳可能的,并且在一定意义下,该在线算法是渐近最优的.     

工件加工时间为非线性分段函数的单机排序问题

讨论工件加工时间是开工时间非线性分段函数的单机排序问题，目标函数为极小化最大完工时间，总完工时间和加权总完工时间．对于目标函数为极小化最大完工时间和总完工时间的问题，给出了求解最优排序的多项式算法，对于目标函数为加权总完工时间的问题，给出了工件间的一致关系。     

基于深度强化学习的云作业调度及仿真研究

针对复杂瞬变的多用户多队列多数据中心云计算环境中作业调度困难的问题,提出一种基于深度强化学习的作业调度方法.建立了云作业调度系统模型及其数学模型,并建立了由传输时间、等待时间和执行时间三部分构成的优化目标.基于深度强化学习设计了作业调度算法,给出了算法的状态空间、动作空间和奖赏函数.设计与开发了云作业仿真调度器,完成作...     

基于MMAS算法的带到达时间批调度问题研究

研究了工件带到达时间的目标为极小最大完工时间(Cmax)的单机批调度问题,采用最大-最小蚂蚁系统(max-min ant system,MMAS)进行求解.针对问题带到达时间以及分批的特性,提出了两种候选列表(candidate list)构建批序列,有效地缩小了搜索空间的维度;考虑两种候选列表的工件对构造解具有不同的影响,针对不同的候选列表设计了相应的启发式信息.仿真实验部分从求解质量和时间性能两方面比较了本文提出的算法和标准的蚂蚁系统(ant system,AS)算法以及使用不同候选列表的MMAS算法.结果表明,本文的算法在质量和时间两方面均全面优于标准的AS算法,而提出的候选列表使得该算法在大幅度提高时间性能的同时,仍然能够取得近似最优解,从而在求解质量和时间性能两方面取得平衡.     

极小化最大完工时间的批到达同时加工排序问题

考虑工件成批到达的同时加工排序问题,目标函数为极小化最大完工时间.给出模型在特殊情况下的统筹算法和针对一般情况的局部统筹算法,并通过大量的实例计算来验证两启发式方法的有效性.     

加工时间具有学习效应的链约束单机排序问题

研究了工件的加工时间具有学习效应的链约束单机排序问题,在链可中断和不可中断两种情况下,均给出了目标函数为极小化最大完工时间的多项式算法。