Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates

DOI10.1016/j.cor.2011.05.024zbMath1251.90173MaRDI QIDQ1761994

Imed Kacem, Rabia Nessah

Publication date: 15 November 2012

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2011.05.024

zbMATH Keywords

scheduling; single machine; splitting; lower bounds; release dates; total weighted completion time

Mathematics Subject Classification ID

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90B35: Deterministic scheduling theory in operations research

90C27: Combinatorial optimization

Related Items

Exact algorithms for single-machine scheduling with time windows and precedence constraints, A hybrid differential evolution approach based on surrogate modelling for scheduling bottleneck stages, Minimizing the makespan on a single machine with flexible maintenances and jobs' release dates, A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems, Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Formulating the single machine sequencing problem with release dates as a mixed integer program
• An algorithm for single machine sequencing with deadlines to minimize total weighted completion time
• An algorithm for single machine sequencing with release dates to minimize total weighted completion time
• Scheduling with release dates on a single machine to minimize total weighted completion time
• A 1. 47-approximation for a preemptive single-machine scheduling problem
• Dominance-based heuristics for one-machine total cost scheduling problems
• Scheduling of a single machine to minimize total weighted completion time subject to release dates
• Minimizing Weighted Completion Times with Deadlines
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline