Approximation Schemes for Minimizing the Maximum Lateness on a Single Machine with Release Times Under Non-availability or Deadline Constraints

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 20 Feb 2018Embargo end date: 01 Jan 2017 Austria English Publisher:Springer Science and Business Media LLCJournal:Algorithmica, volume 80, pages 3,825-3,843 (issn: 0178-4617, eissn: 1432-0541,

Copyright policy )

Authors: Kacem, Imed; Kellerer, Hans;

doi: 10.1007/s00453-018-0417-6 , 10.48550/arxiv.1708.05102

arXiv: 1708.05102

Approximation Schemes for Minimizing the Maximum Lateness on a Single Machine with Release Times Under Non-availability or Deadline Constraints

- Summary
- Subjects
- Metrics

Abstract

In this paper, we consider four single-machine scheduling problems with release times, with the aim of minimizing the maximum lateness. In the first problem we have a common deadline for all the jobs. The second problem looks for the Pareto frontier with respect to the two objective functions maximum lateness and makespan. The third problem is associated with a non-availability constraint. In the fourth one, the non-availibility interval is related to the operator who is organizing the execution of jobs on the machine (no job can start, and neither can complete during the operator non-availability period). For each of the four problems, we establish the existence of a polynomial time approximation scheme (PTAS).

The extended version has been submitted to an international journal. It has been received by Springer on 12 April 2017

Country

Austria

Related Organizations

Keywords

FOS: Computer and information sciences, Single machine scheduling, Deterministic scheduling theory in operations research, lateness, [INFO] Computer Science [cs], Approximation methods and heuristics in mathematical programming, Deadlines, Approximation algorithms, Computer Science - Data Structures and Algorithms, release times, Data Structures and Algorithms (cs.DS), single machine scheduling, deadlines, approximation algorithms, Lateness, Release times

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	12
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%