Makespan minimization subject to flowtime optimality on identical parallel machines

We consider the identical parallel machine problem with makespan minimization subject to minimum total flowtime. First, we develop an optimal algorithm to the identical parallel machine problem with the objective of minimizing makespan. To improve the computational efficiency, two implementation techniques, the lower bound calculation and the job replacement rule, are applied. Based on the algorithm, an optimal algorithm, using new lower bounds, to the considered problem is developed. The result of this study can also be used to solve the bicriteria problem of minimizing the weighted sum of makespan and mean flowtime. Computational experiments are conducted up to six machines and 1000 jobs. Although the proposed algorithm has an exponential time complexity, the computational results show that it is efficient to find the optimal solution.