A decomposition algorithm for the single machine total tardiness problem

From MaRDI portal

Publication:1838424

Jump to:navigation, search

DOI10.1016/0167-6377(82)90035-9zbMath0508.90045OpenAlexW2036912539MaRDI QIDQ1838424

Chris N. Potts, Luk N. Van Wassenhove

Publication date: 1982

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(82)90035-9

zbMATH Keywords

algorithm decomposition job sequencing single machine dominance computational experience minimization of total tardiness

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items

Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs ⋮ A dynamic programming method for single machine scheduling ⋮ One machine scheduling to minimize expected mean tardiness. II ⋮ The stochastic single machine scheduling problem with earliness and tardiness costs ⋮ Preemption in single machine earliness/tardiness scheduling ⋮ A bicriterion scheduling problem involving total flowtime and total tardiness ⋮ Dynamic programming and decomposition approaches for the single machine total tardiness problem ⋮ A branch, bound, and remember algorithm for the \(1|r _{i }|\sum t _{i }\) scheduling problem ⋮ Improving the performance of enumerative search methods. I: Exploiting structure and intelligence ⋮ Scheduling identical jobs on uniform parallel machines under position-based learning effects ⋮ Using two-machine flowshop with maximum lateness objective to model multimedia data objects scheduling problem for WWW applications ⋮ A general variable neighborhood search algorithm for a parallel-machine scheduling problem considering machine health conditions and preventive maintenance ⋮ Matheuristics for the flowshop scheduling problem with controllable processing times and limited resource consumption to minimize total tardiness ⋮ Some remarks on the decomposition properties of the single machine total tardiness problem ⋮ NEH-based heuristics for the permutation flowshop scheduling problem to minimise total tardiness ⋮ A branch and bound algorithm to minimize the total tardiness for \(m\)-machine permutation flowshop problems ⋮ Iterated search methods for earliness and tardiness minimization in hybrid flowshops with due windows ⋮ A theoretical development for the total tardiness problem and its application in branch and bound algorithms ⋮ An investigation on a two-agent single-machine scheduling problem with unequal release dates ⋮ Decomposition of the single machine total tardiness problem ⋮ Efficient constructive and composite heuristics for the permutation flowshop to minimise total earliness and tardiness ⋮ Scheduling parallel machines to minimize total weighted and unweighted tardiness ⋮ The two-machine flowshop scheduling problem with total tardiness ⋮ A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates ⋮ The proportionate flow shop total tardiness problem ⋮ Minimizing total tardiness in permutation flowshops ⋮ 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 ⋮ Algorithms for some maximization scheduling problems on a single machine ⋮ A review and classification on distributed permutation flowshop scheduling problems ⋮ Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems ⋮ A mixed integer formulation and an efficient metaheuristic for the unrelated parallel machine scheduling problem: total tardiness minimization ⋮ Scheduling Unrelated Parallel Machines with Sequence Dependent Setup Times and Weighted Earliness–Tardiness Minimization ⋮ Mixed-Integer Programming Models for Flowshop Scheduling Problems Minimizing the Total Earliness and Tardiness ⋮ A special case of the single-machine total tardiness problem is NP-hard ⋮ New heuristics for total tardiness minimization in a flexible flowshop ⋮ A controlled search simulated annealing method for the single machine weighted tardiness problem ⋮ On the complexity of dynamic programming for sequencing problems with precedence constraints ⋮ Reducibility among single machine weighted completion time scheduling problems ⋮ A branch and bound approach for single machine scheduling with earliness and tardiness penalties ⋮ Two-machine flowshop scheduling to minimize total tardiness ⋮ Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem ⋮ Minimizing total tardiness on a single machine with unequal release dates ⋮ Minimising total tardiness in the \(m\)-machine flowshop problem: A review and evaluation of heuristics and metaheuristics ⋮ A branch-and-bound algorithm for a single machine sequencing to minimize the total tardiness with arbitrary release dates and position-dependent learning effects ⋮ Minimizing total tardiness in a scheduling problem with a learning effect ⋮ 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 ⋮ Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one ⋮ A due date-based approach to part type selection in flexible manufacturing systems ⋮ Algorithmic paradoxes of the single-machine total tardiness problem ⋮ Single machine scheduling problems with financial resource constraints: some complexity results and properties ⋮ Accelerated tabu search for no-wait flowshop scheduling problem with maximum lateness criterion ⋮ Optimal and heuristic solutions for a scheduling problem arising in a foundry ⋮ Single machine scheduling with release times, deadlines and tardiness objectives ⋮ On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation ⋮ Flow shop scheduling problem with position-dependent processing times ⋮ Scheduling a single machine to minimize a regular objective function under setup constraints ⋮ New heuristics for no-wait flow shops with a linear combination of makespan and maximum lateness ⋮ The application of genetic algorithms to lot streaming in a job-shop scheduling problem ⋮ Single machine scheduling with nonlinear cost functions ⋮ Algorithms for a class of single-machine weighted tardiness and earliness problems ⋮ \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees ⋮ An exact exponential branch-and-merge algorithm for the single machine total tardiness problem ⋮ Coupled task scheduling with exact delays: literature review and models ⋮ Minimizing tardiness in a two-machine flow-shop ⋮ Fast LP models and algorithms for identical jobs on uniform parallel machines ⋮ Generalised accelerations for insertion-based heuristics in permutation flowshop scheduling ⋮ Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty ⋮ Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem ⋮ A new branch and bound algorithm for minimizing mean tardiness in two- machine flowshops ⋮ A guaranteed accuracy shifting bottleneck algorithm for the two-machine flowshop total tardiness problem ⋮ A simulated annealing approach for the one-machine mean tardiness scheduling problem ⋮ The use of dynamic programming in genetic algorithms for permutation problems ⋮ Simulation Optimization for MRO Systems Operations ⋮ Scheduling jobs on parallel machines with sequence-dependent setup times ⋮ Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process ⋮ 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 ⋮ Single machine earliness and tardiness scheduling ⋮ The single-machine total tardiness scheduling problem: review and extensions ⋮ A branch and bound procedure to minimize mean absolute lateness on a single processor ⋮ Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem ⋮ Genetic local search for multi-objective flowshop scheduling problems ⋮ Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties ⋮ Empirically discovering dominance relations for scheduling problems using an evolutionary algorithm ⋮ Solution of the single machine total tardiness problem ⋮ A heuristic for single machine scheduling with early and tardy costs ⋮ A heuristic for the single machine tardiness problem ⋮ A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems ⋮ Unrelated parallel machine scheduling with eligibility constraints and delivery times to minimize total weighted tardiness ⋮ A greedy heuristic for the mean tardiness sequencing problem ⋮ One-Machine Sequencing to Minimize Total Tardiness: A Fourth Theorem for Emmons

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1838424&oldid=14209998"