共查询到20条相似文献,搜索用时 9 毫秒
1.
2.
孙世杰 《应用数学与计算数学学报》1995,9(1):61-70
一组n个工件需在一台机器上加工,工件j所需的加工时间,应交工时间、准备时间分别为pj、dj、rj^0,准备时间可压缩量为xj,0≤aj≤rj^0,压缩权因子为ωj由最大延误Jmax和压缩费用∑ωjxj可构成文中(P1)-(P3)三个排序问题,在dj=0的条件下,引文「1」的作者证明了(P1)、(P3)为强NP-C的。本文在dj任意,pj=ωj=1的条件下,对(p1)-(P3)给出了一个伪多项式时间 相似文献
3.
4.
5.
处理机具有不同开始加工时间的可中断排序问题 总被引:6,自引:0,他引:6
本文对处理机具有的不同开始加工时间的可中断排序问题进行讨论,得到下面结论:若处理机具有相同开始加工时间的可中断排序问题存在最优排序算法,则相应的处理机具有不同开始加工时间的可中断排序问题也存在最优排序算法。 相似文献
6.
本文研究加工时间可控的单台机器的赋权的总完工时间问题.它是一个NP 难问题.我们利用半定规划松弛的技巧给出它的一个1.2752-近似算法. 相似文献
7.
研究工件具有相同的加工时间和相同的窗口交货期,目标函数是总费用函数的单机调度问题.给出了求解该问题的一个简洁的数学公式. 相似文献
8.
各机器具有相同加工时间的Flow Shop 成组排序问题 总被引:2,自引:0,他引:2
本文讨论了m台机器的Folw Shop成组排序问题,工件在不同机器上的加工时间相同,目标函数为极小化完工时间和。给出了一个多项式时间可解的最优算法。 相似文献
9.
本文研究了一类不相关平行机的排序问题,在该问题中工件的加工时间既具有学习效应,又资源可控,也就是说在该问题模型中,工件的实际加工时间为其正常的加工时间、加工过程中工件所处位置以及加工时间可控这些变量的函数。该研究的目的是为使得总机器负载和总的控制费用的加权和最小以及总的完工时间和总的控制费用的加权和最小。文章通过对问题的相关性质的分析和证明找到了一个解决问题的最优化算法,并且也证明了在处理机的数量给定的条件下,该问题的时间复杂性为O(nm+2),最后也给出了相应的数值例子来阐述该问题。 相似文献
10.
11.
讨论了处理机具有准备时间的Qm,aj|pj=1|Cmax排序问题,通过这一问题的一个下界,给出了一个最优算法,算法的复杂性为O(m^2)。 相似文献
12.
针对单机环境最优化加权总完工时间问题,当工件加工时间可通过分配资源进行压缩时,研究对工件的加工次序和时间压缩量的优化,从而权衡调度性能目标和资源成本目标。调度性能目标为压缩后工件的加权总完工时间,资源成本目标为工件压缩量的线性函数。此问题复杂性已被证明为NP-hard,为弥补较少有研究从Pareto优化角度求解该问题有效前沿的不足,针对经典NSGA-II求解时易早熟收敛的特点,采用算法混合方式进行优化方法研究。融合归档式多目标模拟退火算法跳出局部极值的优势,启用外部存档策略提升种群的多样性,采用主从模式的并行结构提升求解效率。最后为检验优化方法的有效性,一方面通过对Benchmark测试函数ZDT1-6的求解,表明混合算法对不同结构和形状目标函数兼具普适性和有效性;另一方面结合问题特点设计有效编码方式,针对随机生成算例进行求解。通过分析有效前沿收敛性和多样性,验证了所提方法对于优化加工时间可控单机加权总完工时间问题的有效性。 相似文献
13.
14.
15.
研究带有准备时间的单机学习效应模型,其中工件加工时间具有指数时间学习效应,即工件的实际加工时间是已经排好的工件加工时间的指数函数。学习效应模型考虑工件的实际加工时间同时依赖于工件本身的加工时间和已加工工件的累计加工时间,目标函数为最小化总完工时间。这个问题是NP-难的,提出了一个数学规划模型来求解该问题的最优解。通过分析几个优势性质和下界,提出分支定界算法来求解此问题,并设计启发式算法改进分支定界算法的上界值。通过仿真实验验证了分支定界算法在求解质量和时间方面的有效性。 相似文献
16.
17.
讨论工件加工时间是等待时间的非线性增加函数的单机排序问题,目标函数为极小化完工时间和与极小化最大延误.基于对问题的分析,对于一般非线性函数的情况,给出了工件间的优势关系.对于某些特殊情况,利用工件间的优势关系得到了求解最优排序的多项式算法.推广了文献中的结论. 相似文献
18.
延误工件个数与最大加工时间压缩比例之和的可控排序 总被引:2,自引:0,他引:2
张峰 《高校应用数学学报(A辑)》2004,19(2):241-245
研究工件加工时间可控的排序问题,讨论的目标函数是延误工件个数与最大加工时间压缩比例之和,证明这一问题是多项式时间可解的。 相似文献
19.
20.
加工时间恶化的两个成组加工排序问题 总被引:1,自引:0,他引:1
ChengMingbao SunShijie 《高校应用数学学报(英文版)》2005,20(2):225-234
This paper considers single-machine scheduling problems in group technology with the jobs‘ processing times being simple linear functions of their start times. The objective functions are the minimizing of makespan and total weighted completion time. Some optimal conditions and algorithms are given and the fact that the problem of total weighted completion times is NP-hard is proved. 相似文献