MINIMIZING FLOW TIME IN PARALLEL MACHINE SCI-HEDULE PROBLEM SUBJECT TO MINIMUM MAKESPAN
This paper considers the problem of scheduling n independent jobs on m ≥ 1 identical processors, with objective of minimizing the total flow time under the constraint that it must have minimum makespan considered. For nonpreemptive scheduling, it is known that the problem is NP-hard. But this paper only considers the pre emptive scheduling. And an O (nlgn) polynomial time algorithm to find the optimal preemptive scheduling with at most 2m - 1 preemptions is given. And the algorithm performance is shown through computational experi ments.
flow time schedule length preemptive scheduling makespan
Xiongzhi Wang Xiaowei Wen
College of Economics and Management, South China Agriculture University, Wushan Road 483,Tianhe District, Guangzhou 510642, China
国际会议
The Ninth International Conference on Industrial Management(第九届工业管理国际会议 ICIM2008)
日本大阪
英文
42-50
2008-09-16（万方平台首次上网日期，不代表论文的发表时间）