An algorithm for single machine sequencing with deadlines to minimize total weighted completion time

DOI10.1016/0377-2217(83)90159-5zbMath0496.90048MaRDI QIDQ1170111

Luk N. Van Wassenhove, Chris N. Potts

Publication date: 1983

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

Full work available at URL: https://doi.org/10.1016/0377-2217(83)90159-5

zbMATH Keywords

Lagrangean relaxation; lower bounds; heuristic; deadlines; optimal solution; branch and bound algorithm; computational experience; dominance conditions; n jobs; minimization of total weighted completion time; multiplier adjustment method; processing without interruption; single machine sequencing

Mathematics Subject Classification ID

65K10: Numerical optimization and variational techniques

90B35: Deterministic scheduling theory in operations research

Related Items

Exact algorithms for single-machine scheduling with time windows and precedence constraints, A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem, Formulating the single machine sequencing problem with release dates as a mixed integer program, Reducibility among single machine weighted completion time scheduling problems, A time indexed formulation of non-preemptive single machine scheduling problems, Single machine earliness and tardiness scheduling, A branch and bound algorithm for the two-stage assembly scheduling problem, Scheduling identical parallel machines to minimize total weighted completion time, An improved branch and bound algorithm for single machine scheduling with deadlines to minimize total weighted completion time., Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates, Scheduling unit processing time jobs on a single machine with multiple criteria, \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees, Pareto optima for total weighted completion time and maximum lateness on a single machine, On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems, A branch and bound algorithm for minimizing weighted completion times with deadlines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Single machine scheduling to minimize weighted sum of completion times with secondary criterion - A branch and bound approach
• An algorithm for single machine sequencing with release dates to minimize total weighted completion time
• ONE MACHINE SCHEDULING PROBLEM WITH DUAL CRITERIA
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• A note on a scheduling problem with dual criteria
• Minimizing Total Costs in One-Machine Scheduling
• Scheduling to minimize the weighted sum of completion times with secondary criteria
• A note on the extension of a result on scheduling with secondary criteria