Minimizing maximum lateness of jobs with naturally bounded job data on a single machine in polynomial time

DOI10.1016/J.TCS.2013.07.001zbMath1297.90060OpenAlexW2070961414WikidataQ57633820 ScholiaQ57633820MaRDI QIDQ391321

Frank Werner, Nodari Vakhania

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.07.001

zbMATH Keywords

single-machine schedulingrelease timebinary searchmaximum job lateness

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (5)

Theoretical expectation versus practical performance of Jackson's heuristic ⋮ Single-machine scheduling with workload-dependent maintenance duration to minimize maximum lateness ⋮ Fast solution of single-machine scheduling problem with embedded jobs ⋮ Dispersing points on intervals ⋮ Theoretical and practical issues in single-machine scheduling with two job release and delivery times

Cites Work

• Unnamed Item
• Single-machine scheduling with release times and tails
• Branch less, cut more and minimize the number of late equal-length jobs on identical machines
• Parallel machine problems with equal processing times: a survey
• Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A better algorithm for sequencing with release and delivery times on identical machines
• Minimizing Maximum Promptness and Maximum Lateness on a Single Machine

This page was built for publication: Minimizing maximum lateness of jobs with naturally bounded job data on a single machine in polynomial time