Minimizing total weighted flowtime subject to minimum makespan on two identical parallel machines

摘要

We study the problem of scheduling n jobs on two identical parallel processors or machines where an optimal schedule is defined as one with the shortest total weighted flowtime (i.e., the sum of the weighted completion time of all jobs), among the set of schedules with minimum make-span (i.e., the completion time of the last job finished). We present a two phase non-linear Integer Programming formulation for its solution, admittedly not to be practical or useful in most cases, but theoretically interesting since it models the problem. Thus, as an alternative, we propose an optimization algorithm, for small problems, and a heuristic, for large problems, to find optimal or near optimal solutions. Furthermore, we perform a computational study to evaluate and compare the effectiveness of the two proposed methods.