排序方式: 共有26条查询结果,搜索用时 0 毫秒
1.
时间相关的单机排序的最坏竞争比分析 总被引:1,自引:0,他引:1
张新功 《重庆师范大学学报(自然科学版)》2013,30(5)
本文研究了工件的加工时间具有开工时间和加工所在位置相关的单机排序问题.工件的加工时间是序列中加工所在的位置和开工时间的非增函数,目标函数为最小化的误工工件个数和最小化总误工.本文对于所研究的2个目标函数利用Moore-Hodgson算法和EDD规则分别提出的启发式算法,对于目标函数位误工工件个数情形给出了最坏竞争比近似于2,最小化总误工给出非常数的最坏竞争比.进一步如果工件的加工时间和工期具有一致关系,分别给出了2个多项式时间算法. 相似文献
2.
本文对同一台机器下次品工件可重加工生产的问题进行研究。工件要求成批加工,每批包括连续加工的两个子批。第一子批的工件加工后,一部分工件是按照要求得到的优良品,另一部分工件是次品。次品的工件接着在第二子批重加工,而次品工件在等待重加工时会产生退化与学习现象,加工完成后得到的工件是优良品。同一子批的工件同时完工,工件的完工时间是该子批中最后一个工件的完工时间。假设每批生产的工件次品率是相同的。每一批工件开始加工和重加工时都有安装时间。目标函数是使总安装时间,重加工和库存持续费用最小,并且优良品工件的需求得到满足。对于该问题的一般情形给出了动态规划算法。接着当批工件的完工时间和批的规模满足一致关系,给出多项时间算法。
相似文献
相似文献
3.
【目的】研究需求率为售价的指数函数,变质率服从三参数Weibull分布的订货与定价策略。【方法】系统以利润最大化为目标函数,考虑商品变质时带来的成本,引入价格折扣,构建了库存模型。【结果】采用直接法和泰勒展开式对模型进行近似求解,提供算例分析以得到问题的近似解,通过对折扣率、变质率灵敏度分析给出了相应的合理化管理建议。【结论】零售商在处理保鲜期后的商品时引入的价格折扣越高销量越大。商品的流动环境因子的增加会使得零售商成本增加,在销售过程中可采用更为先进的交通工具和储存手段。 相似文献
4.
重新排序问题是一种新型的排序模型,它有着重要的实际应用背景。生产部门根据自己的生产计划或是由客户提出的要求,在生产前一定时期内事先有一个作业方案,将已有的任务或订单按照某一规则安排好,使某一目标值最优。但是在即将开始生产之前或在生产过程中又有新的客户订单或任务到达。这时就要把新的任务和原有的还未加工的任务一起加工。为了不失信于对原客户的承诺或不耽误原任务的完成,这就要求在原有的工件或任务的次序不至于打乱得过多的前提下,使得总的目标函数值达到最优。本文考虑学习效应作用下的最小化总完工时间的重新排序问题,其中工件的加工时间是其所在序列加工位置有关的函数。对于最大序列错位、总序列错位和最大时间错位下的最小化总完工时间问题均给出了多项式时间算法,对于总时间错位下的最小化总完工时间问题提出了动态规划算法,并证明这个算法是拟多项式时间的。 相似文献
5.
【目的】研究共同工期下与总权误工相关的单机双代理排序问题。【方法】通过动态规划方法分析了双代理模型,即在第2个代理的总误工工件个数不超过一个给定值的前提下,使得第1个代理的总权误工最小。【结果】分别给出了最优性质、伪多项式时间算法以及时间复杂度分析。【结论】通过算例实验分析说明了算法的可行性。 相似文献
6.
讨论带有线性位置恶化及维修区间与加工时间有关的单机排序问题。工件的实际加工时间与其所在的位置线性相关,维修区间长度与其前一组工件的完工时间线性相关。每次维修后都将机器恢复到最原始状态。目标函数为最大完工时间和总完工时间的和。证明在最大完工时间情形下工件满足组平衡原则。对于总完工时间问题,可以转化为线性指派问题。最后分别给出这两个问题的多项式时间算法。
相似文献
相似文献
7.
本文研究了工件的加工时间具有开工时间和加工所在位置相关的单机排序问题。工件的加工时间是序列中加工所在的位置和开工时间的非增函数,目标函数为最小化的误工工件个数和最小化总误工。本文对于所研究的2个目标函数利用Moore-Hodgson算法和EDD规则分别提出的启发式算法,对于目标函数位误工工件个数情形给出了最坏竞争比近似于2,最小化总误工给出非常数的最坏竞争比。进一步如果工件的加工时间和工期具有一致关系,分别给出了2个多项式时间算法。 相似文献
8.
9.
研究考虑机器具有老化效应和工件带有释放时间约束的作业车间调度问题(job shop-scheduling problem, JSP)。建立以最小化最大完工时间为目标的调度优化模型,并设计1种改进的算术优化算法(improved arithmetic optimization algorithm, IAOA)对该问题进行求解。算法首先通过排序值转换规则将IAOA连续解空间映射到JSP的离散空间,并对JSP进行编码,然后使用插入式贪婪解码算法进行解码。提出了非线性数学优化加速函数和6种邻域搜索策略对标准算术优化算法(arithmetic optimization algorithm, AOA)进行改进。通过在33个JSP数据集上进行测试并与AOA、灰狼优化算法和算术三角函数优化算法进行对比分析,结果表明提出的IAOA具有较好的优化效果以及收敛能力,且该算法克服了AOA求解精度低、收敛速度慢的缺陷。 相似文献
10.
研究同总加权误工损失有关联的两个代理间单机排序的问题.两个代理之间的排序问题中,允许工件在加工过程中中断,设总加权误工损失为第一个代理的目标函数,最大正则函数是第二个代理的目标函数.在此问题中结合EDD规则确定一个最优排序算法,使得满足第二个代理目标可行的情况下,第一个代理的目标函数最小.在上述问题最优排序规则确定的前提下,求出最优排序使得第一个代理的目标函数最小.最终给出了和总加权误工损失有关的排序问题的一个最优算法,并且证明了问题在在多项式时间内可解. 相似文献