Improved algorithms for single machine scheduling with release dates and rejections

DOI10.1007/S10288-016-0303-5zbMath1333.90043OpenAlexW2234474530MaRDI QIDQ262445

Joseph Y.-T. Leung, Cheng He, Kangbok Lee, Michael L. Pinedo

Publication date: 29 March 2016

Published in: 4OR (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10288-016-0303-5

zbMATH Keywords

schedulingapproximation algorithmmakespanrejectionrelease datetotal rejection penalty

Mathematics Subject Classification ID

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

Related Items (11)

Scheduling with release times and rejection on two parallel machines ⋮ Faster algorithms for single machine scheduling with release dates and rejection ⋮ New approximation algorithms for machine scheduling with rejection on single and parallel machine ⋮ Minimizing maximum delivery completion time for order scheduling with rejection ⋮ Parallel machine scheduling with restricted job rejection ⋮ Algorithms for single machine scheduling problem with release dates and submodular penalties ⋮ Near-linear-time approximation algorithms for scheduling a batch-processing machine with setups and job rejection ⋮ Single-machine scheduling with maintenance activities and rejection ⋮ Vector scheduling with rejection on a single machine ⋮ Improved approximation algorithms for parallel machine scheduling with release dates and job rejection ⋮ Minmax scheduling and due-window assignment with position-dependent processing times and job rejection

Cites Work

• A survey on offline scheduling with rejection
• Single-machine scheduling under the job rejection constraint
• Single machine scheduling with release dates and rejection
• Fast approximation algorithm for job sequencing with deadlines
• Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem
• Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem
• Primal-Dual Schema for Capacitated Covering Problems
• Algorithms for Scheduling Independent Tasks
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling
• Unnamed Item

This page was built for publication: Improved algorithms for single machine scheduling with release dates and rejections