基于ILOG平台的求解动态车间作业调度问题优化算法研究

1、 军民两用技术与产品2010·3摘要研究了基于约束规划和启发式搜索算法结合求解动态车间作业调度的问题。以最小化制造周期费用与总拖期惩罚费用之和为优化目标,通过建立调度模型、分析问题的优化特性,提出了基于约束规划的禁忌搜索启发式算法,根据与另外两种算法的比较结果,验证了此算法的有效性。关键词车间作业,调整时间,约束规划,禁忌搜索Research on Job Shop Scheduling Optimization Algorithm Based on ILOG PlatformZou Shengliang Yang Jianjun(Institute of Industrial an

2、d Manufacturing System Engineering ,Beihang University,Beijing 100191Abstract The Job Shop scheduling problem was solved by combining the constraint programming method with thetabu search algorithm.The object function was set to be minimizing the sum of the manufacturing cost and the loss due to the

3、 delay.This approach was proved to be effective by comparing its results to those achieved by another two optimization methods.KeywordsJob Shop ,Setup ,Constraint programming ,Tabu search文章编号:1009-8119(201003-0042-03邹胜亮杨建军(北京航空航天大学工业与制造系统工程系,北京100191基于ILOG 平台的求解动态车间作业调度问题优化算法研究1引言生产排程问题广泛存在于各个领域中。作为

4、生产排程问题的一个重要难点,车间作业(Job Shop 调度问题的关键是将不同的工序任务分配到不同的设备上,并根据一个目标函数给定的目标对工序任务进行排序。以往,航空系统车间作业的调度问题一直都属于NP-HARD 难题,是制造业的研究难点和重点。现有的一般性方法已经不能满足其求解需求。本文在分析模型复杂性的基础上,利用约束优化工具ILOG ,以最小化总拖期惩罚费用和总调整费用为优化目标的多目标,提出了基于约束规划(Constraint Programming 的禁忌搜索启发式算法。2问题描述2.1模型描述Job Shop 调度模型可以表述为如下形式:令J =1,2,n 表示工件集,M =1,2

5、,m 表示资源集,O =1,2,o 表示工序集。工件j 由O j 个工序序列组成,它们是(l j-1+1,l j-1+2,l j -1+O j ,工件加工完工时间C j ,这里的l j-1=j-1i=1O i是前j-1个工件中的工序的总数(j =1,2n ;l 0=0;j-1i=1O j =O ,工序i 必须在资源w i M 上面加工一段时间d i >0,i O ,(这段时间工序的加工不能被打断。同样地,从资源的角度,把工序集O 重新分化为很多子集M k =i O :w i =k ,每个子集表示要在资源k 上加工的工序,令m k =M k ,代表资源k 上加工的工序的数量,而在资源k 上

6、加工的工序的序列是k (k (1,k (2,k (m k ,k M ,其中m k (i 表示子集M k 的在k 中处在i 位置的元素,也就是在资源k 上第i 个进行加工的工序。2.2目标函数本文主要考虑的目标函数是整体加工周期(Makespan 最短和拖期费用最小,拖期费用通过对每一个零件任务的完成时间建立一个弹性的约束,使得每一个零件任务都在该期限内完成;如果不能满足该约束,则放弃该解,重新调度。在实际求解的过程中,注意设备负荷的均衡、工序任务的分配问题,就可以很好地解决某零件任务拖期严重的问题。c j =nj=1max (j (c j -d j ,0+max st jh +du jh ,c

7、 max 叟c j 。setLB ,setUB 分别为Makespan 的初始值下限和上限,Makespan 初始值计算公式如下:1(M akespan.setLB (solver.getMin (M akespan +M akespan.setLB (solver.getMax (M akespan 2.3决策变量工序O jh 的开始时间st jh ,另外,还包括一些附加的变量, 2010·3军民两用技术与产品如工件完成时间c j 、表示Makespan 的c max 等。2.4约束(1客观约束包括设备约束和工艺约束;(2主观约束包括设置工作中心的能力、资源可选、指定零件任务开始时

8、间、指定交货期、工序移动方式和下一道工序开始加工时间的约束。3算法实现3.1求解过程本文研究的动态作业调度算法的目标函数是整体加工周期(Makespan 最短、设备利用率最高、任务拖期率最低。为了达到这个目的,如何确定每个设备上的任务队列,以及队列中每个任务的起止时刻是求解这一问题的关键。在约束满足问题中,任务的起止时刻作为变量被加以诸如加工先后顺序、设备占用等约束条件,这个起止时刻的可选集合是有限的。为提高搜索效率,必须运用约束传播来快速减除可选集合中的不可行区域,剩下少量的可行解,通过对其进行比较得到满意的解决方案。具体过程如图1所示:3.2关键路径和缩短任务间的缝隙誗计算关键路径例如,图

9、2中的C0C1B1B2和D0A0C1B1B2是两条关键路径。根据Ilo Scheduler Solution 中的Ilo Activity 工序任务集合计算出关键路径。在关键路径上的某个选择的工序任务未加工完成前,不考虑其它的工序任务和资源约束。誗同一个设备上选择工序任务加工顺序如图3所示,对每一个设备进行图搜索,对每一个结点,设定一对资源约束(srct1,srct2,可缩短的时间为:deltaEnd1=emax1-IlcMin (emax1,smax2deltaStart2=IlcMax (emin1,smin2-smin2impact (srct1,srct2=deltaEnd1+delt

10、aStart2为了实现最后的Makespan 最小,交货期最短,尽量压缩工序之间的加工空隙,采用impact (srct1,srct2=deltaEnd1+deltaStart2较小的加工顺序进行加工。3.3禁忌搜索禁忌搜索(Tabu Search 或Taboo Search 的思想最早由Glover (1986提出,涉及到邻域(Neighborhood 、禁忌表smin1ACT1emax1emax2ACT1deltaStart2smin2deltaEndl图3同一个设备上工序任务加工顺序图2关键路径计算图图4禁忌搜索算法流程图43 军民两用技术与产品2010·3(Tabu list

11、 、禁忌长度(Tabu 1ength 、候选解(Candidate solution 、藐视准则(Aspiration criterion 等概念。简单TS 算法的基本思想是:给定一个当前解(初始解和一种邻域,然后在当前解的邻域中确定若干候选解;若最佳候选解对应的目标值优于“best so far ”状态,则忽视其禁忌特性,用其替代当前解和“best so far ”状态,并将相应的对象加入禁忌表,同时修改禁忌表中各对象的任期;若不存在上述候选解,则指向在候选解中选择非禁忌的最佳状态为新的当前解,而无视它与当前解的优劣,同时将相应的对象加入禁忌表,并修改禁忌表中各对象的任期;如此重复上述迭代搜

12、索过程,直至满足停止准则,如图4所示。本文采用约束规划产生的解作为禁忌搜索的初始解。利用单纯的约束规划(CP 方法求解动态车间作业调度问题的效果并不理想。CP 本质上是通过约束传播等方式尽快地减少搜索空间,从而减少不必要的搜索路径,缩短所耗费时间。本文采用约束规划和禁忌搜索结合的方法,其流程如图5所示:4实验和算例为了证明算法的有效性,选择一项包含10个不同零件的任务,每个零件有10个工序任务,根据不同的顺序依次在10个不同的设备上加工的实验作为输入数据,并对结果进行分析。本实验在奔腾2.8GHz 服务器上运行,其中各主要参数设定为:禁忌表长度为10,总的循环次数为200次。通过与另外两种算法

13、(系统搜索和一般模拟退火的比较来验证禁忌搜索算法的正确性和有效性。系统搜索也是利用ILOG 实现,但并不采用禁忌搜索算法。利用本实验平台得到的结果如表1所示:在实际研究中,本文算法处理的实验样本为263个零件任务共计8000个工序任务,54个工作中心的资源,得到的运算结果如表2所示:其中,拖期的零件个数仅有42个,提前20天完成的零件个数为128个,最大资源利用率为92.3%,通过交货期约束的调整,可将拖期的零件加工完成时间提前。原本提前完成的零件任务的完工时间相应地向后推迟;再次进行调度后产生拖期零件19个,最大拖期35天。资源平均利用率为53.4%,优化值变为225109,从结果看有明显改

14、善。5结论本文建立了以最小化加工周期费用和最小化总拖期费用为优化目标的多目标调度模型,在分析模型复杂性的基础上,采用基于ILOG 的约束规划与禁忌搜索混合算法获得了比较好的效果,利用了ILOG 本身提供的深度优先搜索和约束传播方法,加快了算法实现的进程,结合比较其它的两种算法,验证了禁忌搜索算法的有效性和优越性,对解决这种面向实际应用的复杂性调度问题具有良好的参考价值。参考文献1 F.Sourd ,Earliness-tardiness scheduling with setup consid -erations ,Computers &Operations Research ,2005;32(7:184918652De