论文部分内容阅读
本文研究的连续型批处理机调度问题，是在钢铁工业管坯的加热过程中提出来的．工件带有释放时间和工期，工件进入和离开机器是按周期依次进行的．本文针对单机连续型批调度问题中工件释放时间和工期同序的情况，分析了极小化最大拖期和拖期工件数等问题的计算复杂性，证明了两类问题都是强NP-难的．对于工件的释放时间和加工时间、工期都同序的特殊情况，分别给出了能够获得对应问题的最优解的多项式算法．