Re: [問題] 印刷機和裝訂機

※ 引述《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
→ hil:Cool!