A Lower Bound for the On-Line Preemptive Machine Scheduling with ?p Norm
We consider the on-line version of the preemptive scheduling problem that minimizes the machine completion time vector in the ep norm (a direct extension of the l∞ norm: the makespan) on M parallel identical machines. We present a lower bound on the competitive ratio of any randomized on-line algorithm with respect to the general ep norm. This lower bound amounts to calculating a (non-convex)mathematical program and generalizes the existing result on makespan. While similar technique has been utilized to provide the best possible lower bound for makespan, the proposed lower bound failed to achieve the best possible lower bound for general ep norM (though very close), and hence revealing intricate and essential difference between the general ep norm and the makespan.
Tianping Shuai Donglei Du
School of Science, Beijing University of Posts and Telecommunications, China Faculty of Business Administration,University of New Brunswick, Canada
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
661-669
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）