看板ACMCLUB
标 题Re: [闲聊] 水龙头
发信站批踢踢兔 (Tue Mar 28 16:12:23 2006)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
※ 引述《pangfeng (P老师)》之铭言：
: 有n个人排队取水, 第i个人取水需ti.
: 问如何排队取水, 使所有人的等待时间和为最小?
这个问题和Minimum Average Completion Time等价 (\sum C_j) in scheduling
P||\sum C_j
可以采用shortest-job-first schedule 得到optimal
This is a very special case for multiprocessor scheduling problem
with poly-time algorithm to derive optimal solutions.
--
※ 发信站: 批踢踢兔(ptt2.cc)
◆ From: 218.166.104.87