Fully polynomial-time approximation scheme for single machine scheduling with proportional-linear deteriorating jobs. Issue 11 (2nd November 2019) - Zhao, Chuanli; Hsu, Chou-Jung
ABSTRACT: This article considers a single machine scheduling problem in which the processing time of a job is a linear increasing function of its starting time. The objective is to minimize the weighted number of tardy jobs. A pseudo-polynomial dynamic programming algorithm and a fully polynomial-time approximation scheme are proposed.