带退化效应和不可用区间的并行批处理机问题

本文研究的是一类带有不可用区间和线性退化效应的单机无界并行批处理机排序问题。工件开始加工时间的线性递增函数看成其实际的加工时间。批工件中加工时间的最大者为这批的加工时间,同批工件同时开始加工,且批一旦开始加工就不可中断,同批中工件的完工时间都相同并为这批的完工时间。本文通过对最优解性质的分析,分别给出了求解极小化最大费用和极小化总费用的拟多项式时间算法。特别当k固定、目标函数为误工工件数时,该问题为多项式时间可解的,并用数值例子验证了算法的有效性。