※ 引述《pangfeng (P老師)》之銘言：
: 一台印刷機, 一台裝訂機, n本書.
: 第i本書印刷需pi時間, 裝訂需bi時間.
: 每一本書須先印刷, 再裝訂.
: 問如何排列印刷裝訂順序, 以最短時間完成n本書?
Here is another solution:
For book printing:
1. process the books with pi <= bi in order of nondecreasing order pi
2. process the remaining books in order of nonincreasing bi
For book binding:
bind books with the same order of book printing
It is based on
S. M. Johnson, Optimal two- and three-stage production schedules
with setup times included, Naval Res. Logist. Quart. 1, (1954), 61-68.
The proof should be obvious.
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 140.112.28.117
→
03/23 17:21, , 1F
03/23 17:21, 1F
討論串 (同標題文章)