Some new efficient methods to solve the \(n/1/r_ i/\sum{}T_ i\) scheduling problem

DOI10.1016/0377-2217(92)90071-GzbMath0760.90055MaRDI QIDQ1197646

Chengbin Chu, Marie-Claude Portmann

Publication date: 16 January 1993

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

zbMATH Keywords

approximate algorithmsone-machine schedulingdominant subset of schedulessufficient condition for local optimalitytotal tardiness minimization

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Dynamic programming and decomposition approaches for the single machine total tardiness problem
• A decomposition algorithm for the single machine total tardiness problem
• A fully polynomial approximation scheme for the total tardiness problem
• Minimizing Total Tardiness on One Machine is NP-Hard
• A dual algorithm for the one-machine scheduling problem
• On general routing problems
• A Survey of Scheduling Rules
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
• A hybrid algorithm for the one machine sequencing problem to minimize total tardiness