Single-machine scheduling under the job rejection constraint

DOI10.1016/j.tcs.2010.02.006zbMath1192.68111OpenAlexW2088000640MaRDI QIDQ964407

Jinjiang Yuan, Li-Qi Zhang, Ling-Fa Lu

Publication date: 15 April 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.02.006

zbMATH Keywords

scheduling rejection penalty fully polynomial-time approximation scheme

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (34)

Minsum scheduling with acceptable lead-times and optional job rejection ⋮ Scheduling a single machine with parallel batching to minimize makespan and total rejection cost ⋮ A bi-objective model for the single-machine scheduling problem with rejection cost and total tardiness minimization ⋮ A general scheme for solving a large set of scheduling problems with rejection in FPT time ⋮ A greedy heuristic for solving scheduling problems with bounded rejection cost ⋮ A note on ``Two-machine flow-shop scheduling with rejection and its link with flow-shop scheduling and common due date assignment ⋮ Parallel machine scheduling with restricted job rejection ⋮ A tardiness-augmented approximation scheme for rejection-allowed multiprocessor rescheduling ⋮ Single-machine scheduling with production and rejection costs to minimize the maximum earliness ⋮ Bicriteria order acceptance and scheduling with consideration of fill rate ⋮ A survey on offline scheduling with rejection ⋮ Parallel-batch scheduling with rejection: structural properties and approximation algorithms ⋮ Penalty cost constrained identical parallel machine scheduling problem ⋮ Permutation flow shop scheduling with order acceptance and weighted tardiness ⋮ On the complexity of scheduling problems with a fixed number of parallel identical machines ⋮ Single machine scheduling to minimize maximum earliness/tardiness cost with job rejection ⋮ Flowshop scheduling with learning effect and job rejection ⋮ Single-machine scheduling with maintenance activities and rejection ⋮ Reductions between scheduling problems with non-renewable resources and knapsack problems ⋮ Supply chain scheduling to minimize holding costs with outsourcing ⋮ Vector scheduling with rejection on a single machine ⋮ Order acceptance and scheduling with consideration of service level ⋮ On the parameterized tractability of single machine scheduling with rejection ⋮ Scheduling with job-rejection and position-dependent processing times on proportionate flowshops ⋮ Order acceptance and scheduling with machine availability constraints ⋮ Single machine lot scheduling with optional job-rejection ⋮ Minmax scheduling and due-window assignment with position-dependent processing times and job rejection ⋮ Minimizing total late work on a single machine with generalized due-dates ⋮ Single Machine Scheduling with Outsourcing Under Different Fill Rates or Quantity Discount Rates ⋮ Regular scheduling measures on proportionate flowshop with job rejection ⋮ Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates ⋮ Two-agent scheduling with rejection on a single machine ⋮ A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems ⋮ Improved algorithms for single machine scheduling with release dates and rejections

Cites Work

This page was built for publication: Single-machine scheduling under the job rejection constraint