多目标柔性作业车间

2024-05-09

多目标柔性作业车间（共3篇）

多目标柔性作业车间篇1

0 引言

作业车间的调度问题一直是生产管理及组合优化等领域的热点之一。传统的作业车间调度(Job-Shop scheduling problem, JSP)的目标通常是求解一组工件的工序在一组机器上的分配。柔性作业车间调度问题(flexible Job-Shop scheduling problem, FJSP)是传统 JSP 的扩展,FJSP与JSP的不同之处在于:它假定工件的一个工序可以在不止一台机器上加工,从而增加了一个将每个工序分配到可以加工它的某个机器上的路径选择问题,使得 FJSP 成为比 JSP 更加复杂的一类组合优化问题。由于工件的工序具有多个可选择的加工路径,更加符合实际的生产环境,因此研究具有柔性路径的作业车间调度问题具有重要的理论价值和应用意义。

传统的FJSP研究主要集中在单目标调度上,近年来多目标FJSP问题由于更贴近实际生产需求而引起了人们更多的关注。多目标FJSP问题扩大了最优调度的搜索空间,而且需要满足更多约束条件,从而导致问题更加复杂,具有复杂性、约束多样性等特点。目前多目标柔性作业车间调度已有不少的研究成果:文献[1]建立了制造周期最短、机器总负荷和关键机器负荷最小的多目标仿真模型;文献[2]提出了一种改进遗传算法,采用了一种新的 GOR 编码、新的分类选择算子和改进的优先操作交叉算子集成设计方法;文献[3] 提出带瓶颈移动的混合遗传算法求解多目标 FJSP;文献[4]应用粒子群算法和禁忌搜索法求解多目标 FJSP;文献[5]提出采用粒子群和模拟退火混合算法求解多目标 FJSP。其中不少多目标优化的处理方法是采用线性加权的方式将多目标优化问题转换为单目标问题。多目标优化问题的特征之一是其解往往不止一个,而是一组在多个目标之间折衷的均衡解,即通常所说的 Pareto最优解。解多目标问题的关键是找到数量足够多且分布均匀的具有代表性的 Pareto 解。多目标进化算法采用模拟生物进化的交叉、组合、变异策略及基于适应度的选择机制,一次运行就能够得到分布均匀且逼近Pareto最优前沿。其中,强度Pareto进化算法(strength pareto evolutionary algorithm, SPEA)[6]在进化过程中保留了外部种群,能够有效控制Pareto前沿中个体的数量及其分布,但是在执行外部种群的缩减操作时,随着问题规模的增大,层次聚类方法的运算效率显著降低[7],而模糊C-均值聚类(fuzzy C-means clustering, FCM)[8]方法能够快速获得指定数目的聚类中心,具有较高的聚类效率,因此,本文将模糊C-均值聚类改进SPEA算法应用于柔性作业车间的多目标调度中。在满足加工能力、加工顺序、加工机器等约束前提下,对加工时间、加工成本和提前/拖期惩罚值多项目标进行优化,并使用基于集合理论的Pareto集选优机制排除人工选优的不确定因素。最后,通过项目应用,证明了改进的SPEA算法可以有效解决多目标柔性车间调度问题。

1 问题描述

多目标FJSP问题可以描述为:设存在M个工件,在N台机器上进行加工。每种工件Mi存在Ji道工序,工件的工序是预先确定的,每道工序可以在多台不同的机器上加工,在不同机器上各工件的工序加工时间和加工费用不同。设tijk为工件i的第j道工序在机器k上加工的时间,Sijk为工件i的第j道工序在机器k上开始加工时刻,Eijk为工件i的第j道工序在机器k上的完工时刻,Di为工件i的最晚交货期,D′i为工件i的最早交货期,ri为工件i提前完工的惩罚系数,wi为工件i拖期完工的惩罚系数,Rijegk表示在机器k上工件i第j道工序和工件e第g道工序的加工先后顺序,Xijk为决策变量,表示工件i的第j道工序是否选择在机器k上加工,则有:

