看板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