Approximation algorithms for no idle time scheduling on a single machine with release times and delivery times

DOI10.1016/j.dam.2011.07.005zbMath1335.90037OpenAlexW2079870327MaRDI QIDQ496647

Imed Kacem, Hans Kellerer

Publication date: 22 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.07.005

zbMATH Keywords

schedulingapproximationmaximum latenessno idle time

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (11)

Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval ⋮ No-idle parallel-machine scheduling of unit-time jobs with a small number of distinct release dates and deadlines ⋮ Homogeneously non-idling schedules of unit-time jobs on identical parallel machines ⋮ Scheduling with limited machine availability ⋮ On scheduling with the non-idling constraint ⋮ A polynomial algorithm for the homogeneously non-idling scheduling problem of unit-time independent jobs on identical parallel machines ⋮ On scheduling with the non-idling constraint ⋮ Approximation algorithms for minimizing the maximum lateness and makespan on parallel machines ⋮ Approximation schemes for minimizing the maximum lateness on a single machine with release times under non-availability or deadline constraints ⋮ A PTAS for single-machine scheduling with release dates and job delivery to minimize makespan ⋮ Scheduling a single machine with primary and secondary objectives

Cites Work

• Unnamed Item
• On single-machine scheduling without intermediate delays
• A block approach for single-machine scheduling with release dates and due dates
• An approximation algorithm for a single-machine scheduling problem with release times and delivery times
• Efficient approximation schemes for scheduling problems with release dates and delivery times
• PERFORMANCE ANALYSIS OF SIX APPROXIMATION ALGORITHMS FOR THE ONE-MACHINE MAXIMUM LATENESS SCHEDULING PROBLEM WITH READY TIMES
• Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
• Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better
• On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness
• Sequencing with due-dates and early start times to minimize maximum tardiness

This page was built for publication: Approximation algorithms for no idle time scheduling on a single machine with release times and delivery times