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 fully parallel jobs with integer units
Scheduling continuous casting of aluminum using a multiple objective ant colony optimization metaheuristic
On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates
Nonpreemptive flowshop scheduling with machine dominance
Multicriteria scheduling
Manufacturing rescheduling after crisis or disaster-caused supply chain disruption
New formulations and solutions for the strategic berth template problem
Single-machine scheduling with positional deadlines, time deadlines, and due date assignment for minimizing total weighted tardiness
Order acceptance and scheduling with weighted makespan
On minimizing total tardiness in a serial batching problem
Match-up scheduling under a machine breakdown
First-improvement or best-improvement? An in-depth local search computational study to elucidate a dominance claim
Solution of the single machine total tardiness problem
Competitive two-agent scheduling with release dates and preemption on a single machine
Solution of the NP-hard total tardiness minimization problem in scheduling theory
ILS heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness
A general variable neighborhood search algorithm for a parallel-machine scheduling problem considering machine health conditions and preventive maintenance
Minimizing total tardiness in parallel machine scheduling with setup times: an adaptive memory-based GRASP approach
On decomposition of the total tardiness problem
Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness
Modified ATCR rule for fixed and variable costs of tardiness
Scheduling aircraft landings using airlines' preferences
Scheduling rules to minimize total tardiness in a parallel machine problem with setup and calendar constraints
A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times
One-machine sequencing to minimize total tardiness: a fourth theorem for Emmons
A note on a single machine scheduling problem with generalized total tardiness objective function
Approximation algorithms for minimizing the total weighted tardiness on a single machine
General variable neighborhood search for the order batching and sequencing problem
Single machine group scheduling with family setups to minimize total tardiness
A special case of the single-machine total tardiness problem is NP-hard
Single machine scheduling with total tardiness criterion and convex controllable processing times
Scheduling jobs with agreeable processing times and due dates on a single batch processing machine
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
Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times
A survey of scheduling with controllable processing times
A memetic algorithm for the total tardiness single machine scheduling problem
Decomposition of the single machine total tardiness problem
Unary NP-hardness of minimizing total weighted tardiness with generalized due dates
Single machine scheduling with controllable release and processing parameters
Scheduling lower bounds via and subset sum
A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times
A bicriteria parallel machine scheduling with a learning effect of setup and removal 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
Scheduling on parallel identical machines to minimize total tardiness
A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness
A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates
Order acceptance with weighted tardiness
Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools
A theoretical development for the total tardiness problem and its application in branch and bound algorithms
Algorithms for some maximization scheduling problems on a single machine
Due date assignments and scheduling a single machine with a general earliness/tardiness cost function
An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
A state-of-the-art survey on multi-scenario scheduling
Single-machine scheduling against due dates with past-sequence-dependent setup times
Metric approach for finding approximate solutions of scheduling problems
Minsum scheduling with acceptable lead-times and optional job rejection
Scheduling jobs on parallel machines with sequence-dependent setup times
A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times
Order acceptance using genetic algorithms
Scheduling problems with two competing agents to minimize minmax and minsum earliness measures
Just‐in‐time scheduling problem with due windows and release dates for precast bridge girders
A bi-objective model for the single-machine scheduling problem with rejection cost and total tardiness minimization
Discovering heuristics with large language models (LLMs) for mixed-integer programs: single-machine scheduling
Two-agent single machine scheduling with forbidden intervals
Just-in-time scheduling for a distributed concrete precast flow shop system
A branch, bound, and remember algorithm for the \(1|r _{i }|\sum t _{i }\) scheduling problem
On minimizing the sum of k tardinesses
Merging nodes in search trees: an exact exponential algorithm for the single machine total tardiness scheduling problem
Two due date assignment problems in scheduling a single machine
Improving local search heuristics for some scheduling problems. I
A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times
Scheduling a single machine to minimize a regular objective function under setup constraints
A hybrid metaheuristic for the single-machine total weighted tardiness problem
Multi-agent scheduling on a single machine with max-form criteria
On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation
Some improved algorithms on the single machine hierarchical scheduling with total tardiness as the primary criterion
Optimization of departure runway scheduling incorporating arrival crossings
Minimizing tardiness scheduling measures with generalized due-dates and a maintenance activity
A review of four decades of time-dependent scheduling: main results, new topics, and open problems
Complexity results for flow shop problems with synchronous movement
The single-machine total tardiness scheduling problem: review and extensions
A note on the equivalence of two heuristics to minimize total tardiness
Scheduling parallel machines to minimize total weighted and unweighted tardiness
New results for scheduling to minimize tardiness on one machine with rejection and related problems
The learning effect: getting to the core of the problem
Single machine scheduling problem with a common deadline and resource dependent release dates
A tabu search algorithm for the single machine total weighted tardiness problem
Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach
Improved estimation of distribution algorithm for the problem of single-machine scheduling with deteriorating jobs and different due dates
Parallel machine scheduling with a common server
Single-machine scheduling to minimize the total earliness and tardiness is strongly NP-hard
Single machine scheduling with release times, deadlines and tardiness objectives
Dynamic scheduling of stochastic jobs on a single machine
Minimizing tardiness in a two-machine flow-shop
A hybrid algorithm for the single-machine total tardiness problem
Minimizing total tardiness on a single machine with controllable processing times

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)