基于规则组合的Job Shop多目标柔性调度方法

2010-10-25王海瑶蒋增强葛茂根

合肥工业大学学报（自然科学版） 2010年1期

王海瑶, 蒋增强, 葛茂根

(合肥工业大学机械与汽车工程学院,安徽合肥 230009)

0 引言

随着现代制造业的发展,小批量、多品种、具有不同完工时间和产品要求的柔性制造逐渐取代了大批量、单品种的流水线产品制造,与此相适应的柔性车间的调度问题随之成为机械制造业研究的热点问题。

目前常用的柔性调度方法主要集中在各种优化算法上,如微粒群算法、遗传算法、免疫算法、模拟退火算法及神经网络算法等[1-5],但是在实际应用中随着生产系统规模的扩大,这些优化算法普遍存在着运算量较大、速度较慢、不容易求取全局较优解的问题,难以适应现场调度的实时性需求。本文通过建立一种基于规则组合的多目标柔性调度方法,利用规则调度的简单、快速的特点,解决Job Shop制造环境下多目标柔性调度的快速求解问题。

1 问题描述

关于柔性调度问题可以描述为:设有m类待加工工件和n台机器,pi表示工件i包含的工序数;表示工件i的第j道工序在机器k上加工表示工序开始加工时间;表示工序的加工时间。

每个工件包含一道或多道工序并且每道工序可以在多台性能不同的机器上加工,每道工序的加工时间、成本随机器性能的不同而变化。调度目标是对所有工序在不同机器上的加工顺序进行排列,使总优化目标达到最优,并且加工过程还要满足以下假设和约束条件:

(1)工件加工工艺事先已经确定。

(2)加工过程中,任一道已开始加工的工序不允许中途中断。

(3)在零时刻所有的工件都可以被加工。

(4)同一时刻,同一台机器只能加工一道工序。

(5)同一类工件的工序之间有先后约束,上一工序 j-1完成后才能开始下一工序 j,即:tsijk-ti(j-1)k-tsi(j-1)k≥0。

综合考虑工件的时间指标、成本指标以及质量指标,设定目标函数为min{f(T,C,Q)},其中T、C、Q分别表示时间、成本和质量指标。

1.1 T的计算方法

T作为时间指标,主要包含最大完工时间指标T(1)和加权延期和时间指标T(2)两部分,T=T(1)+T(2)。

每类工件的时间指标 Ti主要由时间变量(t(i),tijk,tei)组成。t(i)为工件 i的交货期,tijk为工件i的j道工序在机器k上的加工时间,tei为工件i的完工时间。

最大完工时间指标T(1)的计算公式为T(1)=max{tei},总延期时间指标T(2)的计算公式为:

式中li为第i类工件的超期惩罚权重系数,该系数和订购工件的客户级别密切相关。

其中

1.2 C的计算方法

成本指标C主要包含加工成本指标C(1)和延误成本指标C(2),即C=C(1)+C(2)。若设备k的单位成本为ck,则工件i的j道工序的加工成本cijk=ck×tijk,因此,所有工件的加工总成本C(1)=;延误总成本为式中 αi为工件提前单位时间损失成本;βi为工件延期单位时间损失成本;αi、βi的大小视实时工况而定。

1.3 Q的计算方法

2 规则调度方法研究

2.1 调度规则描述

规则调度方法是指在系统运行时,根据一定的规则和策略决定下一步操作的方法。其优点是不必进行大量的计算,避开了“组合爆炸问题”,只要选择了合适的规则便可产生相应的调度策略,方便易行。同时规则调度方法的计算速度非常快,可以及时、快速地实现基于实时工况条件下的多目标柔性调度[7]。

目前确定的调度规则已经超过100多种,其中运用较为广泛的主要有 FCFS、SPT、LPT、EDD、SCR、MWKR、LWKR 及MOPNR等规则。本文根据柔性调度的特点,结合多目标调度的需求,选择如下的调度规则,并针对柔性调度的特点进行了相应的改进,具体描述如下:

(1)SPT规则:优先选择加工时间最短的任务。

(2)EDD规则:优先选择完工期限最早的任务,尽可能保证交货期。

(3)SCR规则:优先选择关键比最小的任务,关键比的公式为:。式中DD是工件的交货期(t(i)),CD是当前时间,T是工件的剩余工序加工时间,(j′为 i工件的当前工序)。

(4)MWKR规则:优先选择余下加工时间最长的任务,加工时间的计算公式为

(5)MOPNR规则:优先选择余下工序数最多的任务,工序数的计算公式为pi-j′。

(6)SPC规则:优先选择加工成本最小的工序任务,工序加工成本的计算公式为ck×tijk。

