本文主要研究人员不可用及工件带退化效应的单机排序问题, 目标是极小化工件的加权总完工时间。与机器有不可用时间限制的排序问题不同, 工件可以在人员不可用的时间段内加工, 但是不能在这个时间段内开工也不能在这个时间段内完工。我们首先证明当存在两个人员不可用的时间段时, 这个问题不存在最坏情形性能比为常数的多项式时间近似算法, 除非P=NP。当只存在一个人员不可用的时间段时, 我们给出一个伪多项式时间算法和一个完全多项式时间近似方案(FPTAS)。

The scheduling problem with operator non-availability periods and deteriorating jobs on a single machine is studied in this paper. The objective is to minimize the total weighted completion time. Unlike scheduling with machine non-availability constraints, a job can be processed in the operator non-availability time interval but can neither start nor complete in this period. We first show that there exists no polynomial-time approximation algorithm with a constant worst-case bound when the problem has two operator non-availability periods unless P=NP. We then present a pseudo-polynomial time algorithm and a fully polynomial-time approximation scheme (FPTAS) when there exists only one operator non-availability period.