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.90173OpenAlexW2163689386MaRDI 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

schedulingsingle machinesplittinglower boundsrelease datestotal weighted completion time

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items (7)

Exact algorithms for single-machine scheduling with time windows and precedence constraints ⋮ Minimizing the makespan on a single machine with flexible maintenances and jobs' release dates ⋮ A hybrid differential evolution approach based on surrogate modelling for scheduling bottleneck stages ⋮ Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time ⋮ An exact dynamic programming algorithm for the precedence-constrained class sequencing problem ⋮ A makespan minimization problem for versatile developers in the game industry ⋮ A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems

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

This page was built for publication: Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates