Minimizing Total Tardiness on One Machine is NP-Hard

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; zbMATH DE number 4172724
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

Cited in

(only showing first 100 items - show all)

Scheduling orders for multiple product types with due date related objectives
Solution of the single machine total tardiness problem
An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates
The learning effect: getting to the core of the problem
Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming
Nonpreemptive flowshop scheduling with machine dominance
Is a unit-job shop not easier than identical parallel machines?
Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times
A neural network model for scheduling problems
A hybrid algorithm for the single-machine total tardiness problem
On minimizing total tardiness in a serial batching problem
On the complexity of preemptive openshop scheduling problems
Minimizing value-at-risk in single-machine scheduling
Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms
On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation
A special case of the single-machine total tardiness problem is NP-hard
Risk-averse single machine scheduling: complexity and approximation
Minimizing the expected number of tardy jobs when processing times are normally distributed
Evaluation of leading heuristics for the single machine tardiness problem
Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound
Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem
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
Complexity of two dual criteria scheduling problems
Optimizing termination decision for meta-heuristic search techniques that converge to a static objective-value distribution
Improving local search heuristics for some scheduling problems. I
On optimizing a bi-objective flowshop scheduling problem in an uncertain environment
Optimal and heuristic solutions for a scheduling problem arising in a foundry
A note on a single machine scheduling problem with generalized total tardiness objective function
A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines
Minimizing mean tardiness subject to unspecified minimum number tardy for a single machine
Minimizing the bicriteria of makespan and maximum tardiness with an upper bound on maximum tardiness
On the single machine total tardiness problem
Scheduling rules to minimize total tardiness in a parallel machine problem with setup and calendar constraints
Scheduling with time-dependent discrepancy times
A faster fully polynomial approximation scheme for the single-machine total tardiness problem
ILS heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness
Two-agent scheduling of unit processing time jobs to minimize total weighted completion time and total weighted number of tardy jobs
A Bicriteria Scheduling Problem with a Learning Effect: Total Completion Time and Total Tardiness
Minimizing total weighted tardiness for scheduling equal-length jobs on a single machine
Finding the Pareto-optima for the total and maximum tardiness single machine problem
Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times
Parallel machine selection and job scheduling to minimize machine cost and job tardiness
Single machine scheduling with total tardiness criterion and convex controllable processing times
Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria
Scheduling of parallel machines with sequence-dependent batches and product incompatibilities in an automotive glass facility
An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem
Scheduling preemptive open shops to minimize total tardiness
On the complexity of the single machine scheduling problem minimizing total weighted delay penalty
Minimizing total tardiness in a scheduling problem with a learning effect
Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines
Some new efficient methods to solve the \(n/1/r_ i/\sum{}T_ i\) scheduling problem
Scheduling a single machine to minimize a regular objective function under setup constraints
Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints
General stochastic single-machine scheduling with regular cost functions
Distributionally robust single machine scheduling with the total tardiness criterion
Decomposition of the single machine total tardiness problem
Order scheduling in an environment with dedicated resources in parallel
A simulated annealing approach for the one-machine mean tardiness scheduling problem
Rescheduling problems with agreeable job parameters to minimize the tardiness costs under deterioration and disruption
Minimizing Total Tardiness on a Single Machine with Precedence Constraints
A memetic algorithm for the total tardiness single machine scheduling problem
Approximation algorithms for scheduling problems with a modified total weighted tardiness objective
Multicriteria scheduling
Mathematical programming formulations for machine scheduling: A survey
The coordination of scheduling and batch deliveries
Single machine scheduling with release times, deadlines and tardiness objectives
Single machine scheduling with controllable release and processing parameters
A bicriteria scheduling with sequence-dependent setup times
scientific article; zbMATH DE number 4172724 (Why is no real title available?)
Scheduling aircraft landings using airlines' preferences
Single-machine scheduling against due dates with past-sequence-dependent setup times
Approximation algorithms for minimizing the total weighted tardiness on a single machine
Complexity of single machine, multi-criteria scheduling problems
A mixed integer formulation and an efficient metaheuristic for the unrelated parallel machine scheduling problem: total tardiness minimization
An exchange heuristic imbedded with simulated annealing for due-dates job-shop scheduling
Scheduling jobs on parallel machines with sequence-dependent setup times
A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine
Minimizing total tardiness in parallel machine scheduling with setup times: an adaptive memory-based GRASP approach
A general variable neighborhood search algorithm for a parallel-machine scheduling problem considering machine health conditions and preventive maintenance
A note on the SPT heuristic for solving scheduling problems with generalized due dates
Minimizing tardiness in a two-machine flow-shop
A tabu search algorithm for parallel machine total tardiness problem
Multitasking via alternate and shared processing: algorithms and complexity
Minimizing total tardiness in permutation flowshops
A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times
Order acceptance using genetic algorithms
Minimizing total tardiness on a single machine with controllable processing times
Single machine scheduling to minimize total weighted tardiness
A decomposition scheme for single stage scheduling problems
On decomposition of the total tardiness problem
An exact parallel method for a bi-objective permutation flowshop problem
A state-of-the-art review on scheduling with learning effects
A heuristic for the single machine tardiness problem
Improving the anytime behavior of two-phase local search
Single machine group scheduling with family setups to minimize total tardiness
A bicriteria parallel machine scheduling with a learning effect of setup and removal times
Parallel partitioning method (PPM): A new exact method to solve bi-objective problems

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)