An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint

(2) Management Science; (3) Department of Computer Science; 83 Tat Chee Avenue; Chicago; China); City University of Hong Kong; D-22043 Hamburg; F. Jaehn (2); G. Calinescu (1); Germany

arxiv: 1710.10904 · v1 · pith:SENVPIMNnew · submitted 2017-10-30 · 💻 cs.DS

An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint

G. Calinescu (1) , F. Jaehn (2) , M. Li (3) , K. Wang (3) ((1) Department of Computer Science , Illinois Institute of Technology , Chicago , IL 60616 , USA

show 12 more authors

(2) Management Science Operations Research Helmut Schmidt University -- University of the Federal Armed Forces Hamburg Holstenhofweg 85 D-22043 Hamburg Germany (3) Department of Computer Science City University of Hong Kong 83 Tat Chee Avenue Kowloon Hong Kong SAR China)

This is my paper

classification 💻 cs.DS

keywords timecompletionconstraintfptasmachineminimizingpositionsingle

0 comments

read the original abstract

In this paper we study the classical scheduling problem of minimizing the total weighted completion time on a single machine with the constraint that one specific job must be scheduled at a specified position. We give dynamic programs with pseudo-polynomial running time, and a fully polynomial-time approximation scheme (FPTAS).

This paper has not been read by Pith yet.

An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint

discussion (0)