※ 引述《pangfeng (P老師)》之銘言：
: 一台印刷機, 一台裝訂機, n本書.
: 第i本書印刷需pi時間, 裝訂需bi時間.
: 每一本書須先印刷, 再裝訂.
: 問如何排列印刷裝訂順序, 以最短時間完成n本書?
<Reformulate the problem>
Given any optimal schedule, if the optimal time it gives is
T = \sum_i(bi)+t,
we can always pushing all the binding jobs to start as late as possible,
which is, the first binding job starts at time t.
So the problem of finding an optimal schedule is to find a schedule that
minimize t.
<Algorithm: Greedy Algorithm>
float t, T, p;
int i;
1. Initialize:
t = p1;
T = p1 + b1;
p = p1;
Put the first book into schedule;
2. for book i,
p = p+pi;
if we schedule it in the front,
=> t = t - min(t, bi) + pi;
if we schedule it in the back{
if (p > T)
=> t = t + (p - T);
else, t remains the same;
}
comare the t in the above cases, choose the schedule giving minimal q,
Update T accordingly;
3. repeat 2. until all the books are scheduled. This will give an optimal
schedule that takes T.
<Proof Note> (well, it is not a formal/complete proof)
1. Noted that in the second step, insert the book between the schduled
books won't give a better schedule than insert in the front, because
it for sure delayed the books behind but it can't untilize the empty
time slots in binding machine before it.
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 68.181.255.120