释放时间和工期同序的单机连续型批调度问题

摘要：

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

关键词：加热炉调度、连续批、计算复杂性、动态规划算法

所属期刊栏目：34

分类号：O223(运筹学)

资助基金：国家杰出青年科学基金70425003;国家高技术研究发展计划863计划2006AA042174;国家自然科学基金60674084

在线出版日期：2008-09-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：957-963