排序方式: 共有57条查询结果,搜索用时 15 毫秒
1.
宋存利 《系统工程与电子技术》2019,41(5):1079-1086
针对最小化最大完工时间的带有不相关并行机的混合流水车间调度问题,提出了改进贪婪遗传算法。首先,该算法染色体编码采用基于工件加工顺序的编码,解码提出了两种设备分配方案,并考虑到不同阶段加工设备配置不同对算法的影响,采用了正序解码和逆序解码加再调度并用的解码策略。其次,提出贪婪交叉算子和贪婪变异算子,这些算子不仅承担改进种群,增加种群多样性的功能,同时还具有较强的局部搜索能力。最后通过正交实验确定算法的参数设置,与已有算法对已知案例的求解结果进行了比较,说明了该算法的有效性。同时实验表明了正序和逆序解码策略的必要性以及正序或逆序解码的时机。 相似文献
2.
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... 相似文献
3.
研究了目标函数是最小化最大完工时间的多处理机调度问题,此问题被证明是NP hard问题。分析了此问题现有模拟退火算法的缺陷,在此基础上构造了一个模拟退火算法SA LZ。大量的随机数据实验用于验证算法的性能和计算效率,实验结果表明SA LZ算法优于现有算法。 相似文献
4.
基于MMAS算法的带到达时间批调度问题研究 总被引:1,自引:0,他引:1
研究了工件带到达时间的目标为极小最大完工时间(Cmax)的单机批调度问题,采用最大-最小蚂蚁系统(max-min ant system,MMAS)进行求解.针对问题带到达时间以及分批的特性,提出了两种候选列表(candidate list)构建批序列,有效地缩小了搜索空间的维度;考虑两种候选列表的工件对构造解具有不同的影响,针对不同的候选列表设计了相应的启发式信息.仿真实验部分从求解质量和时间性能两方面比较了本文提出的算法和标准的蚂蚁系统(ant system,AS)算法以及使用不同候选列表的MMAS算法.结果表明,本文的算法在质量和时间两方面均全面优于标准的AS算法,而提出的候选列表使得该算法在大幅度提高时间性能的同时,仍然能够取得近似最优解,从而在求解质量和时间性能两方面取得平衡. 相似文献
5.
研究了工件的加工时间具有学习效应的链约束单机排序问题,在链可中断和不可中断两种情况下,均给出了目标函数为极小化最大完工时间的多项式算法。 相似文献
6.
针对文件分配问题,提出了一种求解树状网络中最短接通时间的快速算法.基于边着色和标号的思想,结合网络拓扑,将原来的网络分解为一系列更小规模的子网络进行处理.子网络对应的最优解逼近原始网络的最优解.理论分析和实验结果表明,在最短接通时间的计算精度略微降低的情况下,本文算法的计算复杂度为O(n). 相似文献
7.
一类P/Sij/Cmax问题的LS算法分析 总被引:2,自引:2,他引:0
提出一类有准备时间的排序问题;分析了LS算法解此问题的最坏情况;个性了LPT算法,使最差性能指标由4-2/m改进到8/3-2/3m。 相似文献
8.
平行批排序最小化最大完工时间在线算法的一个注记 总被引:2,自引:2,他引:0
讨论单机、平行批、批容量无界、最小化最大完工时间的在线排序问题.对该排序问题,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时刻.该在线算法仍然是最佳可能的,并且在一定意义下,该在线算法是渐近最优的. 相似文献
9.
工件加工时间为非线性分段函数的单机排序问题 总被引:1,自引:1,他引:1
讨论工件加工时间是开工时间非线性分段函数的单机排序问题,目标函数为极小化最大完工时间,总完工时间和加权总完工时间.对于目标函数为极小化最大完工时间和总完工时间的问题,给出了求解最优排序的多项式算法,对于目标函数为加权总完工时间的问题,给出了工件间的一致关系。 相似文献
10.
雷晓强 《云南大学学报(自然科学版)》2004,26(2):103-106
若干台处理机完成一批任务所需要的最少时间称为完工时间.一般地,当任务数目小于处理机数目时,为了提高处理机的利用率,缩短处理机完成所有任务的完工时间,可以把每项任务预先平均分成几个部分,再放到处理机上使用并行算法进行加工,这样使完工时间尽可能小.文中具体给出了在此情况下的完工时间. 相似文献