2017/08/16 by Imed Kacem, Kacem, Imed, Hans Kellerer +1
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems #Scheduling and Optimization Algorithms #cs.DS
paper · pdf · doi:10.48550/arxiv.1708.05102
The extended version has been submitted to an international journal. It has been received by Springer on 12 April 2017
arxiv created 2017/08/16 · openalex publication_date 2017/08/16 · arxiv updated 2017/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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).