排序方式: 共有52条查询结果,搜索用时 843 毫秒
21.
本文研究了同时带有恶化工件和机器恶化维修的单机工期指派问题。工件的实际加工时间是与工件基本加工时间和工件在排序中的实际加工位置相关的一般函数。机器维修时间与其开始维修时间有关,是其线性恶化函数。研究的目标函数是加权提前、延误和工期之和,目的是确定工件的最优加工顺序、公共工期及维修位置,使目标函数最小。将此问题转化为指派问题,从而证明了该问题在多项式时间内是可解的。对于问题的一种特殊情况进一步给出了一个复杂性为O(n2logn)的最优算法。
相似文献
相似文献
22.
在经典的排序问题中,工件的加工时间是固定不变的。然而,在实际生产中,工件的实际加工时间会发生变化。同时,机器通常需要进行保养,或发生故障时进行维修等原因,导致机器在某一时间段内无法工作,即机器的不可用区间。研究带有到达时间、退化效应和拒绝工件,及机器带有不可用区间的单机排序问题。在这一模型中,工件的开始加工时间越晚,其实际加工时间越大,实际加工时间是与其开始加工时间有关的函数。该问题中工件允许被拒绝。如果工件被拒绝,那么需要支付拒绝惩罚。讨论的目标函数是接受工件的加权总完工时间与所有拒绝工件的拒绝惩罚之和。首先说明该问题是一般意义NP-难的,进而利用划分程序的方法给出了一个全多项式近似方案,最后分析了该近似方案的时间复杂性。 相似文献
23.
24.
本文研究的是一类带有不可用区间和线性退化效应的单机无界并行批处理机排序问题。工件开始加工时间的线性递增函数看成其实际的加工时间。批工件中加工时间的最大者为这批的加工时间,同批工件同时开始加工,且批一旦开始加工就不可中断,同批中工件的完工时间都相同并为这批的完工时间。本文通过对最优解性质的分析,分别给出了求解极小化最大费用和极小化总费用的拟多项式时间算法。特别当k固定、目标函数为误工工件数时,该问题为多项式时间可解的,并用数值例子验证了算法的有效性。
相似文献
相似文献
25.
半连续批处理机调度问题,是从钢铁工业加热炉对管坯的加热过程中提炼出来的。工件按批加工,同一批中工件的加工时间等于此批中工件的最大加工时间,且工件必须按周期一个紧挨着一个进入、离开处理机。批处理机的容量为C,即最多可同时加工C个工件,批的容量为批中工件的个数,批的处理时间与批中工件的加工时间、批处理的容量和批的容量有关。本文研究释放时间与加工时间一致时,对于目标函数为最大完工时间问题,即时间表长问题,分析其最优解的性质,从而将问题转化为工件按释放时间非减顺序排列后,对工件进行分批,使得最大完工时间最小。在此基础上给出了一个复杂性为O(n2)的动态规划算法,证明了这个算法的最优性,并用数值例子进一步说明了算法的计算过程。 相似文献
26.
赵玉芳 《沈阳师范大学学报(自然科学版)》2013,(1):34-38
半连续型批处理机调度问题是从钢铁工业加热炉对管坯的加热过程中提炼出来的,其中把加热炉看作批处理机,同一时刻可以有C个工件被加工。工件以批方式进行加工,批中工件的进入、加工和离开都是按周期进行,同一批中的工件都有自己的开始加工时间和完工时间,且加工时间均等于这批工件中加工时间的最大者,批的大小为这批工件的个数。半连续型批处理机调度问题包含如何分批及安排各批间的加工顺序。考虑了单机且工件分簇的情况,其中在同一簇中工件的加工时间相同。目标函数为极小化总完工时间。对于工件的簇数是F的情况,通过最优解的性质给出了一个复杂性为O(F^2)的动态规划算法,能够获得对应问题的最优解。 相似文献
27.
笔者考虑的工件带有到达时间,且到达时间与工期同序、目标函数为加权误工工件数的单台串行批处理机排序问题是NP-难的,其中批处理机的容量无限。当同一批中的工件都到达后,此批才可以开始加工。同一批中工件的开始加工时间相同,批的加工时间为此批中所有工件的加工时间之和,且完工时间也相同,为这批中最后一个工件的完工时间;每批开始加工之前都有一个固定的调整时间,而批内工件间无调整时间,在批的调整时间内机器不能加工任何工件。研究工件带有2个不同到达时间,且到达时间与工期同序的情况。对于目标函数为加权误工工件数问题,分析了其最优解的性质,给出了拟多项式动态规划算法及其时间复杂性。 相似文献
28.
本文讨论了问题Pm|ressor,pj=1|Cmax的解法,并且证明了基本例子(基本向量)数不大于(o+1)(r+1)s-1.给出了求基本向量的算法. 相似文献
29.
本文给出处理机具有不同的开始加工时间的Q,ai|pmitn|Cmax排序问题的一个最优算法,算法的复杂性为O(m^2n^2)。 相似文献
30.
在工业生产过程中,由于一些特殊的原因,工件可以被拒绝加工但要付出相应的费用,即拒绝惩罚。为了节约处理成本,加工时间长的工件或者加工所需的费用高的工件,可以支付一定的费用来进行外加工或购买。将退化和拒绝结合起来考虑,讨论带有退化工件和拒绝的不同类型机排序问题。在这一模型中,工件的实际加工时间是其开始加工时间的线性递增函数,其中工件的退化率只与机器有关,与工件本身无关。目标函数是极小化接受工件的排序指标与拒绝工件总惩罚之和。排序指标分别为总时间表长和总完工时间。目的是找到拒绝工件集和接受工件集,并安排接受工件的加工顺序,使所求问题的目标函数值最小。通过将2个问题的目标函数转化为指派问题,证明了他们都是多项式可解的。 相似文献