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

DOI10.1007/s10878-013-9643-7zbMath1325.90041OpenAlexW2059001284MaRDI QIDQ498410

Yann Lanuel, Imed Kacem, Hans Kellerer

Publication date: 28 September 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-013-9643-7

zbMATH Keywords

schedulingapproximation algorithmslate jobsnon-availability intervals

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (5)

Multitasking via alternate and shared processing: algorithms and complexity ⋮ Minimizing total weighted late work on a single-machine with non-availability intervals ⋮ Single-machine serial-batching scheduling with a machine availability constraint, position-dependent processing time, and time-dependent set-up time ⋮ Prioritized surgery scheduling in face of surgeon tiredness and fixed off-duty period ⋮ Improving the solution complexity of the scheduling problem with deadlines: A general technique

Cites Work

• Unnamed Item
• Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates
• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• Fast approximation algorithm for job sequencing with deadlines
• Approximation algorithms for scheduling a single machine to minimize total late work
• Scheduling with limited machine availability
• Machine scheduling with an availability constraint
• Algorithms for Scheduling Independent Tasks
• Combinatorial Problems: Reductibility and Approximation
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Scheduling

This page was built for publication: Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals