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)

Order acceptance using genetic algorithms
Minimizing total tardiness on a single machine with controllable processing times
A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times
Heuristic factory planning algorithm for advanced planning and scheduling
Scheduling jobs with agreeable processing times and due dates on a single batch processing machine
Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness
The single-machine total tardiness scheduling problem: review and extensions
A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines
Minimizing total tardiness in permutation flowshops
On the complexity of generalized due date scheduling problems
On minimizing the sum of k tardinesses
Single machine scheduling problem with a common deadline and resource dependent release dates
Some new efficient methods to solve the \(n/1/r_ i/\sum{}T_ i\) scheduling problem
A guaranteed accuracy shifting bottleneck algorithm for the two-machine flowshop total tardiness problem
Minimizing mean tardiness subject to unspecified minimum number tardy for a single machine
A neural network model for scheduling problems
A simulated annealing approach for the one-machine mean tardiness scheduling problem
Scheduling jobs on parallel machines with sequence-dependent setup times
An exchange heuristic imbedded with simulated annealing for due-dates job-shop scheduling
A note on the equivalence of two heuristics to minimize total tardiness
Evaluation of leading heuristics for the single machine tardiness problem
Complexity of single machine, multi-criteria scheduling problems
A heuristic for the single machine tardiness problem
A greedy heuristic for the mean tardiness sequencing problem
On the complexity of preemptive openshop scheduling problems
Scheduling in a sequence dependent setup environment with genetic search
Decomposition of the single machine total tardiness problem
Scheduling parallel machines to minimize total weighted and unweighted tardiness
General stochastic single-machine scheduling with regular cost functions
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
An efficient tabu search approach for the two-machine preemptive open shop scheduling problem.
A note on the SPT heuristic for solving scheduling problems with generalized due dates
Parallel machine scheduling with a common server
Solution of the single machine total tardiness problem
Dynamic scheduling of stochastic jobs on a single machine
Nonpreemptive flowshop scheduling with machine dominance
Minimizing the expected number of tardy jobs when processing times are normally distributed
Distributionally robust single machine scheduling with the total tardiness criterion
A bi-objective model for the single-machine scheduling problem with rejection cost and total tardiness minimization
A mathematical model and heuristic algorithms for an unrelated parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and a common server
An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem
General variable neighborhood search for the order batching and sequencing problem
Scheduling with time-dependent discrepancy times
Minimizing the number of late jobs when the start time of the machine is variable
A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times
Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
Scheduling rules to minimize total tardiness in a parallel machine problem with setup and calendar constraints
A cooperative dispatching approach for minimizing mean tardiness in a dynamic flowshop
A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine
A tabu search algorithm for parallel machine total tardiness problem
Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria
A possibilistic approach to sequencing problems with fuzzy parameters
On the single machine total tardiness problem
Single machine scheduling to minimize total weighted tardiness
Optimal and heuristic solutions for a scheduling problem arising in a foundry
Scheduling a single machine to minimize a regular objective function under setup constraints
On the complexity of the single machine scheduling problem minimizing total weighted delay penalty
Unary NP-hardness of minimizing total weighted tardiness with generalized due dates
An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
Match-up scheduling under a machine breakdown
Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound
Scheduling continuous casting of aluminum using a multiple objective ant colony optimization metaheuristic
Finding the Pareto-optima for the total and maximum tardiness single machine problem
A heuristic approach for minimizing weighted tardiness and overtime costs in single resource scheduling
Scheduling two-machine preemptive open shops to minimize total completion time
Improving local search heuristics for some scheduling problems. I
On decomposition of the total tardiness problem
A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times
A special case of the single-machine total tardiness problem is NP-hard
New heuristics for total tardiness minimization in a flexible flowshop
Minimizing functions of infeasibilities in a two-machine flow shop
Minimizing delays in a shunting yard
Metaheuristics for a scheduling problem with rejection and tardiness penalties
\textit{Branch} \& \textit{memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees
Two-agent scheduling of unit processing time jobs to minimize total weighted completion time and total weighted number of tardy jobs
Minimizing total late work on a single machine with generalized due-dates
Large-scale storage/retrieval requests sorting algorithm for multi-I/O depots automated storage/retrieval systems
Metric approach for finding approximate solutions of scheduling problems
New results for scheduling to minimize tardiness on one machine with rejection and related problems
Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates
Mirror scheduling problems with early work and late work criteria
New formulations and solutions for the strategic berth template problem
On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates
A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
Modeling and solving the waste valorization production and distribution scheduling problem
Minsum scheduling with acceptable lead-times and optional job rejection
Scheduling lower bounds via AND subset sum
Optimizing termination decision for meta-heuristic search techniques that converge to a static objective-value distribution
Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times
A general variable neighborhood search algorithm for a parallel-machine scheduling problem considering machine health conditions and preventive maintenance
Single machine scheduling with rejection and generalized parameters
Risk-averse single machine scheduling: complexity and approximation
Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines
Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints
A review of four decades of time-dependent scheduling: main results, new topics, and open problems
Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty
A metric for total tardiness minimization
Approximation algorithms for minimizing the total weighted tardiness on a single machine
Minimizing total tardiness in parallel machine scheduling with setup times: an adaptive memory-based GRASP approach

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)