Branch less, cut more and minimize the number of late equal-length jobs on identical machines

DOI10.1016/j.tcs.2012.08.031zbMath1259.90038OpenAlexW2077843589MaRDI QIDQ1929241

Nodari Vakhania

Publication date: 7 January 2013

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

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

zbMATH Keywords

polynomial-time algorithmsolution treescheduling identical machines

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items (4)

Theoretical expectation versus practical performance of Jackson's heuristic ⋮ Minimizing maximum lateness of jobs with naturally bounded job data on a single machine in polynomial time ⋮ A study of single-machine scheduling problem to maximize throughput ⋮ Interweaving real-time jobs with energy harvesting to maximize throughput

Cites Work

• Unnamed Item
• Unnamed Item
• Single-machine scheduling with release times and tails
• A note on scheduling equal-length jobs to maximize throughput
• Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs
• Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the `Tower of Sets' property
• Ten notes on equal-processing-time scheduling: at the frontiers of solvability in polynomial time
• On the complexity of minimizing the number of late jobs in unit time open shop
• Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times
• A better algorithm for sequencing with release and delivery times on identical machines
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs

This page was built for publication: Branch less, cut more and minimize the number of late equal-length jobs on identical machines