带有释放时间的半连续型批处理机调度问题(运筹学与控制论)

半连续批处理机调度问题,是从钢铁工业加热炉对管坯的加热过程中提炼出来的。工件按批加工,同一批中工件的加工时间等于此批中工件的最大加工时间,且工件必须按周期一个紧挨着一个进入、离开处理机。批处理机的容量为C,即最多可同时加工C个工件,批的容量为批中工件的个数,批的处理时间与批中工件的加工时间、批处理的容量和批的容量有关。本文研究释放时间与加工时间一致时,对于目标函数为最大完工时间问题,即时间表长问题,分析其最优解的性质,从而将问题转化为工件按释放时间非减顺序排列后,对工件进行分批,使得最大完工时间最小。在此基础上给出了一个复杂性为O(n2)的动态规划算法,证明了这个算法的最优性,并用数值例子进一步说明了算法的计算过程。

Semicontinuous Batch Processor Scheduling with Release Time

We consider the problem of semicontinuous batch scheduling arisen in the heating-process of blooms in the iron and steel industry.Jobs are processed in batch,the processing time of jobs in the same batch is the longest processing time of jobs in the batch and the jobs enter or leave the machine one after another in periods.The capacity of the machine is C,which can handle up to C jobs simultaneously.The capacity of a batch is the size of batch;the processing time of a batch is related to its size,the longest processing time of jobs in the batch and the capacity of the machine.In this paper,we assume that the job release time and processing time are agreeable.For the problem to minimize makespan,we study the characterizations of the optimal batching and then turn into nondecreasing order of the release time,process in batches and obtain the minimize makespan.On that basis,we present a dynamic programming algorithm with complexity of O(n2) and prove properties of the optimal solution,and give a numerical example to explain the process of algorithm.