Journal
NAVAL RESEARCH LOGISTICS
Volume 63, Issue 2, Pages 172-183Publisher
WILEY-BLACKWELL
DOI: 10.1002/nav.21684
Keywords
scheduling; late work; fully polynomial-time approximation scheme
Categories
Funding
- National Natural Science Foundation of China [11561036, 71301022]
- Ministry of Science Technology (MOST) of Taiwan [NSC 102-2221-E-035-070-MY3, MOST 103-2410-H-035-022-MY2]
- Hong Kong Polytechnic University
Ask authors/readers for more resources
We consider the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. We first discuss the approximability of the problem. We then develop two pseudo-polynomial dynamic programming algorithms and a fully polynomial-time approximation scheme for the problem. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms. (C) 2016 Wiley Periodicals, Inc.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available