Minimizing total weighted flowtime subject to minimum makespan on two identical parallel machines |
| |
Authors: | Johnny?C?Ho Francisco?J?López Alex?J?Ruiz-Torres Tzu-Liang? Tseng |
| |
Affiliation: | (2) Industrial Engineering and Operations Research, Columbia University, New York, NY, USA; |
| |
Abstract: | 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 makespan
(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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|