Minimizing Total Tardiness on One Machine is NP-Hard
From MaRDI portal
Publication:3200872
DOI10.1287/moor.15.3.483zbMath0714.90052OpenAlexW2030250600MaRDI QIDQ3200872
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
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)
Related Items (only showing first 100 items - show all)
On the complexity of preemptive openshop scheduling problems ⋮ Minimizing total weighted tardiness for scheduling equal-length jobs on a single machine ⋮ Multitasking via alternate and shared processing: algorithms and complexity ⋮ 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 ⋮ The complexity of scheduling starting time dependent tasks with release times ⋮ Optimal due date assignment in multi-machine scheduling environments ⋮ Scheduling in a sequence dependent setup environment with genetic search ⋮ A bicriteria parallel machine scheduling with a learning effect of setup and removal times ⋮ 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 ⋮ A branch, bound, and remember algorithm for the \(1|r _{i }|\sum t _{i }\) scheduling problem ⋮ Scheduling identical parallel machines with fixed delivery dates to minimize total tardiness ⋮ A note on scheduling problems with competing agents and earliness minimization objectives ⋮ 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 ⋮ A tabu search algorithm for the single machine total weighted tardiness problem ⋮ Scheduling on parallel identical machines to minimize total tardiness ⋮ An exact parallel method for a bi-objective permutation flowshop problem ⋮ Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools ⋮ An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem ⋮ A theoretical development for the total tardiness problem and its application in branch and bound algorithms ⋮ Decomposition of the single machine total tardiness problem ⋮ A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date ⋮ A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness ⋮ Scheduling parallel machines to minimize total weighted and unweighted tardiness ⋮ On optimizing a bi-objective flowshop scheduling problem in an uncertain environment ⋮ Two due date assignment problems in scheduling a single machine ⋮ Parallel partitioning method (PPM): A new exact method to solve bi-objective problems ⋮ A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates ⋮ Order acceptance with weighted tardiness ⋮ General stochastic single-machine scheduling with regular cost functions ⋮ Order scheduling in an environment with dedicated resources in parallel ⋮ Minimizing total tardiness in permutation flowshops ⋮ Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach ⋮ Algorithms for some maximization scheduling problems on a single machine ⋮ Is a unit-job shop not easier than identical parallel machines? ⋮ 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 ⋮ Improving the anytime behavior of two-phase local search ⋮ Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity ⋮ General variable neighborhood search for the order batching and sequencing problem ⋮ Permutation flow shop scheduling with order acceptance and weighted tardiness ⋮ Two-agent single machine scheduling with forbidden intervals ⋮ A hybrid TP+PLS algorithm for bi-objective flow-shop scheduling problems ⋮ Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming ⋮ Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs ⋮ A GRASP based on DE to solve single machine scheduling problem with SDST ⋮ Single machine scheduling with total tardiness criterion and convex controllable processing times ⋮ An efficient tabu search approach for the two-machine preemptive open shop scheduling problem. ⋮ Rescheduling problems with agreeable job parameters to minimize the tardiness costs under deterioration and disruption ⋮ A note on the SPT heuristic for solving scheduling problems with generalized due dates ⋮ On the complexity of generalized due date scheduling problems ⋮ Single-machine scheduling against due dates with past-sequence-dependent setup times ⋮ On minimizing the sum of \(k\) tardinesses ⋮ Single machine scheduling problem with a common deadline and resource dependent release dates ⋮ Scheduling of parallel machines with sequence-dependent batches and product incompatibilities in an automotive glass facility ⋮ Minimising total tardiness in the \(m\)-machine flowshop problem: A review and evaluation of heuristics and metaheuristics ⋮ ILS heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness ⋮ Minimizing value-at-risk in single-machine scheduling ⋮ A hybrid algorithm for the single-machine total tardiness problem ⋮ Some new efficient methods to solve the \(n/1/r_ i/\sum{}T_ i\) scheduling problem ⋮ A faster fully polynomial approximation scheme for the single-machine total tardiness problem ⋮ Minimizing the bicriteria of makespan and maximum tardiness with an upper bound on maximum tardiness ⋮ Single-machine scheduling under the job rejection constraint ⋮ Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms ⋮ Single machine scheduling problems with financial resource constraints: some complexity results and properties ⋮ Scheduling preemptive open shops to minimize total tardiness ⋮ A parallel multiple reference point approach for multi-objective optimization ⋮ Scheduling problems with two competing agents to minimize minmax and minsum earliness measures ⋮ A decomposition scheme for single stage scheduling problems ⋮ Complexity results for flow shop problems with synchronous movement ⋮ 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 ⋮ Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem ⋮ Heuristic factory planning algorithm for advanced planning and scheduling ⋮ 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 with agreeable processing times and due dates on a single batch processing machine ⋮ 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 a single machine scheduling problem with generalized total tardiness objective function ⋮ A note on the equivalence of two heuristics to minimize total tardiness ⋮ Evaluation of leading heuristics for the single machine tardiness problem ⋮ Parallel machine scheduling with a common server ⋮ 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 ⋮ Solution of the single machine total tardiness problem ⋮ Complexity of single machine, multi-criteria scheduling problems ⋮ A heuristic for the single machine tardiness problem ⋮ Dynamic scheduling of stochastic jobs on a single machine ⋮ A greedy heuristic for the mean tardiness sequencing problem ⋮ Nonpreemptive flowshop scheduling with machine dominance ⋮ Mathematical programming formulations for machine scheduling: A survey ⋮ The coordination of scheduling and batch deliveries ⋮ Minimizing the expected number of tardy jobs when processing times are normally distributed
This page was built for publication: Minimizing Total Tardiness on One Machine is NP-Hard
