一种求解排程问题的剪枝搜索算法

甄 卓

(宝山钢铁股份有限公司中央研究院,上海 201999)

宝武集团提出将绿色作为企业发展的生命底色和战略基色,大力推进智慧制造支撑绿色发展。同时市场环境也在发生变化,需求呈现多品种小批量定制化的趋势。智慧制造能力日渐成为钢铁制造企业的核心竞争力,而排程作为智慧制造的关键部分,需要企业给予足够的重视和投入。如果不能使用模型进行智能排程,那么智慧制造就是名不副实的。宝钢研究院智能制造所的智能优化领域技术团队,在智能排程领域深耕多年,取得了丰富的经验和丰硕的成果。针对钢级“以优充次”的炼钢组炉问题,构建了以炼钢成本最小化与炼钢余材最小化为目标的多目标优化模型[1]。针对炼钢生产中的钢种集约问题,以图论的工具,设计了基于最大独立集的求解方法[2]。针对连铸计划中的组中间包问题,建立了多旅行商模型,提出了一种结合启发式、邻域搜索和EDA进化的混合优化算法[3]。在炼钢连铸计划中,改进后的新工艺条件使得中间包寿命的评价方法由固定炉数变成了固定时间,针对这种变化,提出了相应的中间包优化模型[4]。结合双目标旅行商问题提出了最大最小蚂蚁算法[5]。将热轧生产计划优化问题归结为多目标奖金收集车辆路径问题,实现了一种Pareto最大最小蚂蚁系统算法[6]。提出了一种实用有效的计划排程优化算法,开发了基于该优化模型的轧制计划排程优化应用系统[7]。设计了基于局部搜索与混合多样性策略的多目标粒子群算法[8]。针对板坯重可变的自产板坯设计问题,设计了一种基于列生成与网络最大流的两阶段优化算法[9]。自主开发了不锈钢与碳钢交叉轧制计划混合排程优化模型[10]。

已有成果更多关注于单工序,针对工序特点进行设计,在算法通用性和复用性方面考虑不足。在对以往的工作成果进行总结的基础上,结合宝钢生产实际情况,对排程问题进行深入分析并抽象,提出了一种通用的算法,可以在不同工序、不同机组上复用,而且算法运行速度快。此外,算法执行一次,可以得到对应多种优化目标的多个最优解。该算法目前已在宝钢某热镀锌产线上线试用。

1 排程问题分析

在对不同工序、不同产线、不同机组的排程情况进行综合分析之后,发现以下几个方面对算法的设计有重要影响:

(1) 材料之间的顺序。材料完全无序的情况在实际中几乎不会出现,合同的优先级和工艺规程都会对材料的先后顺序提出要求。例如生产计划的编排以合同为单位,不同的合同具有不同的优先级;再比如冷轧工序要按从宽到窄的顺序安排轧制。如果可以充分利用材料之间确定的顺序关系,则可以显著提升算法效率。

(2) 通板规程,即判断两个材料是否可以连续生产的规则。在实际生产中,通板规程数量最多,比如冷轧工序要关注材料的宽度跳跃、厚度跳跃、温度跳跃等。由于任意相邻两块材料都要满足所有的通板规程,所以在计划构建过程中,大量的时间将用于通板规程的检测。同时,通板规程对产品的质量、设备的状态都有直接影响。比如平整过程中,如果违反厚度跳跃的约束,一方面会影响产品表面,另一方面也会影响平整辊表面,严重时导致产品表面质量不合格,更换平整辊。所以通板规程是规程检测的重中之重。

(3) 优化目标。在实际生产过程中,在不同情况下,生产的目标会发生变化。比如说季度初的目标是促生产,季度末的目标是保合同。排程模型应该能够支持多种优化目标。如果模型可以一次给出若干种优化目标下的最优结果供比较选择,对生产管理有积极意义。

在之前的成果中,通常把排程问题建模为组合优化问题,以材料之间的序为决策变量,以规程为约束条件,求某种目标下的最优解。这样做有几方面的不足:第一,在钢铁生产过程中,材料之间经常是有序的。建模为组合优化问题,建模过程中难以充分利用材料有序这一条件。第二,有很多规程难以用数学公式表达,限制了组合优化模型的表达能力。比如如果限制硅钢产品不能和汽车外板连续轧制,这种规程难以用数学公式的方式表达。第三,在不同情况下,优化目标可能不同,如果建模成单目标组合优化问题,那么为了求解不同目标下的最优解,需要分多次从头求解。

