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
Minsum scheduling with acceptable lead-times and optional job rejection, Scheduling lower bounds via AND subset sum, A metric for total tardiness minimization, Optimizing termination decision for meta-heuristic search techniques that converge to a static objective-value distribution, SOME GENERAL PROPERTIES OF A FUZZY SINGLE MACHINE SCHEDULING PROBLEM, 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, 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, Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times, \(K\)-PPM: a new exact method to solve multi-objective combinatorial optimization problems, The learning effect: getting to the core of the problem, A survey of scheduling with controllable processing 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, Parallel machine selection and job scheduling to minimize machine cost and job tardiness, Complexity of two dual criteria scheduling problems, An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates, Improving local search heuristics for some scheduling problems. I, On decomposition of the total tardiness problem, Just-in-time scheduling for a distributed concrete precast flow shop system, A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times, Optimization of departure runway scheduling incorporating arrival crossings, A Bicriteria Scheduling Problem with a Learning Effect: Total Completion Time and Total Tardiness, Manufacturing rescheduling after crisis or disaster-caused supply chain disruption, Minimizing tardiness scheduling measures with generalized due-dates and a maintenance activity, A state-of-the-art survey on multi-scenario scheduling, A special case of the single-machine total tardiness problem is NP-hard, New heuristics for total tardiness minimization in a flexible flowshop, Scheduling with time-dependent discrepancy times, Algorithms for single machine total tardiness scheduling with sequence dependent setups, Single machine scheduling with controllable release and processing parameters, Minimizing total tardiness on parallel machines with preemptions, A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs, Single machine group scheduling with family setups to minimize total tardiness, Minimizing functions of infeasibilities in a two-machine flow shop, Due date assignments and scheduling a single machine with a general earliness/tardiness cost function, Approximation algorithms for scheduling problems with a modified total weighted tardiness objective, Minimizing total tardiness in a scheduling problem with a learning effect, A state-of-the-art review on scheduling with learning effects, Multi-agent scheduling on a single machine with max-form criteria, Minimizing the number of late jobs when the start time of the machine is variable, Sequencing jobs on a single machine: A neural network approach, A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times, Scheduling aircraft landings using airlines' preferences, 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, On Minimizing Total Tardiness in a Serial Batching Problem, A tabu search algorithm for parallel machine total tardiness problem, Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria, A memetic algorithm for the total tardiness single machine scheduling problem, 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, Minimizing delays in a shunting yard, Single machine scheduling with release times, deadlines and tardiness objectives, Metaheuristics for a scheduling problem with rejection and tardiness penalties, On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation, A genetic algorithm methodology for complex scheduling problems, Scheduling a single machine to minimize a regular objective function under setup constraints, \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees, A HYBRID METAHEURISTIC FOR THE SINGLE-MACHINE TOTAL WEIGHTED TARDINESS PROBLEM, Fabrication scheduling on a single machine with due date 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, Two-agent scheduling of unit processing time jobs to minimize total weighted completion time and total weighted number of tardy jobs, A bicriteria scheduling with sequence-dependent setup times, An exact exponential branch-and-merge algorithm for the single machine total tardiness problem, Minimizing total late work on a single machine with generalized due-dates, Minimizing tardiness in a two-machine flow-shop, Risk-averse single machine scheduling: complexity and approximation, Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines, Improved estimation of distribution algorithm for the problem of single-machine scheduling with deteriorating jobs and different due dates, SOME IMPROVED ALGORITHMS ON THE SINGLE MACHINE HIERARCHICAL SCHEDULING WITH TOTAL TARDINESS AS THE PRIMARY CRITERION, Large-scale storage/retrieval requests sorting algorithm for multi-I/O depots automated storage/retrieval systems, A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times, Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints, Metric approach for finding approximate solutions of scheduling problems, Match-up scheduling under a machine breakdown, A review of four decades of time-dependent scheduling: main results, new topics, and open 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, Unnamed Item, New formulations and solutions for the strategic berth template problem, Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem, Multicriteria scheduling, Scheduling orders for multiple product types with due date related objectives, Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound, Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty, On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates, 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 classification of dynamic programming formulations for offline deterministic single-machine scheduling problems, Modeling and solving the waste valorization production and distribution scheduling problem, One-Machine Sequencing to Minimize Total Tardiness: A Fourth Theorem for Emmons, A mixed integer formulation and an efficient metaheuristic for the unrelated parallel machine scheduling problem: total tardiness minimization, Competitive two-agent scheduling with release dates and preemption on a single machine, Hybrid evolutionary algorithm with optimized operators for total weighted tardiness problem, Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness, The parcel hub scheduling problem with limited conveyor capacity and controllable unloading speeds, Order acceptance and scheduling with delivery under generalized parameters, Just‐in‐time scheduling problem with due windows and release dates for precast bridge girders, 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
