Some new efficient methods to solve the n/1/r_ i/T_ i scheduling problem

DOI10.1016/0377-2217(92)90071-GMaRDI QIDQ1197646zbMATH OpenFDO

Authors Chengbin Chu, Marie-Claude Portmann

Publication date 16 January 1993

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(92)90071-G

zbMATH Keywords

approximate algorithmsdominant subset of schedulesone-machine schedulingsufficient condition for local optimalitytotal tardiness minimization

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Solution of the NP-hard total tardiness minimization problem in scheduling theory
• A greedy algorithm for the solution of the classical NP-hard scheduling problem of minimizing the total delay
• scientific article; zbMATH DE number 4031379
• A general scheme for solving an NP-hard problem in the strong sense of the scheduling theory
• About one algorithm for solving scheduling problem

Cites work

• A decomposition algorithm for the single machine total tardiness problem
• A dual algorithm for the one-machine scheduling problem
• A fully polynomial approximation scheme for the total tardiness problem
• A hybrid algorithm for the one machine sequencing problem to minimize total tardiness
• A Survey of Scheduling Rules
• Dynamic programming and decomposition approaches for the single machine total tardiness problem
• scientific article; zbMATH DE number 3550186 (Why is no real title available?)
• scientific article; zbMATH DE number 2146482 (Why is no real title available?)
• Minimizing Total Tardiness on One Machine is NP-Hard
• On general routing problems
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness

Cited in

(12)

• Scheduling a single machine to minimize a regular objective function under setup constraints
• New heuristics for total tardiness minimization in a flexible flowshop
• Dominance-based heuristics for one-machine total cost scheduling problems
• Minimizing total tardiness on a single machine with unequal release dates
• Permutation flow shop scheduling with earliness and tardiness penalties
• An investigation on a two-agent single-machine scheduling problem with unequal release dates
• Dominance rules in combinatorial optimization problems
• A branch-and-bound algorithm for a single machine sequencing to minimize the total tardiness with arbitrary release dates and position-dependent learning effects
• A new dominance rule to minimize total weighted tardiness with unequal release dates.
• A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates
• Dominance rules for the parallel machine total weighted tardiness scheduling problem with release dates
• A branch, bound, and remember algorithm for the \(1|r _{i }|\sum t _{i }\) scheduling problem

This page was built for publication: Some new efficient methods to solve the \(n/1/r_ i/\sum{}T_ i\) scheduling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1197646)