单机批调度中的算法与计算复杂性研究

单机批调度问题源于半导体制造中耗时最长的预烧工序，研究如何把工件合理分批调度使完成时间最短，在飞机制造、服装制造、金属切割、网格计算等领域都有广泛的应用，是计算机科学中的研究热点。项目将解决2个长久未解决的计算复杂性问题，并对其中一个问题给出多项式时间近似方案；对2-3个问题给出多项式时间算法；对2个问题给出实用近似算法。具体的研究内容如下：（1）证明批容量有界，即使是批容量=2的一般情况是NP-困难的；证明批容量有界，即使是批容量=2的m-type问题是NP-困难的；（2）设计批容量有界的一般情况的多项式时间近似方案；（3）对工件类型是常量的简单情况，批容量=3的简单情况设计多项式时间算法；（4）对批容量无界、权重相同、到达时间可能不同的情况设计多项式时间算法；（5）对批容量有界和无界的一般情况分别设计实用的近似算法。