Load balancing a priori strategy for the probabilistic weighted flowtime problem

In a previous work (Bouyahia et al., 2010), we introduced and studied the probabilistic generalization of the classical total weighted completion time problem. We defined two a priori strategies devoted to the incorporated problem on parallel identical machines ( ${\mathcal{U}}_A$ and ${\mathcal{U}}_B$ ). The main drawback of the proposed a priori strategies is that the machine loads are not balanced after deleting the absent jobs from an a priori schedule. In this paper, we try to overcome this limitation by proposing an a priori strategy denoted as ${\mathcal{U}}_k$ which takes into account the load balance. First, we present the algorithm of the load balancing strategy and we explicit the objective function. Then, we study its complexity and its performance compared to the other strategies. Special care is also devoted to assess experimentally the performance of ${\mathcal{U}}_k$ .