带有可变加工时间和可用性限制的排序问题

党 蕊, 赵玉芳

(沈阳师范大学 数学与系统科学学院, 沈阳 110034)



带有可变加工时间和可用性限制的排序问题

党 蕊, 赵玉芳

(沈阳师范大学 数学与系统科学学院, 沈阳 110034)

研究带有恶化效应、学习效应和可用性限制的单机和2台平行机的排序问题。在这个模型中,工件的实际加工时间与其基本加工时间、加工过程中所排位置及开始加工时间有关;同时由于维修、保养等原因,使得机器在某段时间不能加工工件,即机器具有可用性限制,且维修之后机器性能完全恢复,讨论的目标函数为总完工时间。对于可以在任意时间只维修一次的单机问题,以及只有一台机器具有可用性限制的2台平行机问题,分别给出了拟多项式时间的动态规划算法。特别对于一台机器只在零时刻开始维修另一台机器无可用性限制的特殊情况,通过将其转化为指派问题,给出了复杂性为O(n4)的多项式时间最优算法,并通过一个数值例子说明了其计算过程。

排序; 可用性限制; 恶化效应; 学习效应; 指派问题

在经典排序模型中,工件的加工时间是一个常数。但在实际生产中,由于长时间的工作,机器受到一定的影响,使得工件的开始加工时间越晚,其所需的实际加工时间越长,此现象称为恶化效应。同时,由于工人长期加工相同的工件获得了经验,使得工件所排位置越往后其所需要的实际加工时间越短,此现象称为学习效应。文献[1-2]研究带有恶化效应的单机排序模型,分别证明了最大完工时间问题和总完工时间问题是多项式时间可解的。……