On the parameterized tractability of single machine scheduling with rejection

DOI10.1016/J.EJOR.2018.07.038MaRDI QIDQ1991260zbMATH OpenOpenAlexWikidataFDO

Authors Danny Hermelin, Dvir Shabtay, Nimrod Talmon, Michael L. Pinedo

Publication date 30 October 2018

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2018.07.038

zbMATH Keywords

fixed-parameter tractabilityparameterized complexityscheduling with rejectionsingle machine scheduling

Mathematics Subject Classification ID

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

Recommendations

• On the parameterized tractability of single machine scheduling with rejection to minimize the weighted makespan
• Single machine scheduling with rejection and generalized parameters
• Single-machine scheduling under the job rejection constraint
• New approximation algorithms for machine scheduling with rejection on single and parallel machine
• Single Machine Scheduling with an Availability Constraint and Rejection
• Scheduling on single machine and identical machines with rejection
• Single machine scheduling with rejection to minimize the \(k\)-th power of the makespan
• Single machine scheduling with rejection to minimize the weighted makespan
• A semi-online algorithm for single machine scheduling with rejection
• A single machine scheduling problem with rejection jobs and a machine non-availability interval

Cites work

• A bicriteria approach to scheduling a single machine with job rejection and positional penalties
• A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
• A survey on offline scheduling with rejection
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Multicriteria Optimization
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Parameterized algorithms
• Parameterized complexity of machine scheduling: 15 open problems
• Scheduling and fixed-parameter tractability
• Scheduling meets n-fold integer programming
• Scheduling two competing agents when one agent has significantly fewer jobs
• Single-machine scheduling under the job rejection constraint

Cited in

(28)

• Single machine lot scheduling with optional job-rejection
• Applying ``peeling onion approach for competitive analysis in online scheduling with rejection
• Minimizing total late work on a single machine with generalized due-dates
• Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates
• 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
• Single machine scheduling with rejection and generalized parameters
• Single machine scheduling with rejection to minimize the weighted makespan
• A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection
• Scheduling with competing agents, total late work and job rejection
• A semi-online algorithm for single machine scheduling with rejection
• Scheduling and fixed-parameter tractability
• Scheduling problems with rejection to minimize the \(k\)-th power of the makespan plus the total rejection cost
• Fixed interval scheduling with third‐party machines
• Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
• Equitable scheduling on a single machine
• Parallel-batch scheduling with rejection: structural properties and approximation algorithms
• Single machine scheduling with rejection to minimize the \(k\)-th power of the makespan
• A multivariate complexity analysis of the material consumption scheduling problem
• Order acceptance and scheduling with delivery under generalized parameters
• Single machine scheduling to minimize maximum earliness/tardiness cost with job rejection
• On the parameterized tractability of single machine scheduling with rejection to minimize the weighted makespan
• Minimizing the maximum lateness for scheduling with release times and job rejection
• Serial batching to minimize the weighted number of tardy jobs
• Order acceptance and scheduling with weighted makespan
• Scheduling kernels via configuration LP
• The circular balancing problem
• Complexity of scheduling few types of jobs on related and unrelated machines

This page was built for publication: On the parameterized tractability of single machine scheduling with rejection

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