Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals

Imed Kacem (), Hans Kellerer () and Yann Lanuel ()
Additional contact information
Imed Kacem: Université de Lorraine
Hans Kellerer: University of Graz
Yann Lanuel: Université de Lorraine

Journal of Combinatorial Optimization, 2015, vol. 30, issue 3, No 1, 403-412

Abstract: Abstract In this paper we consider the maximization of the weighted number of early jobs on a single machine with non-availability constraints. We deal with the resumable and the non-resumable cases. We show that the resumable version of this problem has a fully polynomial time approximation scheme (FPTAS) even if the number of the non-availability intervals is variable and a subset of jobs has deadlines instead of due dates. For the non-resumable version we remark that the problem cannot admit an FPTAS even if all due dates are equal and only one non-availability interval occurs. Nevertheless, we show in this case that it admits a polynomial time approximation scheme (PTAS) for a constant number of non-availability intervals and arbitrary due dates.

Keywords: Scheduling; Non-availability intervals; Late jobs; Approximation algorithms (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9643-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:3:d:10.1007_s10878-013-9643-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9643-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().