Common due date assignment and cumulative deterioration scheduling on a single machine. Issue 6 (3rd June 2017)

• Record Type: Journal Article
• Authors: Li, Shi-Sheng; Chen, Ren-Xia
• Is Part Of: Engineering optimization. Volume 49:Issue 6(2017)
• Page Start: 976
• Page End: 989
• Publication Date: 2017-06-03
• Subjects: scheduling -- cumulative deterioration -- due date assignment -- approximation algorithm; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2016.1227616
• Languages: English
• ISSNs: 0305-215X

Abstract

ABSTRACT: This article addresses a single-machine scheduling and common due date assignment problem in which the actual processing time of a job is a linear increasing function of the total basic processing times of already processed jobs. The aim is to determine simultaneously the common due date and job schedule that will minimize a cost penalty function including the due date assignment cost, total earliness penalties and a weighted number of tardy jobs. The problem is shown to be -hard even if there is no earliness penalty. Moreover, a pseudo-polynomial time algorithm and a fully polynomial time approximation scheme are proposed to solve the problem. An time algorithm is designed to solve the special case when all jobs have identical tardiness penalties.