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