Improved algorithms for single machine scheduling with release dates and rejections

DOI10.1007/S10288-016-0303-5MaRDI QIDQ262445zbMATH OpenOpenAlexFDO

Authors Cheng He, Joseph Y.-T. Leung, 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

approximation algorithmmakespanrejectionrelease dateschedulingtotal rejection penalty

Mathematics Subject Classification ID

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

Recommendations

• Single machine scheduling with release dates and rejection
• Faster algorithms for single machine scheduling with release dates and rejection
• New approximation algorithms for machine scheduling with rejection on single and parallel machine
• Single machine scheduling with rejection to minimize the weighted makespan
• Scheduling on single machine and identical machines with rejection

Cites work

• A survey on offline scheduling with rejection
• Algorithms for Scheduling Independent Tasks
• Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem
• Fast approximation algorithm for job sequencing with deadlines
• Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem
• scientific article; zbMATH DE number 33203 (Why is no real title available?)
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Primal-Dual Schema for Capacitated Covering Problems
• Scheduling. Theory, algorithms, and systems.
• Single machine scheduling with release dates and rejection
• Single-machine scheduling under the job rejection constraint

Cited in

(21)

• Bounded single-machine parallel-batch scheduling with release dates and rejection
• Vector scheduling with rejection on a single machine
• Minmax scheduling and due-window assignment with position-dependent processing times and job rejection
• Near-linear-time approximation algorithms for scheduling a batch-processing machine with setups and job rejection
• Single-machine scheduling with maintenance activities and rejection
• Scheduling with release times and rejection on two parallel machines
• Parallel machine scheduling with restricted job rejection
• Faster algorithms for single machine scheduling with release dates and rejection
• scientific article; zbMATH DE number 5151903 (Why is no real title available?)
• Algorithms for single machine scheduling problem with release dates and submodular penalties
• The prize-collecting single machine scheduling with bounds and penalties
• Minimizing the maximum lateness for scheduling with release times and job rejection
• Improved approximation algorithms for parallel machine scheduling with release dates and job rejection
• W-prize-collecting with release dates on a single machine
• Coordinated order scheduling and outsourcing on dedicated parallel machines
• An efficient heuristic for a real-life OAS problem
• Two-machine job shop scheduling with optional job rejection
• Approximation algorithm for the W-prize-collecting scheduling problem on a single machine 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
• Improved algorithms for two single machine scheduling problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q262445)