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

Scheduling with Agreeable Release Times and Due Dates on a Single Continuous Batch Processing Machine

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

We consider the problem of continuous batch scheduling arisen from the heating-process of blooms in the steel industry, where each job has release time and a due date, each heating furnace is modeled as continuous batch processing machine and the jobs in the same batch enter and leave the machine in periods. In this paper, the jobs release time and due dates are assumed to be agreeable. We consider two different objective functions： minimize the maximum tardiness and minimize the number of tardy jobs. We study the complexity of the problems and prove that both of them are NP-hard in the strong sense. We also provide optimal algorithms with polynomial running times for the case where the jobs release time, due dates, and processing time are agreeable, respectively.