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

DOI10.1007/s10951-016-0479-8zbMath1373.90065OpenAlexW2341012368MaRDI QIDQ2398650

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

schedulingNP-harddeadlinesnumber of tardy jobs

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 (11)

Pareto-scheduling with family jobs or ND-agent on a parallel-batch machine to minimize the makespan and maximum cost ⋮ Pareto‐scheduling with double‐weighted jobs to minimize the weighted number of tardy jobs and total weighted late work ⋮ Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices ⋮ Single-machine scheduling of multiple projects with controllable processing times ⋮ 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 ⋮ A note on competing-agent Pareto-scheduling ⋮ Single-machine scheduling with positional due indices and positional deadlines ⋮ 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

Cites Work

• Unnamed Item
• A survey of single machine scheduling to minimize weighted number of tardy jobs
• Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness
• The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard
• Sequencing a single machine with due dates and deadlines: An ILP-based approach to solve very large instances
• A note on the single machine scheduling to minimize the number of tardy jobs with deadlines
• A multiple-criterion model for machine scheduling
• The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard
• Scheduling Problems with Two Competing Agents
• Single Machine Scheduling with Deadlines to Minimize the Weighted Number of Tardy Jobs
• Multiagent Scheduling
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs

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