Unary NP-hardness of minimizing the number of tardy jobs with deadlines

DOI10.1007/S10951-016-0479-8MaRDI QIDQ2398650zbMATH OpenOpenAlexFDO

Authors Jinjiang Yuan

Publication date 18 August 2017

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10951-016-0479-8

zbMATH Keywords

deadlinesNP-hardnumber of tardy jobsscheduling

Mathematics Subject Classification ID

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

Recommendations

• Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines
• Unary NP-hardness of preemptive scheduling to minimize total completion time with release times and deadlines
• Unary NP-hardness of minimizing total weighted tardiness with generalized due dates
• Minimizing Total Tardiness on One Machine is NP-Hard
• Unary NP-hardness of minimizing the total deviation with generalized or assignable due dates

Cites work

• A multiple-criterion model for machine scheduling
• A note on the single machine scheduling to minimize the number of tardy jobs with deadlines
• A survey of single machine scheduling to minimize weighted number of tardy jobs
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Multiagent scheduling. Models and algorithms
• Scheduling Problems with Two Competing Agents
• Sequencing a single machine with due dates and deadlines: An ILP-based approach to solve very large instances
• Single Machine Scheduling with Deadlines to Minimize the Weighted Number of Tardy Jobs
• The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard
• The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard

Cited in

(17)

• Unary NP-hardness of minimizing total weighted tardiness with generalized due dates
• A note on competing-agent Pareto-scheduling
• Single-machine scheduling with positional due indices and positional deadlines
• A note on the complexity of two supply chain scheduling problems
• Pareto-scheduling with family jobs or ND-agent on a parallel-batch machine to minimize the makespan and maximum cost
• Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices
• Unary NP-hardness of preemptive scheduling to minimize total completion time with release times and deadlines
• Scheduling to tradeoff between the number and the length of accepted jobs
• ND-agent scheduling of linear-deteriorating tasks with positional due indices to minimize total completion time and maximum cost
• Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines
• Parallel machine scheduling with due date-to-deadline window, order sharing and time value of money
• Pareto‐scheduling with double‐weighted jobs to minimize the weighted number of tardy jobs and total weighted late work
• Single-machine scheduling of multiple projects with controllable processing times
• Single-machine primary-secondary scheduling with total tardiness being the primary criterion
• Minimizing the weighted number of tardy jobs: data-driven heuristic for single-machine scheduling
• Single machine scheduling with few deadlines
• The single-machine preemptive or resumable scheduling with maintenance intervals

This page was built for publication: Unary NP-hardness of minimizing the number of tardy jobs with deadlines

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