看板ACMCLUB
标 题Re: [问题] 印刷机和装订机
发信站批踢踢兔 (Thu Mar 23 17:21:45 2006)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
※ 引述《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
1F：→ hil:Cool!推 03/23 17:21