极小化最大完工时间的单机连续型批调度问题

从钢铁工业中加热炉对管坯的加热过程,提出一种新的连续型批处理机调度问题,与传统批处理机调度问题的批进批出方式不同,其主要特征为批中工件的进入、处理和离开都连续进行,批B_i的处理时间与该批的大小|B_i|、批中工件T_j的处理时间p_j及机器的容量C都有关,表示为p^{(i)}=\dmax_{T_j\in B_i}\{p_j\}(1+\displaystyle\frac{|B_i|-1}{C}).对于极小化最大完工时间问题,给出了一个复杂性为O(n^2)的动态规划算法,并证明了这个算法的最优性.

Scheduling a Single Continuous Batch Processing Machine to Minimize Makespan

A new problem of continuous batch scheduling arisen from the heating-process of blooms in the iron and steel industry is addressed, which differs from the traditional batching machine scheduling where jobs in the same batch have a starting time and a finishing time. Each heating furnace is modeled as a continuous batch processing machine, which can handle up to C jobs simultaneously, where jobs in the same batch enter and leave the machine continuously. The processing time of a batch Bi in this paper is related to |Bi|, pj and C, where |Bi| is the size of Bi and pj is the processing time of job Tj in the batch. We give the expression of the processing time of batch Bi as . We also present a dynamic programming algorithm with complexity of O(n2) and the properties of the optimal solution to minimize makespan.