基于对排程问题的和已有工作的分析,提出了一种新的算法。算法以通板规程为约束,利用材料已知的先后顺序,对合规的材料序列展开搜索,给出一个包含了若干优质可行解的集合。根据优化目标,在可行解集合中挑选出最优解;若存在多种优化目标,可以从可行解集合中挑选出多种优化目标下的多个最优解。为了提升算法执行效率,提升搜索结果质量,采取了头部剪枝和尾部剪枝两种优化技巧。

2 算法组成

算法由等价材料过滤、材料排序、搜索可行解(剪枝优化)、等价材料恢复和选取最优解几个部分顺序组成。

2.1 等价材料过滤

宝钢生产计划以合同为核心,挂在同一合同下的材料其目标规格和其他工艺指标相同。有的合同虽然不同,但从排程的角度来看,材料之间仍可视为等价。材料等价的现象十分常见,待排计划的材料中,只有一部分是不同的。如果只保留不同的材料,将显著减小问题的规模,在后续的排序和搜索中,显著减少运算次数,提升运算速度。所以首先对材料进行过滤,等价的材料只保留一个,再进行排序和搜索,最后将过滤掉的材料恢复。例如有材料序列A0、A1、B0、B1、B2、C0、D0、D1、D2,其中A0、A1等价,B0、B1、B2等价,D0、D1、D2等价,经过过滤之后,以A0、B0、C0、D0作为后续步骤的输入。

2.2 材料排序

由于合同交期的不同,生产计划目标的不同,设备状态的不同,工艺上的要求,材料之间存在先后顺序。比如紧急合同优先于一般合同,精整过程中要求材料按照宽度递减等。综合各方面的要求,可以指定材料排序的方式。材料经过排序后,确定材料生产序列的问题,就从排列问题简化为组合问题,极大降低了运算代价。

2.3 搜索可行解(剪枝优化)

在材料先后顺序确定的条件下,进行可行生产序列的搜索。一边搜索,一边进行通板规程检测。为了生产的稳定和产品的质量,排计划时会尽可能地把所有的材料排入计划,以免排出若干个“碎片”计划,导致机组需要不断地中断生产,调整设备和人员。为了保证不遗漏任何可行的序列,使用深度优先搜索策略。为了便于开发和调试,采用了递归的实现方式。

假设算法已经从材料A出发,通过深度优先搜索尝试了所有以A为开头的序列,并得到了一个合法的材料序列A、B、C、D、E,那么B、C、D、E,C、D、E,D、E,E这几种序列就不需要保留,只应保留最长的A、B、C、D、E。进一步,在后续搜索过程中,不需要再以B为开头搜索可行的序列。这是由深度优先搜索的特性决定的,在以A为开头的搜索过程中,所有以B为开头的序列都已经尝试过了。C、D、E同理。这种剪枝方式可以避免大量的从序列头部开始的无效搜索,称之为头部剪枝。

除此之外,假设算法已经从材料A出发,通过深度优先搜索尝试了所有以A为开头的序列,并得到了一个合法的材料序列A、B、C、D、E,那么A、B、C、E,A、B、D类似的序列就不需要保留,把这些无效的序列丢弃,可以大量减少搜索结果中的无效序列。另外,在算法搜索到序列A、B、C、E时,不需要再继续向后搜索,因为深度搜索策略的特性决定了A、B、C、E后续所有可能的材料序列,在搜索到A、B、C、D、E时都已经尝试过。这种从尾部过滤无效搜索的方式,称之为尾部剪枝。

通过头部剪枝和尾部剪枝,根据已经搜索到的结果避免后续无意义的搜索,显著提升了算法运行速度并提升了结果质量。极端情况下,在O(n)时间内,就可以求得全部可行序列。需要指出的是,算法保证在给出的可行序列集合中,没有任何一个序列是另一个序列的子序列。

2.4 等价材料恢复

为了提升排序和搜索效率,等价的材料只保留一个参与运算,在算法执行完毕之后,需要将被过滤掉的等价材料重新插入到结果中。与2.1对应,如果搜索得到的结果是A0、B0、D0,则经过恢复,得到序列A0、A1、B0、B1、B2、D0、D1、D2。

2.5 选取最优解

在已经得到了全部可行解的前提下,从中选取到的最优解一定是全局最优解。此外,在生产中通常有若干种优化目标,从中可以挑选出对应每种优化目标的全局最优解。也就是说,一次搜索,就可以得到若干最优解,方便管理人员进行对比和挑选。

3 算法实现

算法以C++实现,以C++标准库提供的组件为基础。为了减小算法执行过程中大批数据移动造成的开销,以vector存储待排序的材料序列,以材料在vector中的下标作为材料的索引。后续所有的计算针对索引进行。

