共查询到18条相似文献,搜索用时 78 毫秒
1.
2.
本文研究有n个作业需在5个处理机中心进行加工,处理机中心i由l1个恒速机组成的非抢占式多机flow shop调度最小和问题.每个作业有s个工序,每个工序需在对应的处理机中心的任一台机器上加工处理,作业到达前不能加工,所有作业通过处理机中心的路径相同.目标是确定一个作业在每个处理机中心机器上的可行调度序列,使所有作业在最后处理机中心的加权完成时间总和最小化.在作业处理时间需求、作业权重分别为独立同分布的有界随机变量时,通过特殊flow shop调度松弛方法,我们证明该问题在作业数趋于无穷时,一个基于有效作业最短加权平均处理时间需求的启发式算法是渐近最优的. 相似文献
3.
随机柔性Flow shop加权完成时间调度问题的启发式策略性能分析 总被引:1,自引:0,他引:1
因实际生产中调度问题的规模很大,分析其近似算法的绝对性能比很难,有时甚至不可能,所以研究近似算法的渐近性能比就很有必要.本文针对随机柔性Flow shop加权完成时间调度问题,使用单机松弛和概率分析方法,证明了基于加权最短期望处理时间需求的启发式策略是渐近最优的. 相似文献
4.
5.
Flow—shop调度问题的遗传启发算法 总被引:11,自引:0,他引:11
结合遗传算法和启发式规则,构造了一种新的遗传启发搜索算法,用于求解Flow-shop调度问题。通过分析和实例计算表明,算法能够有效地适用于大规模加工过程中调度问题的优化计算,在运行时间,适应性和最优率等方面都具有很好的搜索优势。 相似文献
6.
用约束满足自适应神经网络和有效的启发式算法解Job—shop调度问题 总被引:1,自引:0,他引:1
提出一种用约束满足自适应神经网络结合有效的启发式算法求解Job-shop调度问题,在混合算法中,自适应神经网络具有在网络运行过程中神经元的偏置和连接权值自适应取值的特性,被用来求得调度问题的可行解,启发式算法分别和来增强神经网络的性能,获得确定排序下最优解和提高可行解的质量。仿整表明了本文提出的混合算法的快速有效性。 相似文献
7.
求解一类并行多机调度问题的混合启发式算法 总被引:8,自引:0,他引:8
该文研究了一类工件具有不同释放时间的并行多机调度问题,调度目标为使总流程时间最小。针对该类调度问题具有强NP—hard的特点,首先构造了的一种启发式算法,该算法能够在很短的时间内找到次优解。由于通常启发式算法会随着问题规模的扩大导致求解的质量有所下降,结合遗传算法的全局搜索能力,提出了一种混合启发式算法进一步改善解的质量。仿真结果表明该算法很好地结合了启发式算法和遗传算法的特点,能够在较短的时间内求解较大规模的调度问题,算法的计算量小,鲁棒性好。 相似文献
8.
9.
1 贪心算法简介 贪心算法总是作出在当前看来是最好的选择.也就是说贪心算法并不从整体最优上加以考虑,它所作出的选择只是在某种意义上的局部最优选择.贪心算法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它能产生整体最优解. 相似文献
10.
11.
针对以最小化时间表长为目标的复杂混合流水车间调度问题,提出了一种将机器布局和工件加工时间特征紧密结合的启发式算法.首先,充分利用各阶段平均机器负荷一般不相等的特点确定瓶颈阶段,构建初始工件排序.其次,针对在瓶颈阶段前加工时间较短而瓶颈阶段后加工时间相对较长的工件,在第1阶段优先开始加工.同时,在瓶颈阶段前的每一个阶段,每当有工件等待加工或同时完工时,优先选择瓶颈阶段前剩余加工时间最短的工件加工;在瓶颈阶段以及瓶颈阶段之后,则优先选择这台机器后剩余加工时间最长的工件加工.最后,采用工件交换和插入操作改进初始调度.用Carlier和Neron的Benchmark算例测试提出的启发式算法.将计算结果与NEH启发式算法进行了比较,平均偏差降低了0.0555%,表明这个启发式算法是有效的. 相似文献
12.
提出了一种新的求解置换flowshop调度问题的启发式算法。问题的目标是:在满足约束条件的前提下使得调度的makespan尽可能地小。定义了一种新的邻域结构。给出了跳坑策略以跳出局部最优解并且将搜索引向有希望的方向。计算了一组著名的问题实例。计算结果表明,算法的优度高于一种改进的遗传算法。 相似文献
13.
求解混合流水车间调度问题的一种遗传算法 总被引:3,自引:0,他引:3
由于高度的计算复杂性(NP-hard问题),混合流水车间调度问题很难求得最优解,启发式算法和智能优化算法(如遗传算法)求解此类问题的近优解的有效性和实用性已被证实。该文提出了一种基于遗传算法的求解方法,在由染色体转换成可行调度的过程中引入工件插入方法,同时设计了一种新的交叉算子。通过大量的数值计算表明,该算法的优化质量大大优于传统的遗传算法和NEH启发式算法。 相似文献
14.
15.
流水作业批调度问题优化算法研究 总被引:1,自引:0,他引:1
为解决流水作业环境作业尺寸有差异的批调度问题,建立了基于混合整数规划方法的最大时间跨度模型,分析问题的计算复杂性,给出设备数、作业数既定情况下的可行解规模.设计一种混合蚁群算法对最大时间跨度进行优化,结合算法的搜索机制和批调度启发式规则,实现了最小化最大时间跨度.利用模拟退火方法改进蚁群算法路径选择,避免算法陷入局部最优和过早收敛.实验设计随机算例,对各类不同规模的算例进行仿真实验,实验结果表明混合蚁群算法在最优解、平均运行时间和最大时间跨度等方面优于其他同类算法. 相似文献
16.
17.
为高效地求解多目标流水车间调度问题,提出了一种多目标混合遗传算法,此算法将局部搜索融入进化计算中,采用非劣解并行局部搜索策略,并依据基于Pareto支配关系的个体排序数和密度值进行适应度赋值,以加速算法的收敛,保持群体多样性.仿真结果表明,新算法能够有效地解决多目标流水车间调度问题. 相似文献
18.
为了克服单独的遗传算法用于车间作业调度缺点,提出一种遗传算法与启发式算法结合的混合遗传算法,在运用该算法的过程中给出了适合的遗传操作和启发式规则的应用方法。结果表明:混合遗传算法优于两种单独的算法。 相似文献