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

※ 引述《hil (隨機客)》之銘言：
: ※ 引述《pangfeng (P老師)》之銘言：
: : 一台印刷機, 一台裝訂機, n本書.
: : 第i本書印刷需pi時間, 裝訂需bi時間.
: : 每一本書須先印刷, 再裝訂.
: : 問如何排列印刷裝訂順序, 以最短時間完成n本書?
: 看來像是
: Non-preemptive 2-processor scheduling
: with precedence constraint to minimize
: makespan
: 的排程問題（的special case), 會不會是 NP-hard?
: General multi-processor scheduling problem
: with precedence constraint to minimize
: makespan
: 應該是NP-hard（即使只要尋找4/3-approximation也
: 是NP-hard), 好消息是有2-approximation.
應該更像是flow shop problem with two processors,
這個是P可解
see http://www.mathematik.uni-osnabrueck.de/research/OR/class
for reference

--
※ 發信站: 批踢踢兔(ptt2.cc) 
◆ From: 218.166.104.206
→ hil:Cool!