$\begin{array}{l} R_{i j e g k} = {\begin{cases} 1 ⌶ 件 i 第 j 道 ⌶ 序和 ⌶ 件 e 第 g 道 ⌶ 序在 \\ 同一机器 k 上执行 ‚ 若 ⌶ 序 j 先于 ⌶ 序 g \\ 0 其他 \end{cases} \\ X_{i j k} = {\begin{cases} 1 若 ⌶ 件 i 第 j 道 ⌶ 序在机器 k 上执行 \\ 0 其他 \end{cases} \end{array}$

与传统的车间调度模型相比,FJSP模型增加了决策变量Xijk,即工件的工序可以选择在哪台机器上加工,该变量的增加提高了调度系统的应变能力,同时也大大增加了模型求解的复杂程度。调度目标是为每道工序选择最合适的机器,以及确定每台机器上各工件工序的最佳加工顺序,使系统的总优化目标达到最优。加工过程还要满足以下假设条件和约束条件:

(1)假设条件。①工序一旦进行不能中断;②所有机器一开始均处于空闲状态,在零时刻,所有的工件都可被加工;③不同工件的工序之间没有先后约束,工件之间具备相同的优先级;④各工件的准备时间和移动时间一起计入加工时间。

(2)约束条件。①顺序约束——工艺要求的同一工件相邻工序间的加工顺序不能颠倒,即

Eijk-Ei(j-1)k-tijk≥0 (1)

1<j≤JiXijk=Xi(j-1)k=1

②资源约束——同一机器k上一个加工任务完成后才能开始另一个加工任务,即

Eegk-Eijk-tegk≥0 (2)

Xijk=Xegk=1 Rijegk=1

本文中面向柔性作业车间的多目标优化调度考虑包含3个优化目标的优化目标集{T, C, D},T、C、D分别表示制造工期、加工成本和工件提前/拖期完工的惩罚值。其对应的优化模型如下:

(1)工件的制造工期T最短

$\min Τ = \max_{k = 1, 2, \dots, Ν} Ρ_{k} (3)$

式中,T为所有工件的最后完工时间;Pk为所有工件在机器k上的完工时间。

式(3)表示在机器k上的完工时间取决于在其上加工的所有工件中最后一个工件的完工时间。工件的制造工期包括工件的等待时间和工件的每道工序加工时间。每道工序加工时间Td包括工序的准备时间Tdp和工序的作业时间Tdj。准备时间Tdp包括准备专用工装夹具、安装调整工装夹具模具、检验时间等,工序的作业时间Tdj即机器加工工件的实际作业时间。工序的加工时间Td=Tdp+Tdj。

(2) 加工成本C最低

$\min C = \min \sum_{i = 1}^{Μ} \sum_{j = 1}^{J_{i}} \sum_{k = 1}^{Ν} C_{i j k} X_{i j k} (4)$

其中,Cijk表示第i个工件的第j道工序在第k台机器上的加工成本。加工成本可由工序费用来表示,工序费用指的是仅与加工机器有关的费用,产品材料费用的增减与加工机器无关或关系较小,所以不在工序费用之中考虑。工序费用Cd可分为机器成本Cdm和人工成本Cdh,其中机器成本Cdm包括机器的准备成本Cdp和作业成本Cdj,Cdm=TdpCdpt+TdjCdjt,其中Cdpt、Cdjt分别表示机器单位时间的准备费用和加工费用。人工成本Cdh=aTdjCdht,由于工序的作业时间Tdj与工人实际工作时间可能不一致,故设a为调整系数。由上可知工序费用Cd的计算公式为

Cd=TdpCdpt+TdjCdjt+aTdjCdht

(3)提前/拖期完工的惩罚值D最小

$\begin{array}{l} \min D = \sum_{i = 1}^{Μ} [r_{i} \max (0, D^{'}_{i} - E_{i J_{i} k})] + \\ \sum_{i = 1}^{Μ} [w_{i} \max (0, E_{i J_{i} k} - D_{i})] (5) \end{array}$

通过工厂日历、订单交货期和车间加工情况分析确定每个工件的最早交货期时间D′i和最晚交货期时间Di,同时根据工件的交货优先级确定不同工件的提前惩罚系数ri和拖期惩罚系数wi。

2 优化算法

FJSP多目标优化包括多个相互冲突目标同时优化,为了权衡生产管理的需要,需要得到Pareto最优解集而不是一个优化解。传统处理此柔性车间多目标调度优化问题的方法是通过权值的设定将多目标优化问题转化为单目标优化问题来解决的。为了获得多目标优化问题的Pareto最优解集,就必须求解一系列的单目标优化问题。强度Pareto进化算法保留外部种群存储运算过程中的非支配个体,基于Pareto支配计算个体适应度,并使用聚类方法缩减外部种群的数量,能够获得包含指定数目个体且分布均匀的Pareto前沿。因此,本文以SPEA算法为基础,引入模糊C-均值聚类算法加快外部种群的聚类缩减过程,并结合基于集合理论的Pareto综合选优机制,形成FJSP多目标优化方法。

2.1 算法概述

2.1.1 强度Pareto进化算法

SPEA由Zitzler等[6]于1998年提出,它采用了协同进化规则的适应度分配策略和基于 Pareto 支配关系的小生境机制,和其他多目标进化算法相比具有更强的优化能力。T(n)表示在规模为n的问题中算法基本操作重复执行的次数, f(n)是n的某个函数, T(n)=O(f(n)), O(f(n))为算法的时间复杂度。强度Pareto进化算法具有O(MN2)(M为优化目标个数,N为种群个数)的时间复杂性,能够通过聚类操作控制外部种群的数量并获得分布均匀的Pareto前沿,在工程优化领域已有不少研究。文献[9]将强度Pareto进化算法与并行遗传算法相结合,对火电站多目标负荷调度问题进行了求解;文献[10]采用多点交叉和Cauchy变异的方法对SPEA算法的收敛速度进行了改进,并对其收敛性进行了分析;文献[11]将强度Pareto进化算法应用于燃气涡轮的燃烧过程的多目标优化。

SPEA算法的流程如下:

(1)初始化。随机产生初始规则群体,构造一个空的外部群体。

(2)计算外部种群中个体的强度值,即该个体的适应度。此强度值与它所支配的内部种群个体数目成正比。内部种群个体的适应度是支配它的外部种群中所有个体的适应度之和。

(3)更新外部种群。在内部种群中查找非支配个体,并把它们复制到外部种群中。在外部种群中查找并删除劣势个体,如果外部种群中个体的数量超过了最大数量,则通过聚类方法缩减外部种群。

(4)组合内外种群的个体,采用联赛机制选择优势个体生成新的内部种群。个体适应度越小,则被选择的概率越大。

(5)检查是否达到最大循环代数,若没有达到则返回第②步,若达到则运算停止,获得Pareto最优前沿。

2.1.2 基于模糊C-均值聚类的外部种群缩减

模糊C-均值聚类[8]是一种被广泛使用的聚类方法,该算法是一种典型的基于划分的聚类算法,它的思想是使得被划分到同一簇的对象之间相似度最大,而不同簇之间的相似度最小。模糊 C均值算法是普通 C均值算法的改进,普通C均值算法对于数据的划分是硬性的,而FCM则是一种柔性的模糊划分,同时FCM算法占据O(N)的时空复杂性低于SPEA算法中使用的层次聚类方法(O(N2))。

设Y={y1,y2,…,yn}为未聚类的原始种群;n为原始种群中个体数目;Nc为聚类集合;c 为用户设定的模糊聚类集合的数目(c<n);m 为成员权重参数(m>1, 此处取m=2)。FCM算法流程如下:

(1)随机生成Y={y1,y2,…,yn}的模糊初始划分P(0)。

P(0)={A1,A2,…,Ac} (6)

其中,Ap(yq)表示个体yq对于每个聚类集Ap的隶属度,且满足:

$\sum_{p = 1}^{c} A_{p} (y_{q}) = 1 q = 1, 2, \dots, n (7)$

$0 < \sum_{p = 1}^{c} A_{p} (y_{q}) < n, \forall p \in Ν_{c} (8)$

(2)在循环中计算每个集合Ap(p=1,2,…,c)的c中心值:

$v_{p} (t) = \sum_{q = 1}^{n} [(A_{p} (y_{q}))^{m} y_{q})] / \sum_{q = 1}^{n} (A_{p} (y_{q}))^{m} (9)$

(3)从新的c中心值开始,更新聚类P(t+1):

若‖yq-vp(t)‖2>0,则

$A_{p}^{(t + 1)} (y_{q}) = [\sum_{j = 1}^{c} (∥ y_{q} - v_{p}^{(t)} ∥^{2} / ∥ y_{q} - v_{j}^{(t)} ∥^{2})^{1 / (m - 1)}]^{- 1} (10)$

若‖yq-vp(t)‖2=0,则

当p∈I⊆Nc时

$\sum_{p \in Ι} A_{p}^{(t + 1)} (y_{q}) = 1 (11)$

当p∈Nc-I时

$\sum_{p \in Ι} A_{p}^{(t + 1)} (y_{q}) = 0 (12)$

(4)如果|P(t+1)-P(t)|≤ε(ε为预先设定的值),则运算停止,获得聚类划分;否则,t←t+1,转步骤(2),继续运行。

模糊聚类运算完成后,保留与每个聚类中心最接近的个体,并删除原始种群中的其他个体,在保持原始种群分布性的前提下,获得包含指定数目个体的新种群。

2.2 算法设计

2.2.1 编码和解码

本文提出的柔性车间调度问题的解包含两方面的内容:任务的顺序和机器的选择。因此编码也要反映这两方面的内容,为此使用基于任务顺序和机器的选择两层编码方案[12]。第一层编码为各工序的优先权随机数(在[1,J]中产生,其中J表示总的工序数),第二层编码是各工序所选择的加工机器,在可供选择的机器中随机选出。

上述编码方案的解码主要是排定所有工序的加工顺序,在这里采用结合编码中各工序的优先权随机数对AOV(activity on vertex)网络图进行拓扑排序的方法。因为在拓扑排序过程中已经考虑了各工件工序的先后约束,所以得到的调度一定是可行的。

2.2.2 交叉与变异

交叉操作可以将父代的良好基因通过信息互换而产生更好的子代。由于模型中染色体编码的特殊性(具有两层编码),分别对每一层编码进行交叉操作。图1中交叉操作方法主要是采用从一个父代(如父代1)中随机挑选一个子序列复制到子代的相应位置的方法。为避免在第一层编码中产生不合法染色体,可以从父代2中移走在子代中已有的随机数3、1,同时将6、2、3、5依次放入子代中,如编码1中箭头所示。而对于第二层编码则可以将父代2的基因(除子代中已有的子序列外)直接复制到子代的相应位置,如编码2中的箭头所示。

变异操作仅对第一层编码进行变异,采用倒置变异的方法。如图1,对于父代1,将子序列中的随机数2、6反转得到4、1,从而得到新个体的第一层编码为5、6、4、1、2、3。

2.3 求解步骤

根据所建立的模型及FCM-SPEA算法,给出柔性车间多目标调度问题的求解步骤(设置内部种群规模N与外部种群规模 $\bar{Ν}$ ,设置种群最大迭代次数为T):

(1)令t=0, 随机生成初始群体P0,建立一个空的外部种群 $\bar{Ρ}_{0}$ 。

(2)计算内部种群Pt与外部种群 $\bar{Ρ}_{t}$ 中个体的适应值。

(3)将内部种群Pt与外部种群 $\bar{Ρ}_{t}$ 中的所有非支配个体复制到新一代外部种群 $\bar{Ρ}_{t + 1}$ 中。如果外部种群 $\bar{Ρ}_{t + 1}$ 中个体的数量超过了 $\bar{Ν}$ ,则对外部附属种群中的个体进行模糊C-均值聚类方法运算减少个体的数量;如果外部种群 $\bar{Ρ}_{t + 1}$ 中个体的数量都小于 $\bar{Ν}$ ,则将内部种群Pt与外部种群 $\bar{Ρ}_{t}$ 中的优良个体添加到新的外部种群 $\bar{Ρ}_{t + 1}$ 中。

(4)检查是否达到最大循环代数(t≥T)。若没有达到继续进行步骤(5);若达到则终止运算,获得Pareto最优前沿,并输出结果。

(5)通过复制外部种群 $\bar{Ρ}_{t + 1}$ 生成新的内部种群Pt+1。根据预先设定的交叉与变异概率对Pt+1中的个体进行交叉、变异操作,并令t←t+1,转到步骤(2)。

2.4 Pareto综合选优机制

FCM-SPEA求得多目标优化的Pareto集后,需要得到Pareto解的优先选择序列。由于人工Pareto选优存在多种不确定的主观因素,本文采用基于模糊集合理论的Pareto集选优方法[10],建立Pareto综合选优机制。定义成员函数δd表示一个解的第d个目标值所占的比重,则

$δ_{d} = {\begin{cases} 1 F_{d} \leq F_{d}^{\min} \\ \frac{F_{d}^{\max} - F_{d}}{F_{d}^{\max} - F_{d}^{\min}} F_{d}^{\min} < F_{d} < F_{d}^{\max} \\ 0 F_{d} \geq F_{d}^{\max} \end{cases} (13)$

式中,Fd为第d个目标值;F $_{d}^{\min}$ 、F $_{d}^{\max}$ 为第d个目标的最小值和最大值。

对于Pareto集中的每一个非支配解e,定义支配函数δ(e)为

$δ^{(e)} = \frac{\sum_{i = 1}^{Ν_{o b j}} δ_{i}^{(e)}}{\sum_{f = 1}^{Μ} \sum_{d = 1}^{Ν_{o b j}} δ_{d}^{(f)}} (14)$

式中,Nobj为优化目标的个数;M为Pareto集中解的个数。

δ(e)值越大表示该解的综合性能越好。将Pareto集按δ(e)值降序排列,即可得到解的优先选择序列,选择具有最大δ(e)值的解作为Pareto最优解。

3 实例应用与分析

该方法已在某机械公司ERP系统中的生产管理和柔性作业车间调度模块得到实际应用。系统采用Powerbuilder9.0,开发平台为C++、后台数据库为SQL SERVER2000,采用Client/Server架构。该模块的主要功能包括:柔性车间作业计划管理,工装机器管理,柔性车间工艺管理,柔性车间调度甘特图,工件生产进度查询等。

以该公司的模具车间为例,进行柔性作业车间多目标调度优化。该车间的主要机器包括车床、铣床、磨床、数控机床、加工中心等。通过对车间的工艺库和工艺卡管理来获取Tdp、Tdj、Cdm、Cdh等基础参数。对该车间数据进行计算处理后得到表1和表2:表1是调度问题的原始数据,包括工件的每道工序对应的机器的加工时间、加工成本;表2是工件交货期和提前拖期惩罚系数表。

以制造工期最短、加工成本最低及提前拖期惩罚最少为目标函数,进行柔性作业车间调度问题的多目标优化,多目标优化需保证Pareto前沿的收敛性和多样性特征。FCM-SPEA的内部种群提供多样化机制,而外部种群保留进化中的优势个体,并通过聚类缩减保证其分布性特征。本例中采用双层编码和进化算子,设置内部种群为100、外部种群数为30、最大运行代数为800、交叉概率为0.9、变异概率为0.1,10次实验运行均获得稳定收敛的Pareto前沿。

根据上文提出的模糊集合选优方法和管理人员所设定的决策指标范围进行Pareto选优,得到Pareto解的优先选择序列,选择具有最大δ(e)值的解作为Pareto集的最优解,如图3所示,图3中的数字表示工件工序号。为验证该算法在解决柔性车间多目标调度优化问题上的优越性,将该方法与传统的多目标加权方法、SPEA算法进行了计算比较。为了与加权系数法进行比较,采用文献[13]提出的方法,确定决策指标的权重w1=0.4,w2=0.35,w3=0.25,对得到的Pareto解集进行选优,通过计算可得到该权重下的综合最优方案。表3为应用本文的FCM-SPEA算法与传统加权系数法及SPEA算法各运行10次的对比结果。计算结果表明:FCM-SPEA算法比加权系数法计算时间少,解的性能更好;与SPEA算法相比,两种算法解的性能相当,但FCM-SPEA算法缩短了运算的时间。

4 结论

多目标柔性作业车间调度问题与传统的车间调度相比更符合实际的生产调度情况,对现实的车间调度更具有实际的指导意义。本文在构建柔性车间多目标调度优化数学模型的基础上,采用FCM-SPEA算法以制造工期、加工成本和交货期为目标对柔性作业车间调度问题进行多目标优化,并采用模糊集合选优方法进行Pareto选优,得到Pareto解的优先选择序列和一个最优解。最后将该方法应用于某制造车间调度中,通过与加权系数法和SPEA算法的比较,证明了该方法的有效性和适应性。

多目标柔性作业车间篇2

关键词：柔性作业车间,智能调度,多目标,调度资源信息

0引言

柔性作业车间调度问题 (flexible job-shop scheduling problem,FJSP)具有设备使用时间的限制及其生产能力的多样性,减少了机器约束,由此增加了可行解的搜索范围和问题求解难度,是一种比经典作业车间调度问题(job shop scheduling problem,JSP)更为复杂的NP-hard问题。目前,分支定界法[1,2,3]、枚举法等精确的优化调度算法仅能用于求解小规模柔性作业车间调度问题[4],而启发式人工智能优化算法 (如遗传算法[5,6,7,8,9,10,11]、蚁群算法[12,13,14,15]等)在求解柔性调度问题的近优解时,不受调度问题规模的限制,已成为目前算法研究的主要方向。对于实际调度问题中多目标的求解要求,通常采用群体进化算法求得Pareto解集,再由决策者依照调度要求和偏好进行选择,或是将多目标合成单目标评价函数进行优化[16,17,18]。上述方法均无区别地对待各个目标,因此大大增加了求解计算量,且由于需要决策者在决策环节手动选择,导致权值分配的优劣依赖于决策者经验。

柔性作业车间调度问题的求解方法可以分为分层法和集成法两种[19],其中集成法的算法过程相比分层法来说往往能获得更优的解,但是算法过程存在耦合,难以设计。分层法的思想在于通过将原来的整个问题进行分解来降低问题的复杂性,即首先考虑将特定工件的每道工序分配到一台合适的设备,再通过传统的作业车间调度方法进行求解。这种方法由于其快捷的求解速度和良好的求解效果得到了较为广泛的应用[20,21,22],但在用于某些复杂调度问题时,如需综合考虑特定调度期间、特定工件相关工序应采用的机器、特定机器的可工作时间、特定机器上先后加工的工件及其相应的工序等约束的问题,该方法并不能保证实现总作业时间最短、瓶颈设备不超负荷等多约束和多目标的工程要求。

本文研究分层蚁群-遗传混合算法的多目标优化策略及其智能寻优方法,根据现代柔性生产车间基于资源情况的相关车间实时信息,以最大完工时间、瓶颈机床负荷和机床总负荷为优化目标,旨在有效地解决现代柔性作业车间调度问题的实际工程问题。

1柔性作业车间调度问题描述

柔性作业车间调度问题的一般描述如下:该车间有m台机床{M1,M2,…,Mm}可使用,有n个工件{J1,J2,…,Jn}需要加工。每个工件含有一道或多道工序,工序加工的先后顺序为预先给定(如工件Jj的第x道工序为Ojx);其中每道工序可以在其可选机床集合中任选一台进行加工, 在不同机床上的加工时间也不同。调度问题的目标是为每道工序选择最合适的机床,确定每台机床上的最佳加工顺序及开始加工时间。

其他变量定义如下:TOj为第j个工件的总工序数;Ωjx为可用于加工第j个工件的第x道工序的机床集合;tijx为第j个工件第x道工序在机床Mi上加工的时间;Sjx为第j个工件第x道工序加工开始时间;Ejx为第j个工件第x道工序加工结束时间;Biy为机床Mi上第y个加工任务的开始时间;Oiy为机床Mi上第y个加工任务的结束时间;Cj为每个工件的完成时间;wijx为

上述调度问题中,基于资源情况的车间调度相关实时信息主要有以下三种:

(1)类型信息,即不同机床加工能力的差异性。多品种小批量生产车间内的机床之间往往在机床型号、适用范围、加工质量等方面存在较大的差异,其中,加工能力最强和适用范围最广的机床成为瓶颈机床的可能性很大。因此,对于加工要求不高或交货期非紧急的工件,应优先选择可用的非瓶颈机床进行加工。

(2)工况信息,即生产过程的动态性。在加工过程中可能存在工序紧急返修、工序插入、订单紧急变更等动态事件,导致一部分车间资源被临时占用。有些情况下,这种临时占用对调度计划的执行影响较小,可以忽略,但在有些情况下,这种临时占用会对原调度计划的执行产生严重影响。

(3)任务信息,即调度区间的灵活性。传统的柔性调度模型通常作如下假设:在零时刻所有机床可用于加工且所有工件可被加工。而在实际生产中,由于上一调度期的加工任务残留、部分机床故障维修等原因,部分机床并不能马上启动新调度期的加工任务。

2多目标柔性作业车间调度关键算法研究

2.1问题的假设与约束

在基于资源情况的多目标智能调度问题中, 除了要遵守一般调度问题的大多数假设和约束外,更重要的是,必须具有其特殊的假设和约束。

假设包括:

(1)在任意调度时刻,任意一台机床与任意一个工件相关,一道工序的加工与被加工关系是唯一的;

(2)任意进行中的工序或任务是不能被中断的;

(3)任意工件任意一道工序在相应机床上的工作时间是在调度前确定的;

(4)进入调度周期的工件,依据它们的完工时间目标和重要程度等要求,具有不同优先级。

约束包括:

(1)工件的工序约束。工件的工序约束保证任意工件多道工序的既定加工顺序,即工件j的第x道工序的开始时间Sjx必须等于或大于其前一道(x-1)工序的完工时间Ej(x-1):

(2)机床的任务约束。机床的任务约束保证任意机床多个加工任务的目标顺序,即机床i上的第y个加工任务的开始时间Biy必须等于或大于前一个(y-1)加工任务的完工时间Oi(y-1):

(3)资源的可用时间约束。可用时间包括:机床不处于维修或保养阶段;本调度周期内,机床不存在上一调度周期的剩余工序任务;毛坯或半成品已先于本调度周期前到达,且相关机床在上一调度周期未执行时段尚存空闲时间。

(4)任务的优先级约束。任务的优先级约束就是基于工序任务完工时间的目标要求、任务的重要程度等任务优先级计算及其优化的约束。

2.2调度优化模型

在实际生产中常采用周期性调度的方式来安排生产计划。每一次的周期性常态调度均采用基于资源情况的分层蚁群遗传多目标调度方法,包括资源数据分析、机床分配方案的选择、求非劣解和优化决策四个环节。通过分析当前最新的资源信息,明确资源可用时间约束。在每一次迭代运算中,选择机床分配方案;根据已选定的机床分配方案,求解得到多个非劣解,形成Pareto解集;最后根据多目标优化,对Pareto解集进行筛选,得到本次迭代中的最优解,以此指导下一次迭代运算。多次迭代后决策出的最终方案作为输出,下达生产任务,如图1所示。

生产计划的执行过程中,可能发生实际工时超出预计工时、紧急工件插入等影响车间资源的动态事件。当车间资源信息发生变化时,可用右移重调度方法进行处理。

本文研究的多目标柔性作业车间调度问题以三个目标作为性能评价指标:最大完工时间、瓶颈机床负荷和机床总负荷。使用时可根据需要,指定不同目标的优先顺序。

(1)最大完工时间makespan最短,即

(2)瓶颈机床负荷Wm最小,即

(3)机床总负荷Wt最小,即

2.3调度方法流程

基于资源情况的分层蚁群遗传多目标柔性作业车间调度算法 (hierarchical ant-genetic algorithm based and resource-driven multi-objective scheduling method for flexible job shop,MoSMRFJ)的主要步骤如下:

(1)根据车间内的机床数据库、刀具数据库等基本数据库的数据,更新资源信息库。从资源信息库中读取相关的基本信息,确定待调度工件集 {J1,J2,…,Jn}、加工机床集{M1,M2,…,Mm}、机床可用时间表{t1,t2,…,tm}以及工件工序在不同机床上的加工时间集{tijx|Mi∈Ωjx,i=1, 2,…,m,j=1,2,…,n,x=1,2,…,TOj};将调度基本信息转化为算法可识别的输入,确定优化目标、优先级顺序 {Obj1,Obj2,…,Objs}(按优先级从高到低排列)。

(2)初始化算法参数。蚁群算法的部分主要参数参考文献[23]中的参数设置,即信息重要程度参数α =10.0,启发式因子重要程度参数β= 10.0,信息素挥发率ρ =0.01,信息素增强系数Q =6。对于迭代次数N和蚂蚁数量na,则需要根据多次试验和总运算时长限定等方法确定。 NSGA -Ⅱ算法的参数使用文献[24]的参数推荐值,即种群数量popSize = 20, 迭代次数maxGen=30,选择率Ps=0.1,交叉率Px=0.6, 变异率Pm=0.1,最优前端个体系数pf=0.3。在不考虑计算时间的条件下,默认值为:工件数n≤ 10时,采用文献[25]中推荐的N =25和na=10; 工件数n>10时,采用文献[25]中推荐的na= 20,根据多次试验所得到的历代最优解收敛图可知,各案例迭代70代以后基本趋于稳定,取N = 70。

(3)在第k次迭代过程中,对于选定的机床分配方案,使用NSGA?Ⅱ算法求非劣解,得到非劣解集(即Pareto解集);然后通过考虑多目标优先级顺序的优化准则对Pareto解集进行依次筛选,将得到的解加入优化解集X。

(4)根据步骤(3)中的优化结果,指导下一次的迭代计算过程。

(5)迭代次数达到预设的N,停止计算,以同样的优化策略对多次迭代所得优化解集X进行筛选,得到的调度方案以表格和甘特图的形式输出,下达生产线。

MoSM-RFJ算法的工作流程如图2所示。

3案例测试结果

3.1标准案例测试

为验证MoSM-RFJ算法的优化效果,使用标准库的FL4 × 6、FL5 × 6、FL15 × 10、 MK01(10×6)、MK04(15×8)、MK05(15×4)、 MK07(20×5)和MK09(20×10)8个典型案例进行测试,并与文献[26]中MOGV算法的求解结果进行对比。为方便对比,测试均在标准案例条件(全部机床可启动时间从零时刻开始)下进行。令:目标的优先顺序为makespan、Wm、Wt,即以最大完工时间最短为首要寻优目标。测试结果显示,62.5% 的案例计算结果等同MOGV算法, 25%的案例(MK01案例和MK07案例)计算结果优于MOGV算法,12.5% 的案例计算结果劣于MOGV算法。其中MK01案例和MK07案例的调度结果对比如表1所示。表1中的变化量为MoSM-RFJ算法与MOGV算法进行比较的目标值变化百分比,正数代表MoSM-RFJ算法得到的对应目标值高于MOGV算法得到的对应目标值,负数代表MoSM-RFJ得到的对应目标值低于MOGV算法得到的对应目标值,0代表两种算法的结果持平。

与MOGV算法相比,MoSM-RFJ算法可以有效地取得对指定优先目标的最佳优化效果,第一优化目标的比值≤第二优化目标比值≤第三优化目标比值。MK01案例计算结果的甘特图见图3。

3.2组合案例测试

为验证MoSM-RFJ算法的优化效果,组合FL5×6案例和MK01案例进行测试,两个案例中的机床数均为6。每一个案例作为单个调度周期的调度任务。在特定调度周期内,若机床残留上一调度周期的剩余工序任务,则该机床应先完成上一调度周期的残余任务,再开始本调度周期的工序任务;若毛坯或半成品先于本调度周期到达,且相关机床在上一调度周期未执行时间存在空闲时间,则应提前开始相关工序任务。相邻调度周期间存在机床可用时间互补,如图3和图4所示。令第x-1个调度周期的资源信息为:全部机床从零时刻起可用。其中组合案例1指先MK01案例后FL5×6案例,组合案例2为先FL5×6案例后MK01案例。图3、图4中,竖直粗点划线左侧为第x-1个调度周期,右侧为第x个调度周期。细实线表示第x-1个调度周期内的工序任务,粗虚线表示第x个调度周期内的工序任务。

由图3和图4可知,标准案例条件下,MK01案例的最大完工时间makespan为42,FL5×6案例的makespan为27。组合案例1的makespan为66,组合案例2的makespan为68,均小于两案例的makespan之和69。可以预见,多个调度周期后,makespan的缩短会越发明显,有利于生产实际中节约时间成本。

3.3动态案例测试

以MK04(15×8)案例为例,考虑紧急任务插入情况的测试结果如图5所示。机床可启动时间为零的初始调度方案如图5中粗虚线所示。现假设:原定于在M5上15~20时段进行工件8第2道工序的加工,图中表示为(8,2),计划工时t825= 20-15=5,但是在t1=15时刻发生了紧急任务插入的动态事件,使得该加工任务在t2=20时刻才开始进行,而实际加工工时较计划工时延长3, t′825=5+3=8。该动态扰动事件导致原定加工任务(8,2)延迟的时间一共为:td= (t2-t1)+ (t′825-t825)=5+3=8。运用右移重调度算法对初始调度方案进行修正,修正后的调度方案如图5中细实线所示。

可以看出,t1=15时刻后,仅有受影响的工序被无间隙顺延,其他不受影响的工序不变(粗虚线与细实线重合 ), 该动态扰动事件导致makespan延迟的时间Td= makespan′ makespan=68-66=2<td=8。

3.4算法效率分析

算法的运算时间Ts包括执行蚁群算法的时间和执行NSGA?Ⅱ算法的时间。而遗传算法每次迭代的时间较短,相较于前者可以忽略[27]。多次试验发现,蚁群算法中每次迭代中每只蚂蚁的寻优平均时间ta与调度问题的规模大小有关,如表2所示。寻优平均时间首先与工件数成正相关,在同样工件数量的条件下,其与机床数成正相关,即同批调度的工件数量是影响寻优时间的主要因素。解决对运算时间Ts有要求的问题时,对于工件数较多的情况,应适当选取较小的迭代次数N和蚂蚁数量na,对于机床数较多而工件数相对不多的情况,可适当增大迭代次数N和蚂蚁数量na。

4小结

本文针对基于车间调度相关实时信息的多目标调度,研究和实现了分层蚁群-遗传混合算法的多目标智能寻优方法,在标准案例测试下,取得了比较理想的多目标调度结果:25%的案例计算结果优于MOGV算法,第一优化目标makespan减小了5% ~7%,62.5% 的案例计算结果等同MOGV算法,12.5% 的案例计算结果劣于MOGV算法。在实际的连续生产中,基于上一调度计划或正在执行的上一调度计划剩余或空闲资源等启发式知识,该智能调度方法的优化效果更为显著。该智能调度方法不仅可以有效地取得对指定优先目标的最佳优化效果,且可自动获得多目标综合的最优解而无需决策者确定不同目标的优先权比值。

多目标柔性作业车间篇3

车间作业调度问题(Job Shop Scheduling Problem,JSSP)实际上是一个资源分配问题,问题的求解目标主要是找到一个键一组资源安排到设备上去,以使作业可被“最优”到完成的方案,通常JSP约束条件很多,使得JSP成为一个非常难解的NP完全问题,不但它的算法复杂性呈指数增长,而且没有一个有效的通用的调度算法用于求解通用目标函数的JSP问题。柔性作业车间调度问题突破了资源唯一性限制,每个工序可由多个不同的机器完成,从而使作业车间调度问题更加符合生产实际,所以相对经典作业车间调度问题而言柔性作业车间调度更加复杂。

2. 柔性车间作业调度问题概述

2.1 柔性车间作业调度

FJSP问题描述如下:

车间配有m台机要加工n种工件,每种工件都由nj个工序组成,总工序数为:

我们用Oij代表工件Jj上的第i个工序。工件的工序是预先确定的,每道工序可以在多台不同的机床上加工。最终目的是确定每道工序的加工顺序和加工机器,使系统的以下各目标最小。

F1:制造周期(各机器最大完工时间)

F2:机器总负载(各机器总的加工时间)

F3:关键机器负载(加工时间最长的机器负载)

加工过程还需满足以下约束条件:

同一时刻同一台机器只能加工一个零件;每个工件在某一个时刻只能在一台机器上加工,不能中途中断;同一工件的工序之间有先后约束,不同工件的工序之间没有先后约束;不同工件具有相同的优先级。

3. 改进的粒子群优化算法

3.1 微粒群优化算法的算法原理

假设在一个n维的目标搜索空间中,有m个粒子组成一个群落,其中第i个粒子表示为一个n维的向量Xi(Xi1,Xi2,Xi3,…,Xin),i=1,2,…,m,即第i个粒子在n维空间中的位置是Xi。将Xi代入一个目标函数就可以计算出其适应度值,根据适应度值的大小衡量Xi的优劣。第i个粒子的“飞翔”速度也是一个n维的向量,记为Vi(Vi1,Vi2,Vi3,…,Vin)。记第i个粒子迄今为止搜索到的最优位置为Pi(Pi1,Pi2,Pi3,…,Pin),整个微粒群迄今为止搜索到的最优位置为Pg=(Pg1,Pg2,…,Pgn)。Kennedy和Eberhart最早提出的PSO算法采用下列公式对粒子操作:

其中,i=1,2,…,m,d=1,2,…,n;学习因子C1和C2是非负常数;Rand()和rand()是介于[0,1]之间的随机数。定义g为全局极值或局部极值的子序号,同时,定义公式中的上标表示迭代的次数,则微粒根据如上的公式来更新自己的速度和位置。其中,d=1,2,…,n;i=1,2,…,N;k=l,2,…;k为迭代次数;N为种群大小。

3.2 对PSO的改进

惯性权重是关系到粒子群优化算法搜索能力的重要参数。一个大的惯性权重值有助于搜索一个新的区域,而一个小的惯性权值有助于在当前区域自习搜索。传统的惯性权重值计算公式如下:

惯量W:权重函数W由下式来确定:

但这种做法的缺点是,需要通过反复试验来确定惯性权重的最大值、最小值以及最大迭代次数,且很难找到适应于不同问题的最佳值。

考虑到PSO算法在解空间寻优的过程本身就是一非线性运动过程,为了平衡算法的全局搜索和局部改良能力,本文把非线性的自适应调节惯性权因子方法运用到解决多目标柔性车间问题中,使惯性权系数随微粒目标变化而自动改变。自适应惯性权系数的表达式为:

其中,Wmax和Wmin分别代表W的最大和最小值,f为粒子当前的目标函数值,favg和fmin分别为所有微粒的平均和最小值。对于目标值由于平均目标值的微粒,将对应于较小的惯性权因子,从而使该微粒得以保护;而对于目标值差与平均目标值的微粒,将对应于较高的惯性权因子,从而使该微粒能够更快地趋向较好的搜索空间。

4. 改进的微粒群优化算法及其在多目标柔性车间调度问题中的应用

4.1 适应度函数的确定

本文随机产生权系数,使同一代种群的不同粒子使用不同的权系数来计算各自的适应度值。

本文所求的多目标柔性作业车间调度问题可以用下面的函数求适应度:

其中i=1,2,3.ri是随机产生的。F1:制造周期(各机器最大的完工时间)。F2:机器总负载(各机器中的加工时间)。F3:关键机器负载(加工时间最长的机器负载)。

4.2 算法流程

根据前面的叙述,我们可以得到面向柔性工作车间调度问题的粒子群算法,算法具体步骤如下:

(1)初始化粒子群。

(2)根据适应度函数评价所有粒子,寻找各子群内的最优解pbest和总群体内最优解gbest。

(3)对每一个粒子,按公式1、公式2和公式4计算速度向量。

(4)若某个粒子的当前适应度优于其历史适应度,则记当前适应度为历史最优适应度,同时记当前位置为该粒子历史最优位置。

(5)寻找当前各子群内最优解和总群体内最优解,若优于历史最优解则更新pbest和gbest。

(6)迭代次数小于规定迭代次数,跳转到(3)。

(7)结束,输出最优解。

4.3 仿真结果分析

分别选用典型Job shop调度问题中的3×3和8×8作为两个粒子群优化算法的仿真实验实例,其中的相关参数见表1,初始解都是随机产生的,最大代数为2000,本文分别从制造周期和机器总负载来说明优化的微粒群算法在解决多目标柔性作业车间调度问题上的有效性。

根据相应的参数,使用微粒群优化算法解决3×3问题的结果如下:

图1为程序迭代40次时求解3×3问题时产生的最优解示例图。

上述机器总负载为23,制造周期为9。

下面在以8×8问题进行分析,表2给出了工件工序在各个机器上的加工时间。

微粒群优化算法参数如下:

根据相应的参数,基于微粒群优化算法解决8×8问题所得的结果如下:

图2为程序迭代1000次时求解8×8问题时产生的最优解示例图。

上述机器总负载为76,关键机器负载为13。

4.4 结果分析

本文也是采用了对3×3和8×8问题进行分析研究,并且和其它算法做了对比。

不同优化算法求解3×3和8×8问题所得目标函数值的比较如下表3、表4所示:

通过上面两个表的对比可以得出:

改进PSO算子优化算法和GA相比:使用微粒群算法自适应算子解决制造周期和机器总负载等问题上和GA算法相比具有一定的优势。

PSO改进算子算法和PSO相比:PSO改进算子算法在解决多目标柔性作业车间调度时,虽然机器总负载比PSO算法在解决此问题时要稍微多一些,但是工件的制造周期要小一些。通过查资料发现:大部分的车间在加工工件时,除了加工工件所必须的材料外,相当大的一部分功耗来源于用电量的消耗,一般情况下这一部分消耗占到了80%以上。而电的消耗主要来源于电机的功耗,电机在空载时的电流是在负载时电流的30%~70%(视不同类型的电机而变化),即电机在负载时和空载时的功耗之比在10/3和10/7之间。下面以3×3问题为例说明PSO自适应算法和PSO相比在解决多目标柔性作业车间调度时的优越性,在此电机的空载和负载的功耗之比选择最大值10/3。由表3可以看出PSO自适应算子优化算法比PSO算法的制造周期少2个,那么3台机器就少2×3=6个,而机器总负载PSO自适应优化算法比PSO多1个,此时6-1×10/3+1>0,所以总的来说PSO自适应算子优化法比PSO在求解多目标柔性作业车间调度问题时的效果更优越。同理在求解8×8问题时可以得到相同的结论。

PSO改进算子优化算法和PSO、SA混合算法相比:在求解3×3和8×8问题时,由表3和表4所得,由于6-2×10/3+1>0,16-2×10/3+1>0,可以得出在求解多目标柔性作业车间调度时,PSO自适应算子优化算法比PSO、SA混合算法更有效。

5. 结语

调度的优化准则中,基于性能的指标研究较多,基于代价指标的研究很少,少量文献涉及到成本,而本文在研究多目标柔性作业车间调度问题时有所涉及。

随着柔性作业车间调度问题的日益发展和粒子群优化算法的不断深入研究,在对参数优化的基础上,如何建立包括生产成本在内的多目标柔性作业车间调度模型,充分考虑企业对成本的关注,使得调度模型更好的反应现实情况,将是该问题发展的一个重要方向。

摘要：多目标柔性车间作业调度问题(JSP)是一类更为复杂的典型调度问题,也是一个典型的多目标优化问题。微粒群优化算法是一个通过不断迭代得到最优解的算法。本文提出了改进的微粒群优化算法,并且利用它来解决多目标柔性车间作业调度问题。通过仿真结果可以发现在利用改进的微粒群算法解决多目标柔性车间作业调度问题时有优异的表现。

关键词：作业车间调度,微粒群算法,多目标,优化算法,柔性

参考文献

[1]孙志峻,朱剑英.具有柔性加工路径的作业车间智能优化调度[J].机械科学与技术,2001.

[2]潘全科.智能制造系统多目标车间调度研究[D].南京:南京航空航天大学,2003.

[3]谢涛,陈火旺,康立山.多目标优化的演化算法[J].计算机学报,2003.

[4]崔逊学.目标进化算法及其应用[M].北京:国防工业出版社,2006.

[5]周济,查建中,肖人彬.智能设计[M].北京:高等教育出版社,1998.

【多目标柔性作业车间】推荐阅读：

目标区间08-02

多指标多目标决策09-17

多目标模型05-08

多目标法05-25