排序方式: 共有36条查询结果,搜索用时 0 毫秒
1.
讨论同时具有截断控制参数学习效应和退化效应并带有公共交货期窗口的单机调度问题,其中工件任务的加工时间不仅依赖资源分配,而且依赖于截断控制参数和工件任务的起始加工时间。全部工件任务共同拥有同一个交货期窗口,假设工件任务若在交货期窗口期限之内完成,则不产生费用;否则,提前或延后交货都要产生一部分费用。目标是确定最优排序以及资源分配最优方案,分别考虑如下2种情况:1)限制资源总成本费用,极小化带有提前、延后、公共交货期起始时间、交货期窗口规模、总完工时间绝对差、完工时间总和值的问题;2)在限制窗口规模、完工时间总和等费用成本的情况下,极小化总资源量。将上述2种问题进一步转化为指派问题,研究并证明所述2种问题可在多项式时间内解决,并分别给出2个最优算法。 相似文献
2.
3.
排序问题是一类重要的组合最优化问题,它的深刻的实际背景和广阔的应用前景,引起了广泛的关注。排序问题的一大特点是模型繁多,适用于某一模型的算法,只要将模型的条件稍加变化,该算法就可能不适用。在经典排序问题中,通常假设工件的加工时间是不变的,然而,在许多实际问题中,工件的加工时间受到加工机器设备、工件本身、加工顺序等许多因素的影响而未必是恒定的。文章提出一类新型的排序问题——带有工期窗口和维护时间的线性退化工件的单机排序问题,目标是寻找:1)最优维护的开始时间;2)工期窗口的位置和大小;3)工件的最优排序使得提前完工、误工、工期窗口开始时间和窗口宽度的总费用最小。文章最后给出了这个问题的最优算法,其时间复杂性是O(n2logn)。 相似文献
4.
罗成新 《沈阳师范学院学报》1999,(3):1-3
研究了具有工期限制、可以中断加工的排序问题1/pmtn,dj/hmax,给出了使最大费用函数hmax=max/h1(s1),…,hn(s0)/最小的一个多项式时间最优算法。 相似文献
5.
具有链形约束排序问题的最优算法 总被引:6,自引:0,他引:6
罗成新 《辽宁大学学报(自然科学版)》1998,25(1):84-88
本文给出了问题1|chains|∑W(1-e^-rcj)的一个最优算法,推广了文「1」中的一个结果。 相似文献
6.
罗成新 《重庆师范大学学报(自然科学版)》2022,(6):1
【目的】研究两个代理商松弛工期指派资源约束单机排序问题。【方法】代理商通过竞争在同一台处理机上处理各自任务集合,各有一定数量的资源可以分派给任务。任务有待定的松弛工期,处理时间与位置有关且是所获资源量的凸函数。目标是求出任务的处理顺序、工期和资源分配方案,使得乙代理商任务中最大费用不超过给定值,且甲代理商任务最大费用取最小值。将问题转化为凸规划问题,先求出任务资源数量;再通过求解指派问题确定任务的处理顺序,进而求得工期。【结果】给出了多项式时间的最优算法,提供算例说明算法的有效性。【结论】分析表明算法的计算时间复杂度为O(n3),其中n为两个代理商任务数中较大的一个。 相似文献
7.
本文讨论带有学习及退化效应和资源分配的交货期指派的单机排序问题。所有工件有一个公共的交货期,如果工件在交货期内完工将不产生任何费用,但是在交货期之前或之后完工将产生相应的提前或延误费用。工件的实际加工时间是与开工时间、在排序中位置和资源分配有关的函数。目标是确定最优交货期的位置、交货期的大小、工件的最优排序和最优资源分配,最小化包括提前、延误、交货期大小、交货期位置和资源消耗的总费用。证明了带有学习及退化效应和资源分配的交货期指派问题仍然是多项式可解的,并且最优算法是可以在O n()3时间内求出最优解。 相似文献
8.
研究两台平行机环境下加工时间线性退化的可拒绝排序问题,工件的实际加工时间是关于该工件开始加工时间的线性函数,每个工件都有一个独立的截止工期,在截止工期之前或之后完工的任务将分别受到提前和误工工件惩罚。工件允许被拒绝,如果工件被拒绝则需要支付一定的拒绝费用。目标是分别确定接受工件和拒绝工件的任务集合,找到接受任务的最优排序和每个被接受工件的最优任务工期最小化工期、误工工件惩罚、总完工时间以及被拒绝工件的惩罚费用之和。证明了此 NP 难问题可以通过动态规划方法求得最优解,并通过动态规划运用简化执行空间的方法给出了复杂度为o(n5D2/ε2)的全多项式近似策略(FPTAS),其中 n 表示工件的数量,ε 是允许误差界。
相似文献
相似文献
9.
考虑的是机器需要维护,且需要对若干个退化工件进行加工的单机排序问题。所谓退化情况是指每个工件的加工时间是关于它本身的开始时间的一个线性单增函数。该问题中工件允许被拒绝,如果工件被拒绝,那么需要支付拒绝惩罚;如果被加工,那么工件被排在机器上(机器需要在某一个固定的时间段内进行维修以提高其加工速度,且在这段时间内机器不能加工任何工件)进行加工。目标是寻找一个最优排序使得被加工工件的总完工时间与被拒绝工件的总惩罚之和最小。对于单机情形,利用划分程序的方法给出了一个全多项式近似方案,并得出该近似方案的时间复杂性,说明该问题是一般意义下NP-难的。 相似文献
10.
罗成新 《沈阳师范大学学报(自然科学版)》1998,(4)
对于问题1‖∑W_j(1-e~(-rC_j)),分别讨论了当 r 充分接近于零或所有权 W_j=1时的最优排序. 相似文献