《單機批調度中的算法與計算複雜性研究》是依託山東大學，由馮好娣擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：單機批調度中的算法與計算複雜性研究
- 項目類別：青年科學基金項目
- 項目負責人：馮好娣
- 依託單位：山東大學
- 支持經費：23（萬元）
- 研究期限：2007-01-01 至 2009-12-31
- 負責人職稱：教授
- 申請代碼：F0201
- 批准號：60603007
中文摘要
單機批調度問題源於半導體製造中耗時最長的預燒工序，研究如何把工件合理分批調度使完成時間最短，在飛機製造、服裝製造、金屬切割、格線計算等領域都有廣泛的套用，是計算機科學中的研究熱點。項目將解決2個長久未解決的計算複雜性問題，並對其中一個問題給出多項式時間近似方案；對2-3個問題給出多項式時間算法；對2個問題給出實用近似算法。具體的研究內容如下：（1）證明批容量有界，即使是批容量=2的一般情況是NP-困難的；證明批容量有界，即使是批容量=2的m-type問題是NP-困難的；（2）設計批容量有界的一般情況的多項式時間近似方案；（3）對工件類型是常量的簡單情況，批容量=3的簡單情況設計多項式時間算法；（4）對批容量無界、權重相同、到達時間可能不同的情況設計多項式時間算法；（5）對批容量有界和無界的一般情況分別設計實用的近似算法。
