The parallel machine real-time scheduling problem with objective of minimizing total weighted completed time
is investigated. The problem is formulated as a mixed integer programming model, and a LR&CG hybrid algorithm which
combines Lagrangian relaxation(LR) with column generation(CG) together is proposed to solve it. The LR&CG algorithm
contains double loops. In the inner loop, the subgradient method is executed to calculate lower bound and generate columns,
and in the outer loop the restricted master problem is solved to get shadow price which is used to adjust Lagrangian multiples.
The results of computational experiment show that the LR&CG algorithm can obtain tighter lower bound and higher quality
upper bound than the conventional LR algorithm within the same computational time, which implies that the previous one
has better convergent performance.