Fully polynomial-time approximation scheme for single machine scheduling with proportional-linear deteriorating jobs. Issue 11 (2nd November 2019)

• Record Type: Journal Article
• Authors: Zhao, Chuanli; Hsu, Chou-Jung
• Is Part Of: Engineering optimization. Volume 51:Issue 11(2019)
• Page Start: 1938
• Page End: 1943
• Publication Date: 2019-11-02
• Subjects: Scheduling -- single machine -- deteriorating jobs -- fully polynomial-time approximation scheme; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2018.1558446
• Languages: English
• ISSNs: 0305-215X

Abstract

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.