Approximation schemes for minimizing the maximum lateness on a single machine with release times under non-availability or deadline constraints

DOI10.1007/s00453-018-0417-6zbMath1404.90075arXiv1708.05102OpenAlexW2963430242MaRDI QIDQ1799225

Hans Kellerer, Imed Kacem

Publication date: 18 October 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1708.05102

zbMATH Keywords

latenessdeadlinessingle machine schedulingrelease timesapproximation algorithms

Mathematics Subject Classification ID

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

Related Items (5)

Minimizing maximum delivery completion time for order scheduling with rejection ⋮ A fully polynomial-time approximation scheme for total completion time minimization on a single machine with DeJong's learning effect and an availability constraint ⋮ Minimizing total weighted late work on a single-machine with non-availability intervals ⋮ Single machine scheduling with non-availability interval and optional job rejection ⋮ Minimizing tardiness scheduling measures with generalized due-dates and a maintenance activity

Cites Work

• Unnamed Item
• Unnamed Item
• Semi-online scheduling on a single machine with unexpected breakdown
• Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval
• An investigation on a two-agent single-machine scheduling problem with unequal release dates
• Approximation algorithms for no idle time scheduling on a single machine with release times and delivery times
• A branch-and-bound algorithm for a single machine sequencing to minimize the total tardiness with arbitrary release dates and position-dependent learning effects
• Approximation algorithms for single machine scheduling with one unavailability period
• Operator non-availability periods
• A block approach for single-machine scheduling with release dates and due dates
• Fast approximation algorithm for job sequencing with deadlines
• An approximation algorithm for a single-machine scheduling problem with release times and delivery times
• Single machine scheduling with small operator-non-availability periods
• Efficient approximation schemes for scheduling problems with release dates and delivery times
• SINGLE MACHINE SCHEDULING WITH FORBIDDEN INTERVALS AND JOB 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
• On scheduling with ready-times, due-dates and vacations
• Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better

This page was built for publication: Approximation schemes for minimizing the maximum lateness on a single machine with release times under non-availability or deadline constraints