Minimizing Total Tardiness on One Machine is NP-Hard

DOI10.1287/MOOR.15.3.483zbMATH Open0714.90052OpenAlexW2030250600MaRDI QIDQ3200872FDOQ3200872

Authors: Jian-Zhong Du, Joseph Y.-T. Leung 

Publication date: 1990

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.15.3.483

Recommendations

• Solution of the NP-hard total tardiness minimization problem in scheduling theory
• Minimizing Total Tardiness on a Single Machine with Precedence Constraints
• scientific article
• A special case of the single-machine total tardiness problem is NP-hard
• Unary NP-hardness of minimizing total weighted tardiness with generalized due dates

zbMATH Keywords

due datestotal tardinessone-machine scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Cited In (only showing first 100 items - show all)

• Metaheuristics for a scheduling problem with rejection and tardiness penalties
• A note on reverse scheduling with maximum lateness objective
• Production scheduling in a market-driven foundry: a mathematical programming approach versus a project scheduling metaheuristic algorithm
• Minimizing value-at-risk in single-machine scheduling
• Minimizing mean tardiness subject to unspecified minimum number tardy for a single machine
• Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines
• Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming
• Scheduling with time-dependent discrepancy times
• Parallel machine selection and job scheduling to minimize machine cost and job tardiness
• An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem
• Minimizing the expected number of tardy jobs when processing times are normally distributed
• A Bicriteria Scheduling Problem with a Learning Effect: Total Completion Time and Total Tardiness
• Finding the Pareto-optima for the total and maximum tardiness single machine problem
• Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria
• Scheduling orders for multiple product types with due date related objectives
• Scheduling preemptive open shops to minimize total tardiness
• Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound
• General stochastic single-machine scheduling with regular cost functions
• An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates
• On the complexity of preemptive openshop scheduling problems
• Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem
• Two-agent scheduling of unit processing time jobs to minimize total weighted completion time and total weighted number of tardy jobs
• Minimizing total tardiness in a scheduling problem with a learning effect
• Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints
• Distributionally robust single machine scheduling with the total tardiness criterion
• Evaluation of leading heuristics for the single machine tardiness problem
• Optimal and heuristic solutions for a scheduling problem arising in a foundry
• A simulated annealing approach for the one-machine mean tardiness scheduling problem
• Is a unit-job shop not easier than identical parallel machines?
• Risk-averse single machine scheduling: complexity and approximation
• Complexity of two dual criteria scheduling problems
• On the complexity of the single machine scheduling problem minimizing total weighted delay penalty
• On the single machine total tardiness problem
• A neural network model for scheduling problems
• Optimizing termination decision for meta-heuristic search techniques that converge to a static objective-value distribution
• A faster fully polynomial approximation scheme for the single-machine total tardiness problem
• Rescheduling problems with agreeable job parameters to minimize the tardiness costs under deterioration and disruption
• A special case of the single-machine total tardiness problem is NP-hard
• Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times
• Single machine scheduling with total tardiness criterion and convex controllable processing times
• Decomposition of the single machine total tardiness problem
• A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times
• A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines
• Minimizing total weighted tardiness for scheduling equal-length jobs on a single machine
• On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation
• Improving local search heuristics for some scheduling problems. I
• Scheduling a single machine to minimize a regular objective function under setup constraints
• The learning effect: getting to the core of the problem
• A hybrid algorithm for the single-machine total tardiness problem
• Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms
• Scheduling of parallel machines with sequence-dependent batches and product incompatibilities in an automotive glass facility
• On optimizing a bi-objective flowshop scheduling problem in an uncertain environment
• Order scheduling in an environment with dedicated resources in parallel
• Minimizing the bicriteria of makespan and maximum tardiness with an upper bound on maximum tardiness
• Minimizing Total Tardiness on a Single Machine with Precedence Constraints
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• Some new efficient methods to solve the \(n/1/r_ i/\sum{}T_ i\) scheduling problem
• Nonpreemptive flowshop scheduling with machine dominance
• On minimizing total tardiness in a serial batching problem
• Solution of the single machine total tardiness problem
• ILS heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness
• Scheduling rules to minimize total tardiness in a parallel machine problem with setup and calendar constraints
• A note on a single machine scheduling problem with generalized total tardiness objective function
• Approximation algorithms for scheduling problems with a modified total weighted tardiness objective
• Minimizing total tardiness on parallel machines with preemptions
• Single machine scheduling problems with financial resource constraints: some complexity results and properties
• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• Multitasking via alternate and shared processing: algorithms and complexity
• Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs
• Single-machine scheduling under the job rejection constraint
• Parallel partitioning method (PPM): A new exact method to solve bi-objective problems
• A hybrid TP+PLS algorithm for bi-objective flow-shop scheduling problems
• Title not available (Why is that?)
• The complexity of scheduling starting time dependent tasks with release times
• Mathematical programming formulations for machine scheduling: A survey
• The coordination of scheduling and batch deliveries
• An exact parallel method for a bi-objective permutation flowshop problem
• Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
• A decomposition scheme for single stage scheduling problems
• A genetic algorithm methodology for complex scheduling problems
• Complexity of single machine, multi-criteria scheduling problems
• Fabrication scheduling on a single machine with due date constraints
• Scheduling identical parallel machines with fixed delivery dates to minimize total tardiness
• A note on scheduling problems with competing agents and earliness minimization objectives
• Optimal due date assignment in multi-machine scheduling environments
• Single machine group scheduling with family setups to minimize total tardiness
• Improving the anytime behavior of two-phase local search
• Permutation flow shop scheduling with order acceptance and weighted tardiness
• Minimising total tardiness in the \(m\)-machine flowshop problem: A review and evaluation of heuristics and metaheuristics
• A GRASP based on DE to solve single machine scheduling problem with SDST
• A parallel multiple reference point approach for multi-objective optimization
• A memetic algorithm for the total tardiness single machine scheduling problem
• A survey of scheduling with controllable processing times
• Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints
• Optimal restricted due date assignment in scheduling
• A survey on single crane scheduling in automated storage/retrieval systems
• On the complexity of generalized due date scheduling problems
• Single machine scheduling with controllable release and processing parameters
• A bicriteria parallel machine scheduling with a learning effect of setup and removal times
• Due date assignments and scheduling a single machine with a general earliness/tardiness cost function

This page was built for publication: Minimizing Total Tardiness on One Machine is NP-Hard

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