%0 Journal Article
%T 带有释放时间的半连续型批处理机调度问题(运筹学与控制论)
%A 王松丽
%A 赵玉芳
%A 崔苗苗
%J 重庆师范大学学报(自然科学版)
%P 16-23
%D 2012
%R 10.11721/cqnuj20120204
%X 半连续批处理机调度问题,是从钢铁工业加热炉对管坯的加热过程中提炼出来的。工件按批加工,同一批中工件的加工时间等于此批中工件的最大加工时间,且工件必须按周期一个紧挨着一个进入、离开处理机。批处理机的容量为C,即最多可同时加工C个工件,批的容量为批中工件的个数,批的处理时间与批中工件的加工时间、批处理的容量和批的容量有关。本文研究释放时间与加工时间一致时,对于目标函数为最大完工时间问题,即时间表长问题,分析其最优解的性质,从而将问题转化为工件按释放时间非减顺序排列后,对工件进行分批,使得最大完工时间最小。在此基础上给出了一个复杂性为O(n2)的动态规划算法,证明了这个算法的最优性,并用数值例子进一步说明了算法的计算过程。
%K 加热炉调度
%K 半连续批
%K 计算复杂性
%K 动态规划算法
%U http://cqnuj.cqnu.edu.cn/oa/DArticle.aspx?type=view&id=120204