On the parameterized tractability of single machine scheduling with rejection

DOI10.1016/j.ejor.2018.07.038zbMath1403.90332OpenAlexW2883474883WikidataQ129483628 ScholiaQ129483628MaRDI QIDQ1991260

Nimrod Talmon, Danny Hermelin, Dvir Shabtay, 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

single machine schedulingfixed-parameter tractabilityparameterized complexityscheduling with rejection

Mathematics Subject Classification ID

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

Related Items (20)

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 ⋮ 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 ⋮ 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 ⋮ Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines ⋮ 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 Semi-Online Algorithm for Single Machine Scheduling with Rejection

Cites Work

• Unnamed Item
• A survey on offline scheduling with rejection
• A bicriteria approach to scheduling a single machine with job rejection and positional penalties
• Interval scheduling and colorful independent sets
• Scheduling and fixed-parameter tractability
• Single-machine scheduling under the job rejection constraint
• Geometric algorithms and combinatorial optimization
• Parameterized complexity of machine scheduling: 15 open problems
• Scheduling meets \(n\)-fold integer programming
• A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Multicriteria Optimization
• Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Parameterized Algorithms

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