考虑了机器具有使用限制的混合恶化排序问题. 其中部分工件的加工时间是固定常数, 另一部分的是其开工时间的简单线性函数, 工件是不可中断的. 文章目标是极小化最大完工时间. 对于单机问题, 证明了问题是一般意义下的NP-难的, 给出了一个$\frac{4}{3}$-近似算法, 并证明了算法界是紧的. 对于平行机问题, 证明了问题是强NP- 难的.

In this paper, we consider the scheduling problem in which the machines have availability constraints and the processing times of some jobs are constant, while others are simple linear increasing functions of their starting times. The objective is to minimize the makespan for non-resumable jobs. For the single-machine issue, we show that this problem is NP-hard in the ordinary sense, provide a $\frac{4}{3}$-approximation algorithm and show that the bound is tight. For the parallel-machine issue, we show that this problem is NP-hard in the strong sense.