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)

• 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
• 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
• Algorithms for some maximization scheduling problems on a single machine
• 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
• Single-machine scheduling against due dates with past-sequence-dependent setup times
• 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
• A bi-objective model for the single-machine scheduling problem with rejection cost and total tardiness minimization
• A branch, bound, and remember algorithm for the \(1|r _{i }|\sum t _{i }\) scheduling problem
• A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times
• Two due date assignment problems in scheduling a single machine
• Some improved algorithms on the single machine hierarchical scheduling with total tardiness as the primary criterion
• Multi-agent scheduling on a single machine with max-form criteria
• The single-machine total tardiness scheduling problem: review and extensions
• Complexity results for flow shop problems with synchronous movement
• Scheduling parallel machines to minimize total weighted and unweighted tardiness
• Single machine scheduling with release times, deadlines and tardiness objectives
• Minimizing tardiness in a two-machine flow-shop
• A tabu search algorithm for the single machine total weighted tardiness problem
• Single machine scheduling problem with a common deadline and resource dependent release dates
• Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach
• Parallel machine scheduling with a common server
• Dynamic scheduling of stochastic jobs on a single machine
• A bicriteria scheduling with sequence-dependent setup times
• A mixed integer formulation and an efficient metaheuristic for the unrelated parallel machine scheduling problem: total tardiness minimization
• A hybrid algorithm for the single-machine total tardiness problem
• Minimizing total tardiness on a single machine with controllable processing times
• A heuristic for the single machine tardiness problem
• Single machine scheduling with rejection and generalized parameters
• 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
• Minimizing total tardiness in permutation flowshops
• An exchange heuristic imbedded with simulated annealing for due-dates job-shop scheduling
• A greedy heuristic for the mean tardiness sequencing problem
• New heuristics for total tardiness minimization in a flexible flowshop
• Scheduling in a sequence dependent setup environment with genetic search
• \(K\)-PPM: a new exact method to solve multi-objective combinatorial optimization problems
• A note on the SPT heuristic for solving scheduling problems with generalized due dates
• Single machine scheduling to minimize total weighted tardiness
• A state-of-the-art review on scheduling with learning effects
• Scheduling continuous casting of aluminum using a multiple objective ant colony optimization metaheuristic
• Multicriteria scheduling
• Match-up scheduling under a machine breakdown
• 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
• On decomposition of the total tardiness problem
• Scheduling aircraft landings using airlines' preferences
• A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times
• Approximation algorithms for minimizing the total weighted tardiness on a single machine
• Algorithms for single machine total tardiness scheduling with sequence dependent setups
• A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs
• 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

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)