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

DOI10.1016/0377-2217(83)90159-5zbMath0496.90048OpenAlexW2058591900MaRDI 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 relaxationlower boundsheuristicdeadlinesoptimal solutionbranch and bound algorithmcomputational experiencedominance conditionsn jobsminimization of total weighted completion timemultiplier adjustment methodprocessing without interruptionsingle machine sequencing

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Deterministic scheduling theory in operations research (90B35)

Related Items

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

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