3.1 等价材料过滤

为了方便等价材料的过滤和恢复,需要配套使用哈希函数和哈希表,记录材料之间的等价关系。根据产线的具体要求,设计一个哈希函数,为材料生成一个键,保证等价的材料生成的键值相同。从前向后扫描材料序列,加入哈希表。如果一个材料的键值已经出现过,则代表该材料已经存在等价材料,需要加入相应的等价材料组。在所有的材料分组完毕之后,每个材料组选取一个代表,作为后续算法步骤的输入。比如哈希表中形成了材料分组为A0、A1一组,B0、B1、B2一组,C0一组,D0、D1、D2一组,以A0、B0、C0、D0作为下一步骤的输入。

3.2 材料排序

综合合同优先级、工艺要求、生产目标,确定材料排序的方式,以C++标准库提供过的sort函数为基础,自己实现排序的方式。比如,如果材料需要按质量递增的顺序排序,排序方式以如下方式实现:

class WeightUp

bool operator()(int left,int right) {

if ((_items + left)->MAT_WT < (_items + right)->MAT_WT)

return true;

else

return false;

调用标注库排序算法实现材料索引按照材料质量递增的方式排序。其中indexes代表需要待排计划的材料的索引。

::std::sort(indexes.begin(),indexes.end(),WeightUp(data,count));

3.3 搜索可行解

为了搜索到尽量长的满足通板规程的材料序列,使用深度优先搜索的策略;为了搜索到所有的可行解,以递归的方式进行深度优先搜索。算法的整体逻辑是,在一开始,将材料加入空的缓存序列,再向后选取一个元素,如果加入之后满足通板规程,则将该元素加入缓存序列,递归地进行深度优先搜索。搜索结束之后,将之前加入缓存的材料退出。再向后选取一个元素,重复执行上述步骤。indexes代表参与搜索的材料的索引,begin代表当前要加入序列的材料在indexs中的位置,current缓存了当前搜索得到的材料序列,result存储了搜索得到的结果。伪代码如下:

backtrack(indexes,begin,current,result)

if begin已经超出indexes的范围,没有材料可以加入缓存序列

将current中缓存的序列作为结果加入result

函数返回

if 缓存序列为空

遍历begin指向的材料及之后的材料

将遍历到的材料加入缓存序列current

backtrack(indexes,i + 1,current,result),递归执行

退出新加入缓存序列current的材料

函数返回

else

遍历begin指向的材料及之后的材料

if 遍历到的材料加入缓存序列,不违反通板规程

将遍历到的材料加入缓存序列current

backtrack(indexes,i + 1,current,result),递归执行

退出新加入缓存序列current的材料

3.4 头部剪枝

假设待排序的材料是A、B、C、D,那么深度优先搜索的策略会先搜索所有以A开头的合法序列,再搜索以B开头的合法序列,再搜索以C开头的合法序列,最后搜索以D为开头的合法序列。如果在以A开头的搜索中,搜索到了A、B、D这样一个合法序列,根据深度优先搜索的特性,可以知道,所有以B为开头的合法序列都已经被搜索到,且以B为开头的序列,一定包含在以A为开头的序列之中。生产实际需要尽量将更多的材料排入计划,所以A、B、D优于B、D。基于以上两点分析,可以得出结论,如果已经得到了A、B、D这样的序列,那么没有必要再以B或者D开头进行搜索。这样就大大减少了算法的运算量。这种从头部剪枝的方式,可以通过修改搜索算法实现。以哈希表headPrune存储已经出现在结果中的材料,当这些材料出现在缓存序列的头部时,直接退出,不进行后续搜索。伪代码如下:

backtrack(indexes,begin,current,headPrune,result)

if begin已经超出indexes的范围,没有材料可以加入缓存序列

将current中缓存的序列作为结果加入result

遍历作为结果加入result的材料序列

将材料加入哈希表headPrune缓存

函数返回

if 缓存序列为空

遍历begin指向的材料及之后的材料

如果该材料已经在哈希表headPrune中出现

函数返回

else

将遍历到的材料加入缓存序列current

backtrack(indexes,i + 1,current,headPrune,result),递归执行

退出新加入缓存序列current的材料

函数返回

else

遍历begin指向的材料及之后的材料

if 遍历到的材料加入缓存序列,不违反通板规程

将遍历到的材料加入缓存序列current

backtrack(indexes,i + 1,current,headPrune,result),递归执行

退出新加入缓存序列current的材料

3.5 尾部剪枝

假设待排序的材料是A、B、C、D、E、F、G,以A为开头的搜索中假设已经搜索到了合法序列A、C、D、E,那么A、C、E和A、D、E这样的序列就不需要出现在最终的搜索结果中。而且深度优先搜索的特性决定了从A、C、E出发得到的所有后续序列,已经包含在以A、C、D、E出发得到的所有后续序列之中。所以在已经得到以A、C、D、E这样的结果之后,不需要以其子序列出发再进行搜索。以这种在序列尾部考虑剪枝的方式,可以从另一方向显著减少搜索的代价,提升结果的质量。

具体的实现方法是,使用一个哈希表来标记已经存在于结果中的材料,在算法回溯的过程中,如果要加入缓存的材料已经出现在结果中,那就不需要搜索下去。比如A、C、D、E已经出现在搜索结果中,当前缓存的序列是A、D,接下来要尝试将E加入,获得A、D、E,但是E已经出现在了结果中,所以可以跳过E,直接尝试加入F,如果加入F满足通板规程,则得到了一个新的合法序列——A、D、F。新增哈希表tailPrune,缓存前一次递归哪些材料已经作为结果输出,算法伪代码如下:

backtrack(indexes,begin,current,headPrune,tailPrune,result)

if begin已经超出indexes的范围,没有材料可以加入缓存序列

将current中缓存的序列作为结果加入result

遍历作为结果加入result的材料序列

将材料加入哈希表headPrune缓存

将材料加入哈希表tailPrune缓存

函数返回

if 缓存序列为空

遍历begin指向的材料及之后的材料

如果该材料已经在哈希表headPrune中出现

函数返回

else

将遍历到的材料加入缓存序列current

backtrack(indexes,i + 1,current,headPrune,tailPrune,result)

退出新加入缓存序列current的材料

函数返回

else

遍历begin指向的材料及之后的材料

if 遍历到的材料没有出现在哈希表tailPrune中,且加入缓存序列不违反通板规程

创建临时哈希表tempTailPrune,复制tailPrune

将当前遍历到材料以后的材料,从tempTailPrune中移除

将遍历到的材料加入缓存序列current

backtrack(indexes,i + 1,current,headPrune,tempTailPrune,result)

退出新加入缓存序列current的材料

将tempTailPrune中新出现的材料加入tailPrune

3.6 等价材料恢复

经过3.5得到了若干优质的可行解,但是这些解是过滤掉了等价元素的,需要根据3.1缓存的分组关系,将材料恢复。假设得到的结果序列为A0、B0、D0,则经过恢复的序列为A0、A1、B0、B1、B2、D0、D1、D2。

3.7 选取最优解

根据不同的优化目标,可以给材料序列设定不同的打分函数,将打分函数应用于可行解序列,即可选出分数最高的材料序列。例如要选取包含材料数最多的材料序列,可以从前向后遍历可行解集合,挑选出最长的材料序列。

4 应用效果

算法使用宝钢某热镀锌产线的实际生产数据进行了试验,得到如图1所示结果。从图1可以看出,算法运行时间随材料个数增加而上升,但上升趋势平缓。材料数量在一定范围内时,算法运行时间与材料数量接近线性相关。热镀锌产线的生产前库的库存是有限的,实践证明,在达到最大库存的情况下,算法可以在2 s内执行完毕。

图1 算法运行时间随输入材料数变化趋势图Fig.1 Tendency chart for time cost of the scheduling algorithm

相比于人工排程或者既有的排程模型,该算法体现出了如下优势:

(1) 运行速度快。绝大部分情况下,算法可以在2 s内给出结果。

(2) 一次运行,多个最优解。在提前设定好多种优化目标之后,算法运行一次,就可以给出各种优化目标对应的最优解,供计划员对比和选择。

(3) 算法通用性高,方便移植。算法对排程问题的假设比较简单,一是材料有序,二是尽可能将更多地材料排入计划。只需要根据新产线的情况,定义好材料排序方式、通板规程以及优化目标,即可应用该算法求得最优的材料序列。目前在酸轧排程模型中,已经成功移植了该算法。

5 结论

(1) 宝武集团将绿色作为生命底色和战略基色,大力推进智慧制造支撑绿色发展,智慧制造能力日渐成为钢铁制造企业的核心竞争力。排程作为智慧制造的核心部分,需要开展深入的研究和实践。

(2) 本文提出了一个算法,可以快速求解排程问题。

(3) 该算法运行速度快;一次执行可以给出多种优化目标下的最优解;具有通用性,易于移植与推广。

(4) 目前已经应用于宝钢某热镀锌产线的智能排程,实践证明了该算法的可行性与优越性,并成功移植到了酸轧产线的排程模型中。