Non-approximability of just-in-time scheduling

DOI10.1007/s10951-009-0120-1zbMath1176.90235OpenAlexW1995157101WikidataQ57013245 ScholiaQ57013245MaRDI QIDQ1041346

Matthias Müller-Hannemann, Alexander Sonnikow

Publication date: 2 December 2009

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-009-0120-1

zbMATH Keywords

earlinesstardinessjust-in-timesingle machine schedulingnon-approximabilityspecial cases

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Ant colony systems for the single-machine total weighted earliness tardiness scheduling problem, Inverse chromatic number problems in interval and permutation graphs, Unnamed Item, Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Preemption in single machine earliness/tardiness scheduling
• Scheduling around a small common due date
• Machine scheduling with earliness, tardiness and non-execution penalties
• Approximation algorithms for minimizing the total weighted tardiness on a single machine
• The one-machine problem with earliness and tardiness penalties
• Multicriteria scheduling
• Single-Machine Scheduling of Unit-Time Jobs with Earliness and Tardiness Penalties
• Minimizing the average deviation of job completion times about a common due date
• One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
• Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date
• The Complexity of Near-Optimal Graph Coloring
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem