窦文卿,范静

一类资源费用可变的平行机排序问题

窦文卿,范静

(上海第二工业大学理学院,上海201209)

研究了资源费用可变的排序问题起源于服务系统和某些特定的生产系统,在这些服务系统中均存在着随着资源使用时段的不同而产生不同的费用。在资源费用可变的排序问题中,工件具有整数加工时间,工件在加工过程中允许中断。假定把机器的时间窗口划分为T个单位时间段,在某个时间段使用机器加工工件就要付出相应的费用,要求在给定的时间窗口内加工完所有的工件。问题的目标函数是经典排序的目标函数与所使用的总资源费用之和。对于目标函数为完工时间和与所使用的总资源费用之和的排序问题,给出了2个近似算法。

排序;平行机;资源费用;可中断

0 引言

在经典的排序模型中考虑的目标函数是Cmax、∑Cj、Lmax、Tmax、∑Uj等。经典的排序模型不考虑资源的使用费用,这是因为经典的排序模型均来源于生产与制造管理,而在制造业中用于工件处理的机器设备均为固定投资,一旦投资购买即为固定成本。然而在许多服务系统中,均存在着随着资源使用时段的不同而产生不同的费用。把资源的使用费用集成到排序与调度模型中,研究可变资源使用费用的排序问题,对于提升服务系统的绩效非常重要。由于资源的使用费用随时间段的变化而变化,故可假定把机器的时间窗口划分为T个单位时间段,在某个时间段使用机器加工工件就要付出相应的费用,要求在给定的时间窗口内加工完所有的工件。……