(7)HPQ规则:优先选择工序能力指数最高的任务。

(8)RONDOM规则:随机挑选任务。

2.2 双层规则组合的调度方法

根据调度目标函数中选取的优化性能指标,考虑到满足加工时间、加工成本和加工质量的要求,在分析各种调度规则特点的基础上,选取以下规则,采用双层规则组合的方式构建调度方案集。4种第 1 层规则(EDD、SCR、MWKR、MOPNR)和4种第2层规则(SPT、SPC、HPQ 、RONDOM)共组成16组方案。

调度流程示意如图1所示。

图1 双层规则组合调度流程示意图

调度开始时,将调度任务集中当前时刻所有可以开始加工的工序任务,调入待加工任务集,根据组合规则中的第1层调度规则对这些工序任务进行排序。当同一优先级的待加工工序任务数大于1时,将此优先级别的工序任务合并为一个集合(视为一个新的虚拟工序任务类型),进入第2层规则调度。

根据待加工任务的排序结果,由高到低依次选取各个待加工任务,根据组合规则中的第2层调度规则进行工序方案的选定,即为当前可加工工序任务选择机器设备的过程。若最优级工序任务所需设备处在加工状态时,则选次优级工序任务,以此类推。若同一优先级工序任务所需的设备均处在加工状态的话,则将该优先级工件归入下一轮调度的待加工任务集。若同一优先级的工序方案数量大于1且工序所需设备均空闲时,则随机选择设备。

2.3 基于离差最大化原理的权重计算方法

2.3.1 离差最大化原理

假设属性权重向量为 ω=(ω1,ω2,…ωn),ωj≥0,j∈M,并满足单位化约束条件,则各方案的综合属性值可定义为:

多属性决策,一般是对这些方案综合属性值的排序比较,若所有方案在属性uj的属性值差异越小,则说明该属性对方案决策与排序所起的作用越小,反之,则说明其对方案决策将起重要作用[6]。

因此,从对方案进行排序的角度考虑,方案属性值偏差越大的属性应该赋予越大的权重。

根据上述分析,向量 ω的选择应使所有属性对所有方案的总离差最大。因此,属性uj的权重计算公式为:

2.3.2 权重计算方法

根据离差最大化原理,在调度方案的一组有效解中,若某一个性能指标在各个调度方案中的变化范围很小,表明现有的资源条件满足这个性能指标的能力相对稳定。那么调度方案的选择对该性能指标的影响较小,则该性能指标不应该成为判断调度方案优劣的主要指标,所以就不应该赋予其重要的权重。

依据此原理分析计算规则调度的结果,可以得到一组权重系数 ω(1),将该权重系数与专家系统给出的权重系数 ω(2)结合,取两者加权值之和作为衡量优化性能指标在目标函数中重要程度的量化标准。

ω既反映了生产系统的实际需求,又兼顾了现场生产资源状况满足系统需求的能力,可以较好地适应Job Shop生产车间柔性生产环境复杂多变的特点。

3 仿真结果与分析

为了验证基于规则组合的Job Shop多目标柔性调度方法的实用性和有效性,对Job Shop车间一个5类工件、5台机器的柔性调度问题进行研究,主要数据见表1所列。

其中,5类工件的交货期分别为[20 h 24 h 18 h 25 h 28 h]。运用本文的调度方法,运行时间为2 s,结果见表2所列。

表1 工序的加工时间、加工费用和相关数据

表2 规则组合调度结果

表2中,T(2)为加权延期和;T(1)为最大完工时间;C(1)为加工成本;C(2)为延误成本;Q为加工质量。

根据组合规则调度结果,结合专家系统给出的权重组合系数,运用离差最大化方法进行调度方案排序,分析结果如下:

考虑工件的加权延期和和延误成本和,规则组合调度结果得到的性能指标[T(1)T(2)QC(1)+C(2)]权重组合 ω(1)=[0.6664 0.0544 0.1735 0.1057],此时,专家系统给出的权重组合 ω(2)=[0.5 0.1 0.1 0.3]。实时工况要求在时间指标上主要强调工件的加权延期和最小,而非通常所要求的最大完工时间越短越好,因此,工件的加权延期和指标成为调度方案优劣性判断的重要依据。此外,在满足工件交货期要求的情况下,包含延误成本在内的成本指标成为评判调度方案优劣的另一个重要指标。

本文取2组权重平均值得到 ω=[0.5832 0.0772 0.1367 0.2028],根据ω计算得到调度方案排序为6-5-10-3-2-1-11-9-8-15-7-14-13-16-4-12,排序表明当前工况条件下方案6、5、10较优。其中加工成本最低的方案12的甘特图如图2所示,最大完工时间最短的调度方案7的甘特图如图3所示。