A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time ?
The identical parallel machine scheduling problem with the objective of minimizing total weighted completion time is considered in the online setting where jobs arrive over time. An online algorithm is proposed and is proven to be (2.51/2m)-competitive based on the idea of instances reduction. Further computational experiments show the superiority over other algorithms in the average performance.
parallel machine total weighted completion time instance reduction online scheduling competitive ratio