作业车间调度

2024-06-10

作业车间调度（共9篇）

作业车间调度篇1

当前随着信息技术的发展,世界制造业企业能否快速地响应市场,是企业能否在市场竞争中生存的关键。生产调度是制造业最重要的技术之一,作业车间动态调度(Job Shop Scheduling Problem)技术可以大大提高企业的生产效益,具有重要的研究意义[1]。

研究了如何应用微粒群优化算法求解生产动态调度问题。首先介绍作业车间动态调度问题的特点和建模方法。然后介绍多微粒群优化算法的基本原理。继而阐述了多微粒群协同优化算法的设计方法。最后分析了求解JSP问题的多微粒群协同优化算法的仿真实验结果,验证了算法的可行性和有效性。

1 动态调度问题

作业车间调度问题的特点是多个工件在有限的机器上加工,不同的工件在相同的机器上进行加工切换时需要一定的准备时间[4]。如果切换加工次数频繁,有利于减少工件的库存,但导致生产率下降。因此,需要在库存成本和工件切换加工频率之间取得平衡。

生产调度问题一般可以描述为:n个工件在m台机器上加工,一个工件分为k道工序,每道工序可以在若干台机器上加工。每一台机器在每个时刻只能加工某个工件的某道工序,只能在上道工序加工完成后才能开始下一道工序的加工,前者称为占用约束,后者称为顺序约束[1]。车间调度问题的决策内容包括分配决策(工件的加工顺序)和时间决策(工件各工序的加工时间)以及路径决策(工件工序的加工设备的分配)。

生产调度分为动态调度和静态调度两大类[5]。静态调度是在已知调度环境和任务的前提下而进行所谓的事前调度方案。

动态调度是指再调度环境和任务存在着不可预测的扰动情况下的调度方案,它不仅依赖于事前调度环境和任务,而且与当前状态有关。

2 多微粒群优化算法

受鸟群运动模型的影响,美国心理学博士James Kennedy和电子工程学博士Russen Ebethart于1995年提出了微粒群算法(Particle Swarm Optimization,PSO)。微粒群算法是一种演化计算技术,该算法中将鸟群运动模型中的栖息地类比于所求问题解空间中可能解的位置,通过个体间的信息传递,导引整个群体向可能解的方向移动,在求解过程中逐步增加发现较好解的可能性,如图1所示。

3 多微粒群协同优化算法设计

3.1 编码策略

采用基于任务的编码方式[3],将每个工件看成一个任务,不妨假设共有3台机器,生产4种产品,每种产品的需求数量分别为{2,3,3,3},则确定编码长度为11=(2+3+3+3),具体方式如表1所示。

表1中,任务序号和X(生产产品种类)都是固定值,表示将每个工件的生产看成一个任务。任务序号2代表第二个任务是生产第一种产品。Y则是随机生成的机器机台号,是将生产任务对应到机台。

3.2 解码策略

当X的值固定后,随机生成Y,进行任务指派,对应地可以清晰地明确每台机器上的生产任务,例如表1中,机器1的生产序列为2,4,由于并行多机之间存在等同性和非等同性,每台机器生产每种产品的生产时间和生产过程中产品切换的换模时间是可知的,因此就可以确定机器1的完工时间T为

其中,t(i,j)为机器i生产产品j的生产时间,c(i,j,k)为机器k上由产品i转换到产品j的换模时间。同理我们可以完成对机器2,机器3的解码,综合以上就可以知道对应Y这个调度结果所有需求产品都生产完毕的完工时间。

3.3 机器故障的预调度、再调度设计

首先,生产车间接到订单任务,由优化算法进行预调度,同时估计最早完工时间,计算提前/延期惩罚成本,结合人工经验对自动优化结果进行调整,下达任务至机台。当有机器故障时,废除该机器正在生产的产品,同时统计其余机器在产任务的最早完成时间作为标定再调度起始时间,按照该时间进行剩余任务的再优化排产,估计最早完工时间,计算提前/延期惩罚成本,结合人工经验进行任务调整。若有故障机器复工时,则统计其他机器在产任务的产品类别,确定剩余任务数量,并重新标定再调度起始时间,计算最早完成时间及各惩罚成本。

3.4 仿真实验分析

根据车间作业动态调度的需求,结合上述微粒群优化算法设计,设置了以下实验参数。其中,T为各个工件的工序的加工时间,表示为时间矩阵,Jm为各工件的各个工序使用的机器,表示为机器矩阵,种群数为40,最大迭代次数为200次。

按照上述的实验参数,在Matlab上运行了设计实现的微粒群算法,得到以下实验结果。其中,图2所示算法求解出的每一代最优解和种群均值的变化趋势图,图3显示了算法执行到第200代时得出的最优解所对应的调度甘特图。

从图2中可以看出,微粒群优化算法求解出的最优调度方案所需的最小最大完工时间是1110。为了形成对比,特修改程序的参数如下:种群的数目为300,最大迭代次数仍为200次,且

按照上述的参数设置,得到了如下的实验结果。其中图4表示种群数为300时的最优解和种群均值的变化图,图5为对应迭代到200代时的甘特图。

从图5中可以看出,微粒群优化算法求解出的最优调度方案所需的最小最大完工时间是987。通过实验对比,得出以下结论:随着种群数的增加,微粒全算法求解出的最优调度方案所需要的最小最大完工时间呈现出越小的趋势,并且多微粒群协同优化算法的收敛速度较标准微粒群优化算法快,收敛效果明显优于标准微粒群算法。多微粒群协同优化算法在寻优过程中能够跳出局部极值点,有利于产生最优解,并且当规模扩大时,基本微粒群算法还能够保持较高的搜索效率,且收敛速度快,收敛性能稳定。

参考文献

[1]熊锐,吴澄.车间生产调度问题的技术现状与发展趋势[J].清华大学学报(自然科学版),1998,38(10):55-60.

[2]唐宇.基于微粒群算法的车间调度问题研究[D].浙江工业大学,1997.

[3]张其松,陈建行.一种基于微粒群算法的车间作业调度方法[D].同济大学电子与信息工程学院,2008.

[4]常桂娟,张纪会.基于微粒群算法的车间调度问题研究[D].青岛大学,2008.

[5]常建娥,张磊.协同PSO算法在Job-Shop调度中的应用[D].武汉理工大学,2010.

作业车间调度篇2

姓名：陈凯

学号：541413430202

地点：四教楼301

指导老师：张旭

专业班级：嵌入式软件14-02

实验名称：短作业优先调度算法

一、实验目的：

测试数据可以随即输入或从文件中读入。必须要考虑到作业的到达时间

最终能够计算每一个作业的周转时间。

二、实验内容：

模拟实现短作业调度算法，具体如下：

设置作业体：作业名，作业的到达时间，服务时间，作业间的链接指针进程初始化：由用户输入作业名、作业的到达时间和服务时间进行初始化。显示函数：

1、显示当前调度的是哪个作业，后备队列中有哪些作业

2、最终显示每个作业的作业名、到达时间、服务时间、完成时间和周转时间

排序函数：对就已到达的作业按照服务时间进行排序。注意考虑到达时间调度函数：每次从已到达的作业队列队首调度优一个作业执行。删除函数：作业结束后撤销。

三、实验代码

#include structsjf //定义进程的结构体 {

char name[10];//进程名

floatarrivetime;//到达时间

floatservicetime;//服务时间

floatstarttime;

//开始时间

floatfinishtime;//完成时间 floatzztime;//周转时间 floatdqzztime;

//带权周转时间 };

sjf b[100];

//定义短作业优先算法进程的最大数量 voidSinput(sjf *p,int N)

//输入函数 { int i;

printf(“输入进程的名称、到达时间、服务时间:n”);for(i=0;i<=N-1;i++){

printf(“输入第%d进程的名称、到达时间、服务时间:”,i+1);scanf(“%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);} }

//输出函数 voidSPrint(sjf *p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floatzztime,floatdqzztime,int N){ int k;

printf(“n执行顺序:n”);printf(“%s”,p[0].name);

for(k=1;k

{

printf(“-%s”,p[k].name);}

printf(“n进程名tarrivetservicetstarttfinishtzztdqzzn”);

for(k=0;k<=N-1;k++)

{

printf(“%st%-.2ft%-.2ft%-.2ft%-.2ft%-.2ft%-.2ftnn”,p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime);

} }

voidSsort(sjf *p,int N)

//按短作业优先算法排序 {

for(int i=1;i<=N-1;i++)for(int j=1;j<=i;j++)

if(p[i].servicetime

sjf temp;temp=p[i];

p[i]=p[j];

p[j]=temp;} }

//运行结果 voidSdeal(sjf *p, float arrivetime,floatservicetime,floatstarttime,floatfinishtime,float&zztime,float&dqzztime,int N){

int k;

for(k=0;k<=N-1;k++)

{

if(k==0){

p[k].starttime=p[k].arrivetime;

p[k].finishtime=p[k].arrivetime+p[k].servicetime;

} else {

p[k].starttime=p[k-1].finishtime;//开始时间=前一个进程的完成时间

p[k].finishtime=p[k-1].finishtime+p[k].servicetime;

//结束时间=前一个进程的完成时间+现在进程的服务时间 }

}

for(k=0;k<=N-1;k++){

p[k].zztime=p[k].finishtime-p[k].arrivetime;

//周转时间=完成时间-到达时间

p[k].dqzztime=p[k].zztime/p[k].servicetime;

//带权周转时间=周转时间/服务时间 } }

void SJF(sjf *p,int N){

float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;

Ssort(p,N);

Sdeal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);

SPrint(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);}

void main()//主函数 { int M;printf(“------------短作业优先调度算法-----------n”);printf(“输入作业数:”);scanf(“%d”,&M);

Sinput(b,M);SJF(b,M);}

四、实验结果

五、实验总结

基于改进遗传算法的作业车间调度篇3

作业车间调度问题 (Job shop scheduling problem, JSP) 是一个非常典型的NP难优化问题。要使得各调度指标 (成本最低、最大加工时间最小、机器利用率最高等) 最优, 求解方法极为重要。

近几年, 遗传算法的应用最广。例如:韦尧兵等[1]提出通过设定种群过早收敛指标来解决遗传算法的早熟收敛问题;万敏等[2]引入自适应交叉概率和变异概率因子;王秋芬等[3]提出一种基于两层采用自然数编码遗传算法的车间调度算法。尽管JSP的研究已取得了一定的成果, 但遗传算法求解容易陷入局部最优等问题还有待于进一步研究。

1 作业车间调度优化模型

作业车间调度问题可描述为:N个工件在M台机器上加工, 每个工件由若干道工序组成, 各个工件在各台机器上的加工时间已知, 各个工件在各台机器上的加工次序也已知, 要求确定各台机器上工件的加工次序, 使预先设定的调度指标达到最优。

1.1 约束条件

约束条件如下: (1) 一个工件同一时刻只能在一台机器上加工; (2) 一台机器在同一时刻只能加工一个工件; (3) 一旦某一工件在某台机器上开始加工就不能中断, 直到该工序加工完成; (4) 一个工件的前一道工序加工没有完成, 不能加工下一道工序; (5) 加工同种工序的机器唯一, 机器不可选; (6) 工序的加工机器和时间确定, 在加工过程中不会变化。

1.2 调度目标数学模型

1.2.1 JSP变量定义

JSP变量定义如下:

(1) N:工件数量。

(2) M:机床数量。

(3) n:工序个数。

(4) 工件集合用数组J表示, J={J1, J2, …, Jj}, Jj为第j个工件, j=1, 2, …, N。

(5) 机床集合用数组JM表示, JM={M1, M2, …, Mk}, Mk为第k个机床, k=1, 2, …, M。

(6) 对应工序所用的加工机床为Mkj (1) , Mkj (2) , …, Mkj (n) , 则机床的加工顺序矩阵为JM:

其中:Mkj (n) 表示工件j的第n道工序在机床Mk (k=1, 2, …, M) 上加工。

(7) 加工时间集合用二维数值TJM表示:

其中:Tkj (n) 表示第j个工件的第n道工序在机床Mk上的加工时间。

(8) tjk表示工件j在机床k上的加工时间。

(9) cjk表示工件j在机床k上加工的完成时间。

(10) A表示一个值较大的正数。

(11) 若工件i先于工件j在机床k上加工, 则xijk=1, 否则xijk=0;当机床h先于机床k加工工件i时, aihk=1, 否则aihk=0。

1.2.2 数学模型

本文以最大完工时间最小为调度目标, 即从工件开始加工一直到工件的每道工序加工完成所用的全部时间最小。目标函数为:

约束条件为:

式 (2) 保证工件的每道工序同一时刻只能在一台机器上加工;式 (3) 保证一台机器在同一时刻只能加工一个工件;式 (4) 和 (5) 是参数的取值范围。

2 算法设计

2.1 染色体编码

根据车间预设的调度目标, 采用基于工序的编码方法, 其可确保染色体的合法性。基于工序的自然数编码方法, 编码得到的染色体数等于工序总数, 每个工件的工序都用对应的工序号表示, 并且工件的工序号出现的先后次数代表该工件工序加工的先后顺序。根据工件序号在染色体中出现的次序, 从左到右依次遍历染色体。

对于第m次出现的工件序号, 表示该工件的第m道工序。以4×3 (4表示工件, 3表示工序) 的Jobshop为例:一组染色体为[2 1 3 2 4 3 1 4 3 2 1 4], 其中1第一次出现表示工件J1的第1道工序, 1第二次出现表示工件J1的第2道工序, 1第三次出现表示工件J1的第3道工序;染色体2, 3, 4同理。

2.2 遗传算子设计

2.2.1 交叉操作

在遗传算法中, 交叉操作是产生新个体的主要途径, 也是父代遗传特性得以继承的关键, 同时交叉操作还可确保遗传算法的全局搜索能力[4,5,6,7], 目前求解易陷入局部最优, 求解质量的问题没有得到很好的解决, 所以本文在交叉算子设计时引入禁忌搜索算法, 利用禁忌表对交叉过程重复产生的子代进行有效禁忌, 以加快算法的收敛速度, 提高算法的全局搜索能力。

禁忌搜索算法的交叉算子是通过在原有的交叉算子设计方法的基础上引入禁忌搜索的一个长度为L的禁忌表来保存染色体。交叉操作采用POX (precedence operation crossover) [8]方法。

POX的具体交叉过程如下:设4×3调度问题的两个父代个体分别为parent1和parent2, POX交叉生成offspring1和offspring2。把工件集随机分成2个集合Jobset1={2, 4}和Jobset2={1, 3}, offspring1和offspring2分别继承parent1和parent2中包含在Jobset1中的工件且保持位置不变, 将parent1和parent2中包含在Jobset2的工件分别复制到offspring2和offspring1, 且保留其位置顺序, 从而产生新个体offspring1和offspring2, 如图1所示。

改进交叉算子的具体步骤如下: (1) 初始化禁忌表, 禁忌表长度为L, 设为空; (2) 在初始种群中随机地选择两个个体根据交叉方法和交叉概率进行交叉操作, 得到两个子代新个体; (3) 将子代新个体1放入禁忌表中; (4) 判断子代新个体2是否在禁忌表中, 若不在则从左向右依次放入禁忌表; (5) 若禁忌表已满, 则将最早放入的个体解禁, 即从右向左依次顺序移动; (6) 更新禁忌表; (7) 再将禁忌表中的个体放入子代新种群; (8) 判断是否达到交叉算子中所设的最大交叉次数, 如果是则结束, 如果不是则转到步骤 (2) 。

2.2.2 变异操作

遗传算法的变异操作最主要目的是维持种群的多样性, 避免有效基因缺失而导致算法早熟。由于基于工序编码方式能确保交换变异方法的可行性, 所以本文采用交换变异方法, 即从初始种群中选择某个个体, 随机选择两个变异位置λ1和λ2, 且λ1≠λ2, 然后将λ1和λ2所在位置上的工序号进行交换, 完成变异操作。

3 算例分析

3.1 算例的基本参数

本文以单资源作业生产系统为例, 该生产系统的特点是每个工件的加工工艺路径不同。本算例以最大完工时间最小为优化目标, 利用MATLAB 7.10分别对本文所提的改进前和改进后的方法进行分析与验证。该算例中有6个工件和不同功能的6台机床。每个工件都有6道工序, 每道工序均只能在指定的唯一一台机床上加工, 不同工序加工对应的机床和加工时间关系如表1所示。

表1中, “1, 1, 10”表示工件1的第1个工序在机器1上的加工时间为10, 其余同理。此算例中设计的每个参数是:工件数J=6, 机床数M=6, 种群个体数NIND=40, 最大迭代次数GENmax=200, 选择概率GGAP=0.9, 交叉概率XOVR=0.8, 变异概率MUTR=0.6。对这批零件加工过程分别重复仿真10次, 对比改进前、后算法的稳定性和全局性。

3.2 算法改进前、后最优解和平均解的对比

(1) 用改进前的遗传算法对这批零件的加工过程重复仿真10次, 调度最优解即最小加工时间为152min, 调度Gantt图见图2, 种群均值及解的变化见图3。

需要说明的是, 在本次调度中工件工序的编号是由0~5这6个工序组成。图2方格中的数字, 第一个代表工件, 第二个代表工序, 例如:“50”表示第5个工件的第1道工序, 再和对应的纵坐标机床编号联系起来, 则完整地表示第5个工件的第1道工序在机床2上加工。其余以此类推。

(2) 用改进后即禁忌交叉算子的遗传算法对这批零件的加工过程重复仿真10次, 调度最优解即最小加工时间为135min, 仿真结果如图4和图5所示。

就改进前和改进后的调度Gantt图来比较, 可以看出改进后的调度结果比改进前机床的安排更加合理、紧凑, 缩短了加工时间。就图3和图5进行比较, 改进后的算法在收敛速度和求解质量方面有了明显改善。

4 结论

本文将禁忌搜索算法加入遗传算法, 由于这两种算法的优缺点相互弥补, 提高了算法的求解质量和效率。通过对典型的Job shop调度问题的求解和分析, 验证了引入禁忌搜索算法的改进遗传算法的全局搜索能力和求解的稳定性。

参考文献

[1]韦尧兵, 王睿超.基于改进遗传算法的作业车间调度问题研究[J].科学技术与工程, 2009, 9 (13) :3867-3869.

[2]万敏, 唐敦兵, 王雷, 等.求解车间调度问题的改进型自适应遗传算法[J].机械科学与技术, 2011, 30 (1) :39-42.

[3]王秋芬, 杨泽平, 梁道雷.一种改进的车间调度问题算法[J].科学技术与工程, 2013, 13 (11) :2997-3001.

[4]刘民, 吴澄.制造过程智能优化调度算法及其应用[M].北京:国防工业出版社, 2008.

[5]李佳, 彭玉青, 胡希文.改进的遗传算法在作业调度中的应用[J].计算机工程与科学, 2008, 30 (10) :48-50.

[6]黄可坤.改进遗传算法求解流水车间调度问题[J].嘉应学院学报, 2012, 30 (5) :8-12.

[7]曾益.一种基于改进遗传算法的车间调度问题研究[J].机械设计与制造, 2011 (10) :180-182.

调度员正规作业标准篇4

一、岗前准备

上岗前要更换工作服，戴好工作牌。

二、岗前交接

1、每班人员提前十分钟进行交接班，对下班处理过的遗留的问题进行岗前交接，并填写交接班记录。对运行的人员定位、广播系统、执法网系统、风机在线监测系统、井下大屏幕公示系统的运行进行巡查。

2、跟看领导跟班专栏报表、探放水报表、探水通知单、对井下有害气体报表、风机报表、公司领导值班表、隐患排查专栏等报表是否填写齐全，领导是否及时签字，隐患整改及时落实。

3、在双方确认无误情况下，在交接班记录上签字，完成岗前交接，检查作业场所卫生、设备运行情况。

三、上岗

1、每班对入井人员人数、特工人员、领导跟值班、大屏幕进行公示，及时通知总务部井下用餐人数（每月25日结），严格按照规定时间进行井下广播，对临时广播的内容需由值班领导批准方可进行。对风机监控系统内的各项参数要重点关注，发现异常及时汇报值班矿长。执法专网系统，除工作人员外，其余人员不准操作，对上级部门发出的指令要认真记录传达。对每日考勤人员上报的入井人数进行准确核对，做到入井挂牌与人员定位系统显示的人数一致，如出现人数不符，查明原因，对无视井下考

勤的人员，通报并上报安全部进行处罚，做好入井人员、公司领导值班、跟班的出勤情况，月底对主要领导入井情况、跟班情况进行大屏公示。

2、接班后调度人员核对工作面的班作业计划、任务，统计好各班组的当班作业计划和出勤人数，查看上班的调度记录，熟悉情况。收集坑口、车间、销售部门的日报情况，对每班产量生产情况、事故情况进行登记，认真填写调度台帐，上班后对本班生产安全进行分析汇总，填好材料，由值班矿长在调度会上进行汇报，传达有关领导的安排、指示、命令，做到上情下达、下情上报，掌握当班生产动态情况。每月八日前对下月生产计划安排进行井下大屏公示。

3、一旬、月完成后，要做出旬、月生产完成情况及存在的问题分析，并预测下旬、月的生产动态及发展趋势。

4、每日、旬、月的作业计划完成数据，日常发生的职工伤亡事故和生产事故以及采掘出勤等，要做好统计和分析。

5、当一个月的各项调度工作结束之后，要将调度记录、台帐、文件及各种分析资料整理存档，妥善保管。

6、坚守工作岗位，做到不迟到、不早退、不离岗，上班期间不做与无关的工作，严禁在电脑上接入U盘等存储设备，如因外部设备引起电脑系统病毒，软件损坏等问题，一经发现，处以重罚。

7、认真做好本室卫生工作，做到清洁卫生，整洁有序，对

工作认真负责，处理问题不慌不忙、井然有序，汇报工作有条有理、有理有据，如实上报。

四、交接

作业车间调度篇5

为了更好地适应市场竞争,满足用户个性化需求,多品种、变批量的生产方式成为了复杂作业模式下的主要生产方式。而为了保证柔性化生产的同时有效提高企业的生产效率、降低制造成本,对于具有相似工艺的批次任务,在制造资源使用上要求能最大限度地实现共享。由于流水线的规模效益能极大提高制造企业的生产效率,局部流水就成为了复杂作业模式下的另外一个生产特点[1]。

在复杂作业模式下,制造企业的车间的生产过程主要以多品种、变批量生产为主。而由于受到制造资源、交货期及批量变化等诸多因素的影响,一个批次的生产任务在其加工过程中可能会不断的进行调整[2],包括生产节奏和生产方式的变化等。当交付期提前时,可能会引起原有的调度方案或者在原有调度方案基础上的柔性重调度都无法满足新的交货期要求,此时就只能通过部分批次进行局部流水生产来满足交货期提前的要求。例如,生产车间存在两个在制批次,加工信息表如表1所示,批次1的交货期为10,批次2的交货期为9。车间生产的初始调度如图1所示。如果此时应客户要求,批次1的交货期提前为7。则按照原方案显然会使得批次1拖期完工,而由于初始方案已经是最优的调度方案。如果此时对批次1 进行局部流水生产,如图2所示。显然,进行局部流水生产是复杂作业车间避免批次任务无法满足交货期要求的一个可行方案。

然而,对于离散制造企业,由于车间布局的分散性,使得局部流水生产模式会增加车间现场管理难度,增加零件在各个设备之间的运输成本,合理的安排车间局部流水生产批次的数量才能降低企业的制造成本。可见,实际的离散制造车间存在着批量生产和局部流水生产同时并存现象。柔性作业车间调度问题是强NP-hard问题[3],而该问题比柔性作业车间调度问题复杂。因此,研究这种混合生产方式下的生产调度问题具有重要的实际意义。针对这个问题,本文首先对该问题进行建模,然后提出一种基于模拟退火法的调度算法。

1 含局部流水的柔性作业车间调度问题建模

含局部流水的柔性作业车间调度问题可描述为:n个待加工批次任务J={J1,J2,J3,…,Jn},批次相应的批量大小D={D1,D2,D3,…,Dn},有m台加工设备M={M1,M2,M3,…,Mm}。Ji为第i个待加工批次任务,该批次零件的工艺工序数量为ni。零件的每道工序可以在一台或者多台设备上进行加工,加工时间根据设备性能的不同而变化。优化过程满足以下约束:(1)批次任务的每道工序同一时刻只能在一台设备上进行加工;每台设备同一时刻只能加工一个批次任务的工序。(2)批次任务的工序在加工过程中不允许中断。(3)批次工序的加工时间是确定的,不考虑批次启动时间,零件的装卸时间计算在加工时间内。(4)批次是否能进行局部流水生产是确定的,对于不能按局部流水生产的批次,其工序在加工及搬运过程中视为一个整体处理,同批次的前道工序加工完成后才能进行下道工序加工;而能按局部流水操作的批次工序前后工序应满足:STi,j+pi,j≤STi,j+1+(1-ri,j)L;ETi,j≤ETi,j+1-pi,j+ri,j×L。如图3示。其中,STi,j为批次i的第j道工序Oi,j的开始加工时间;pi,j为工序Oi,j在选择设备后的单件工时。ETi,j为工序Oi,j的结束时间。ri,j为C变量参数,当pi,j≤pi,j+1时,ri,j=1;否则ri,j=0。L为一个很大的整数。(5)不同批次任务的工序之间没有先后顺序约束。

目标函数:调度目标为最小化批次完工日期,即min(max ETi,ni)。

由上面分析,可以建立该问题的线性规划模型:

其中,STi,j,k为设备Mk加工工序Oi,j开始时间;zi,j为0时工序Oi,j按局部流水进行加工并流转到下道工序,zi,j为1表示Oi,j按正常批量生产,在整个工序所有零件都完工后才能进行该批次下道工序加工。式(2)和(3)为同批次前后工序的加工时间约束,而式(4)为同一设备上的前后两道工序之间的加工时间约束,式中Oi,j为工序Oi′,j′在设备Mk的后一道工序。

2 基于模拟退火法的调度算法

模拟退火法(Simulated Annealing,SA)是IBM托马斯.J.沃森研究中心的Kirkpatrick等人在文章中首次提出[4],由于物理退火过程和一般的组合优化问题具有相似性,故而把退火的思想引入其中,通过Monte Carlo迭代策略提出了解组合优化问题的有效方法,称为模拟退火法。

模拟退火法被认为是组合优化问题的有效解决方案之一,它能完成很多传统方法无法解决的优化问题,NP难问题便在其中。因此本文利用模拟退火法解决柔性作业车间局部流水调度问题。而该问题涉及批次工序的设备分配及所有工序的排序问题,是复杂的组合优化问题,根据分层优化思想,本文将这两个问题分开解决。

2.1 编码

本文用一个二维矩阵表示设备分配方案,如图4左边矩阵所示。每一列的含义为:从上往下,第一行为待加工批次号;第二行为工序号,第三行加工设备,第四行为工序加工工时;第六行为设备选择参数,1代表选中,0代表未选中。邻域搜索方法为:在矩阵中随机选择一道工序所在的两列,其中必须有一列的设备选择参数为1,交换这两列设备选择参数。

工序排序编码如图4右边部分所示,采用基于任务的编码方式[5],数字代表批次号,而其在矩阵中出现的次数为该任务的第几道工序。邻域搜索方法为:随机选出两个不同的数字,交换它们的位置。

2.2 算法流程

(1)产生随机的初始解F,对F进行工序排序模拟退火法操作,将得到的最优解F*替换F。记录当前最优解Fbest=F*。初始化初始温度T,最小温度t,退火速度r,终止条件N,马科夫链长度L。(2)如果T>t或者N<20,则转步骤(3),否则转步骤(5)。(3)循环执行步骤(1)~(4)L次。(1)对F进行设备选择邻域搜索的到FC,对FC进行工序排序模拟退火法操作;(2)计算△=f(FC)-f(F),如果△<0,则F=FC;(3)计算△b=f(FC)-f(Fbest)。如果△b<0,则Fbest=FC,N=0;否则N=N+1;(4)如果△>0,产生0到1之间的随机数P,如果e-△/T>P,则F=FC;(4)改变温度,T=r×T,转步骤(3);(5)输出最优调度方案Fbest。算法终止。

对于上述算法流程中的工序排序模拟退火法操作流程为:(1)对输入的方案F进行工序排序随机初始化得到解S,Sbest=S,初始化T,t,r,N,L。(2)如果T>t或者N<20,则转步骤(3),否则转步骤(5)。(3)循环执行步骤(1)~(4)L次。(1)对S进行设备选择邻域搜索的到SC;(2)计算△=f(SC)-f(S),如果△<0,SC=S;(3)计算△b=f(SC)-f(Sbest),如果△b<0,则Fbest=FC,N=0;否则N=N+1;(4)如果△>0,产生0到1之间的随机数P,如果e-△/T>P,则SC=S(4)改变温度,T=r×T,转步骤(3)。(5)输出最优排序方案Sbest;算法终止。

3 实例仿真分析

算法采用了Flash ActionScript3编程语言实现,运行的微机主频为Pentium2.5GHz,2G内存,XP操作系统。利用Kacem[6]等提出的8×8问题对算法进行验证。假设每个任务的批量都为10,假设所有批次都不允许进行局部流水生产。算法得到的调度结果如图5所示,最小交货期为140,与Yazdani等[7]得到的最小完工时间是14是等效的。结果表明了算法在解决柔性作业车间调度问题的有效性。

假设每个任务的批量都为10,其中只有批次任务4不采用局部流水生产方式,利用本文算法进行仿真,算法参数为:T=100,N=20,r=0.9,t=1,L=20。得到的调度方案如图6所示,最小完工时间为132。结果表明与不采用局部流水调度相比,局部流水能有效的减少车间中的最大完工时间,同时也提高了设备利用率。虽然任务6和7的完工时间没有明显减少,但是其它任务的完工时间都很大程度缩短了。

4 总结

对于复杂作业模式下车间批量生产和局部流水生产并存的车间调度问题,本文首先对调度问题进行分析,在柔性作业车间调度问题的基础上建模,然后利用两层基于模拟退火法的混合算法进行工艺路径和工序加工顺序的优化,最后实现最小化完工时间的调度目标。仿真结果表明了算法有效性和可行性。算法能很好的解决含有局部流水生产的柔性作业车间调度问题,具有一定的实用性。

摘要：针对含有局部流水生产的柔性作业车间生产调度问题,首先在柔性作业车间调度问题的基础上建立调度模型,然后提出一种基于模拟退火法的调度算法,同时对加工路径和加工顺序进行优化,并实现最小化完工时间的调度目标。最后通过实例进行仿真,结果表明了算法的可行性和有效性。

关键词：机械制造,车间调度,柔性作业,模拟退火法

参考文献

[1]张蕾.面向复杂作业模式的动态调度问题的研究与实现[D].西北工业大学硕士论文,2010.

[2]魏从刚,何卫平,张英,等.非连续生产的车间作业计划方法研究[J].机床与液压,2006,(9):25-28.

[3]Pezzella F,Morganti G,Ciaschetti G,A genetic algorithm for theFlexible Job-shop Scheduling Problem[J].Computers&OperationsResearch 35(2008)3202-3212.

[4]刘洪普,侯向丹.模拟退火法中关键参数的研究[J].计算机工程与应用,2006,28:38-40.

[5]LI Junqing,PAN Quanke,LIANG Yunchia.An effective hybrid tabusearch algorithm for multi-objective flexible job-shop schedulingproblems[J].Computers&Industrial Engine-ering 59(2010)647-662.

[6]KACEM I,HAM MADI S,BORNE P.Approach by localization andmulti-objective evolutionary optimization for flexible job-shopscheduling problems.IEEE Transactions on Systems,Man,andCybernetics,Part C,32(1),1-13.

作业车间调度篇6

柔性作业车间调度问题(flexible job shop scheduling problem,FJSSP)是比作业车间调度问题(job shop scheduling problem,JSSP)更加复杂的车间调度问题。与JSSP相比,FJSSP考虑了同一个工艺可在不同机器上加工,且加工时间可能不同,增加了问题的复杂性和求解的难度,更符合柔性制造的理念。随着柔性制造理念被制造业广泛接受,其理想化模型FJSSP的求解受到了研究者广泛关注。

车间调度问题的求解可分为数学规划和启发式调度方法两大类。尽管数学规划方法较为成熟,但由于其仅限于求解小规模调度问题,对具有NP-hard特性的车间调度问题已不适用。目前广泛应用的启发式算法主要有余建军等[1]提出的免疫模拟退火算法、Ho等[2]提出的LEGA(learnable genetic architecture)算法与Xu等[3]提出的IACO(improved ant colony optimization)算法,但上述算法的求解精度仍有待提高。

人工鱼群算法[4]基于行为主义人工智能,模拟动物行为寻找全局最优。该算法具有克服局部最优、寻找全局极值的能力[5,6,7],收敛速度快、使用灵活,实现算法时无需目标函数的梯度,对搜索解空间具有一定程度的自适应性,但存在寻优精度不高、前期收敛较快而后期搜索盲目性大[7],或者在局部极值周围严重聚集[8],收敛速度大大降低的问题。

本文针对FJSSP解空间巨大及现有求解方法在寻优精度上的不足,利用人工鱼群算法收敛速度快、使用灵活等优点,采取改进措施提高算法寻优能力,建立了一种改进的FJSSP求解方法,并采用Brandimarte标准问题检验了算法的有效性。

1 FJSSP模型

FJSSP描述的是在具有m台加工设备的生产系统中加工n个工件,每个工件需要按次序完成一个或多个工艺,每个工艺有至少一台加工设备可供选择。

FJSSP模型包含以下约束条件[9,10]:

(1)各个加工设备彼此独立,任一加工设备是否工作、是否故障不影响其他加工设备,且所有加工设备在开始时刻(t=0)均可开始工作。

(2)所有工件彼此独立,任一工件的加工状况不对其他工件产生影响,所有工件在开始时刻均可开始加工。

(3)所有工件的工艺流程在加工开始之前已定,加工过程中不能改变任何一个工件的既定工艺流程。

(4)所有工艺可供选择的加工设备以及在相应设备上的加工时间在加工开始之前已定,加工过程中不能改变。

(5)每台加工设备一次只能完成某个工件的某一道工艺,一个工件的一道工艺不能在多台加工设备上同时完成,一道工艺一旦在某台加工设备上开始加工就不会中断,直到该工艺加工完成。

(6)不考虑临时订单、设备故障等任何可能中断加工过程的突发事件。

本文研究以最小化最大完工时间为调度目标的FJSSP。只考虑工件在加工设备上的加工时间,不考虑加工设备的调整时间以及工件在各个加工设备之间的运输时间。因此,某个工件的完工时间等于该工件的各个工艺在相应加工设备上的加工时间与由于某台加工设备正在加工其他工件而造成的等待时间之和。

综上所述,FJSSP数学描述如下,W ={W1,W2,…,Wn}为需要加工的n个工件的集合;M ={M1,M2,…,Mm}为m台加工设备的集合;表示工件Wi依次经过的ni道工序集合;

表示可以加工工艺Oij的加工设备集合,其中,kij为可以加工工艺Oij的机器数量,。在此基础上建立的最小化最大完工时间调度目标函数为

式中,Emax为最大完工时间,即所有工件的完工时间;Oij表示工件i的第j个工序;Si(j+1)为第i个工件的第j个工序的开始时间;p为机器序号;Eij为第i个工件的第j个工序的完成时间;Mijk表示第i个工件的第j个工序选择在第k台机器加工;Tijk为工序Oij在设备Mijk上的加工时间;Sijk为工序Oij在设备Mijk上的加工开始时间;Eijk为工序Oij在设备Mijk上的加工结束时间,Eijk=Sijk+Tijk。

式(1)说明调度目标为最小化最大完工时间;式(2)表示工艺有先后约束,工件下一个工艺的加工需要上一个工艺完成之后;式(3)表示同一台加工设备同一时刻只能加工一个工件,下一个工件需要等上一个工艺加工完成;式(4)表示工件在设备上开始加工的时间取决于工件在上一台设备加工完成的时间以及设备加工完上一个工件的时间,这两者中的最大值。

2 求解FJSSP

FJSSP求解目标:一是确定工件Mi的工艺Oij的加工设备Mijk;二是确定在各个加工设备上加工的工艺序列,进而确定各个机器上加工的各个工艺的起止时间。基于改进人工鱼群算法求解FJSSP,关键在于人工鱼群算法的编码解码方式,视距、步长等参数的设置和随机行为、觅食行为等的实现,并针对传统人工鱼群算法求解FJSSP中的不足予以改进。

2.1 基于改进人工鱼群算法求解FJSSP

2.1.1 编码解码策略

针对FJSSP需要解决的两个问题,本文采用双子串编码方式。设各个工件的工艺总数为t,并从0到t-1按顺序编号;机器总数为m,并从0到m-1按顺序编号;工件总数为n,并从0到n-1按顺序编号。双子串的两个子串A、B都是长度为t的数组,A[a1],A[a2],…,A[at]为0到t-1号工艺选择的加工设备编号;B[b1],B[b2],…,B[bt]表示n个工件的优先权排序(序号为t个范围在[0,n-1]的自然数),排列靠前的工件优先占有加工资源。Iijk为工件i的第j个工艺在第k号加工台上的加工时间,i为0~n-1的自然数,j为0~s-1的自然数,s为需要经过工艺数量最多的工件具有的工艺数,k为0~m -1之间的自然数。当工件i的第j个工艺不在第k号加工台上加工时,Iijk=-1;数组L表示各个工件需要经过的工艺数量,L[i]表示工件i的工艺数量,i=0,1,…,n-1。

(1)子串A编码算法。

步骤1 令a=0,i=0;

步骤2 若i=n,则转步骤5,否则令j=0,转步骤3;

步骤3 若j=s,则i←i+1并转步骤2,否则转步骤4;

步骤4 如果工件i存在第j号工艺,则随机生成0~m -1之间的自然数k,直到Iijk的值不为-1;A[a]=k,即子串A的第a个数赋值为k,表示这组工件的第a个工艺选择第k号加工台加工;a←a+1,j ←j+1,转步骤3;

步骤5结束子串A编码。

(2)子串B的编码算法。

步骤1 令j=0;

步骤2 若j=t,则转步骤4,否则转步骤3;

步骤3 随机生成0到n-1的自然数k,直到L[k]不为0;B[j]=k,L[k]← L[k]-1,j←j+1,转步骤2;

步骤4 结束子串B编码。

其中,B[j]为子串B的第j个分量。解码即根据双子串编码,求出每个加工机器上加工的工件的起止时间。设H [i]表示工件i已经排序的工序数,解码开始时,H [i]=0;U[i]表示工件i的第一个工艺在子串A中的开始位置。则解码算法可描述为:对于编号x从0~t-1的t个工序,将工件B[x]以最早容许加工的加工时间在机器A[U[B[x]]+H [B[x]]]上加工,最早容许的加工时间是从工件B[x]上一次操作结束时间开始,依次比较机器A[U[B[x]]+ H [B[x]]]的加工空隙是否可以插入该工件,如果可以则插入该工件,否则,将此工件排列在尾端。

2.1.2 人工鱼行为的实现和参数设置

鱼群的随机行为实现,就是对于子串A,随机生成0~t-1的之间自然数u来决定改变编码的哪一位,对于第u位(从0开始计数),重新随机选取可以加工机器;对于子串B随机选取2个位置p、k,若2个位置的工件号不同,则调换2个位置上的工件号。鱼群的觅食行为具体实现方法为,随机选取视距内的人工鱼,如果被选取的鱼的位置优于当前鱼的位置则往其方向前进一步,否则再随机选取视距内人工鱼(已经尝试过的鱼除外),直到超过规定的尝试次数,或所有鱼都尝试过,仍然没有找到更优的人工鱼,则随机移动一步。向某条鱼前进一步指的是,从两条鱼编码中不相同的位里随机选取数量等于步长的位,将当前鱼的这些位修改与目标鱼相同。聚群行为具体的实现方法如下:如果视距内中心位置的食物浓度优于当前鱼处食物浓度且中心位置不拥挤,则向中心位置前进一步,否则执行觅食行为。

人工鱼中食物浓度为所有工件完工时间。人工鱼A1B1与人工鱼A2B2的间距定义为

式中,A(i)、B(i)分别为工设备序列和加工优先级序列字串的第i个分量.

鱼群的移动策略为先执行觅食行为,再执行聚群行为,最后执行追尾行为。在鱼群移动过程中,用公告板来保存算法迭代过程中找到的最优解,即每次执行完一个行为,就与公告板上的最优鱼比较,如果优于最优鱼,则代替公告板上的最优鱼。

人工鱼群算法对初始参数设置不是很敏感,参数可选择范围较广。总体来说,步长较大有利于加快收敛,但过大可能导致震荡无法收敛;步长小就会降低收敛速度,但有利于提高寻优精度。视距较大,算法全局搜索能力较强,但超过一定值后对算法性能改进没有明显效果;视距过小,人工鱼找不到更优位置,始终执行随机行为,算法不能收敛。较大的拥挤度因子不容许局部聚集过多的鱼,迫使鱼群搜索更广的解空间;拥挤度因子较小有利于鱼群收敛,但也易陷入局部最优。种群规模越大,算法寻优能力越强,找到最优解的概率越大,种群规模超过一定限度后,对提高寻优能力作用不明显。迭代越多,算法寻优能力越强,但算法运行时间同样正比于迭代次数,且迭代次数超过一定限度后对寻优能力的提高不再起作用。本文根据大量实验总结了求解FJSSP时基本人工鱼群算法的经验参数设置方法:步长为编码长度(其中一个子串的长度)的1/60~1/30,视距在编码长度的1~2倍之间,拥挤度因子设为0.05 ~0.1之间的数值,尝试次数在种群规模的1/2左右,种群规模设置30~50之间较为合适,迭代次数约为1500。

2.1.3 鱼群算法的改进

人工鱼的随机行为保证了鱼群跳出局部、探索更多解空间的可能性,但过强的随机行为不利于算法收敛,导致搜索精度降低;反之,有利于算法收敛和局部搜索,但易陷入局部最优,降低全局搜索能力。随机行为的强弱与随机移动的步长、随机移动执行的次数有关,随机移动次数多且随机移动步长大,鱼群表现出强随机行为。向目标前进一步与随机移动行为的作用相反,前进步长大有利于快速向最优鱼聚拢,增强收敛性,弱化随机行为;较小的前进步长让聚拢速度较慢,避免早熟收敛,陷入局部最优。因此,本文将随机移动步长和向目标前进步长分为两个参数,细化控制算法执行过程。

拥挤度用来判断某一领域内的鱼群是否拥挤,较大的拥挤度迫使过多的鱼群离开局部聚集区域,尽可能分散,增大搜索广度而不利于鱼群收敛;反之,对鱼群的聚拢容忍度高,有助于算法收敛。同时,局部聚集的较大鱼群有利于增强局部搜索能力,但有可能引发早熟收敛,陷入局部最优。

本文采用柔性参数设置,前期设置较大的拥挤度和随机步长、较小的前进步长,增强随机行为,使鱼群分散而活跃,搜索全局解空间;后期减小拥挤度和随机步长,增大前进步长,弱化随机行为,容许鱼群聚集,增强算法收敛性和局部寻优能力。另外,如果还不满足要求,觅食、聚群、追尾都会执行随机行为。为弱化算法随机性,算法后期减小随机移动次数。

柔性参数设置的具体方案是,将随机移动步长、前进步长、拥挤度按照由大到小的顺序设置为5个等级,算法执行过程按照迭代次数的多少均分为5个阶段,每过一个阶段相应地改变参数等级。

另外,针对算法寻优精度不高的问题,本文将人工鱼群算法与局部遍历搜索算法结合。局部遍历搜索算法的策略:改变子串A的一位;对调子串B的某两个值不同的位,即对调两个工件的加工优先顺序。遍历即是尝试上述局部算法策略,直到新的编码比之前更优或尝试完所有可能的局部搜索。必须指出的是,局部遍历搜索算法将导致算法执行时间的剧增,因此,本文仅将局部遍历搜索算法应用到算法执行即将结束(迭代次数可以人为指定)的阶段。

2.2 调度算法流程

基于前述对人工鱼群算法的改进,以最小化最大完成时间为调度目标,求解FJSSP的改进人工鱼群算法流程如图1所示。

求解FJSSP的改进人工鱼群算法的具体步骤如下:

(1)初始化人工鱼群,按照2.1 节的编码策略,随机初始化40条人工鱼。

(2)从鱼群中选取最优鱼,即解码得到完工时间最小的鱼,存入公告板。

(3)执行觅食、聚群、追尾行为,若是最后10次迭代则执行局部搜索。

(4)将当前迭代次数加1,判断当前的参数等级与迭代阶段是否匹配,不匹配则更新参数。

(5)判断是否达到算法终止条件,达到则结束算法并输出执行结果,否则转到第步骤(2)继续。

3 试验验证

为验证算法性能,以FJSSP常用的Bran-dimarte问题作为算例,将改进后的人工鱼群算法与基本人工鱼群算法以及国外其他柔性作业车间调度算法,如Nhu等[2]提出的学习进化型遗传算法、Xu等[3]提出的增强蚁群算法比较。

柔性参数设置将参数分为5个渐进的等级,随着迭代次数的不同选取不同参数设置,参数设置与迭代次数之间的关系见表1。

表2给出了改进人工鱼群算法(IAFSA)、基本人工鱼群算法(AFSA)、Brandimarte算法、LE-GA算法、IACO算法寻找到的最优解,表中的相对改进表示IAFSA求得的最优解相对于其他算法提高了多少时间单位。从表2可以看出,IAF-SA寻找到的最优解相对于AFSA、Brandimarte算法、LEGA分别平均提高了3.44、19.67、2.75个时间单位,有显著的提高;与IACO相比,MK01、MK05、MK10最优解稍差,但MK02和MK04的最优解有较大幅度提高,平均来看有小幅度提高。可见,本文提出的改进人工鱼群算法能够有效求解柔性作业车间调度问题。

表3~表5对比了几种算法的平均值、方差和平均执行时间,LEGA算法的平均值、方差和平均执行时间数据来源于文献[2],另外两种算法的相关数据统计方法是每种算法连续执行20次,计算20 次解的平均值、方差和算法平均执行时间,文献[3,11-13]未提供平均值、方差和执行时间数据。从表3、表4可以看出,与AFSA和LE-GA算法相比,IAFSA的平均值有一定幅度的提高,分别平均提高3.54时间单位和2.63 时间单位,但方差较大。这表明,改进后的算法寻找最优解的能力及解的平均值都有提高,但算法稳定性略有下降。原因可能是算法在执行的后半段追求提高搜索精度,增强局部搜索能力,导致算法在一定程度上承担了更高的陷入局部最优的风险。文献[2]使用的电脑CPU是2GHz主频Pentium IV,本文使用的电脑CPU是2GHz主频Intel P7350,两者主频相同,试验统计的执行时间具有可比性。表5说明三种算法执行时间相差不大,但由于加入局部搜索,IAFSA执行时间略长。

图2是求解MK04问题时,IAFSA和AFSA的迭代曲线图,图中曲线均为两种算法执行效果最好的一次,IAFSA求得最优解60,AFSA求得最优解66。图2 中,横坐表示是迭代次数,纵坐标表示完工时间Emax。可以看出,两种算法执行初期类似,算法的平均值和最优值均快速收敛,且平均值与最优值有一定距离———反映了鱼群分布较为广泛;迭代400次时,两种算法找到的最优值相近,但IAFSA的鱼群已经收敛;400次迭代之后,AFSA寻找最优解的效率明显降低,且鱼群一直分布广泛,不能收敛,因此,AFSA后半段表现出漫无目的全局搜索。IAFSA在后半段受到柔性参数设置的影响,鱼群逐步收敛到局部区域,增强了搜索精度,后半段最优解仍有较大程度的提高。

1.改进人工鱼群算法的公告板值2.改进人工鱼群算法的均值3.基本人工鱼群算法的公告板值4.基本人工鱼群算法的均值

本文算法求解MK02和MK04问题时,所得最优解较其他算法有较大幅度提高,图3、图4给出了MK02、MK04最优解的甘特图。横坐标表示完工时间,纵坐标表示加工机器编号,图中不同灰度的色块代表色块旁边号数的工件在某一个加工机器上的加工时间段。

4 结语

作业车间调度篇7

作业车间调度问题 (Job-shopSchedulingProblem, JSSP) 是一个典型的NP-hard问题, 随着现代工业的发展, 企业的生产正朝着多类型、小批量、有着不同完工时间和产品要求的方向发展, 从而使得企业的生产作业计划安排工作难度加大。高效的调度算法, 可大大提高生产效率, 增强企业的竞争能力, 因此其研究具有重要的理论意义和工程价值, 它也是目前研究最广泛的一类典型调度问题。作业车间调度问题是制造系统的一个研究热点, 也是理论研究中最为困难的问题之一。调度的目的是根据生产目标和约束, 为每个加工对象确定具体的加工路径、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效益, 有着极大的作用。由于系统建模方法的多样性以及问题的侧重点不同, 调度方法和研究对象也有着明显的不同。就对象而言, 有确定性和随机性调度、离散事件和连续事件调度, 静态和动态调度等。就调度方法而论, 有Gantt图法、构造型方法、动态规划法、分支定界法、排队论方法、规则调度方法和仿真方法等。调度的优化指标包括正规性能指标和非正规性能指标, 常用的指标有最大完成时间、平均加工时间、平均延迟时间、生产成本和E/T指标等。有效的调度方法和优化技术的研究与应用, 是实现先进制造和提高生产效益的基础和关键。改善生产调度方案, 可大大提高生产效率和资源利用率, 进而增强企业的竞争力。调度的研究主要分为建模和调度算法设计两方面, 它是一个交叉性研究领域, 涉及运筹学、数学、计算机工程、控制工程、工业工程等多个学科。其中建模主要研究调度模型、调度规则、目标函数等内容;调度算法主要研究算法设计、算法复杂性、算法收敛性和优化质量等内容。

遗传算法 (GA) 是一种通用的优化算法, 其编码技术和遗传操作比较简单, 优化不受限制性条件的约束, 且具有隐含并行性和全局解空间搜索等特点。利用遗传算法求解车间生产调度问题, 一方面能够充分地利用遗传算法的全局搜索能力, 在较大规模的解空间中寻求全局最优解;另一方面, 利用遗传算法的隐式并行性和强鲁棒性等优点, 可充分减少问题的求解时间, 提高问题的求解效率。

1 问题的描述

车间作业的调度问题可描述为:m台机器 (用集合M={Mj}mj=1表示) 加工n个工件 (用集合J={Jj}ni=1表示) , 每个工件包含由多道工序组成的一个工序集合。工件有预先确定的加工顺序, 每道工序的加工时间为tij, 在给定的时间内每台机器只能加工一个工件, 并且每个工件只能由一台机器处理。不同工件的加工顺序无限制, 工序不允许中断;要求在可行调度中确定每个工序的开始时间sij, 使总完工时间Cmax最小, 即C*max={max (sij+tij) :

Ji∈J, Mj∈M}, 求解满足以上条件的工件加工顺序即构成JSSP调度问题。

2 遗传算法的设计

2.1 编码与解码

采用按工序的实数编码。每个染色体用n×m个代表工序的基因组成, 是所有工序的一个排列, 其中各工件号均出现m次, 表示每个工件都有m道工序。解码过程是:先将染色体转化为一个有序的工序表, 然后按该表和机器约束对各工序以最早允许加工时间逐一进行加工, 从而产生调度方案。假设问题规模为3×3, 染色体为[211123233], 机器约束为[112332213]每个数字表示工件号, 如第一次出现的2表示工件2的第1个工序在第1台机器上加工, 第二次出现的2表示工件2的第2个工序在第3台机器上加工, 依此类推。因此对照加工顺序的工艺约束, 每个个体都对应问题的一个可行解。

2.2 种群生成

遗传进化初期, 通常会产生一些超级个体, 在选择中占据优势;随着进化的进行, 这些个体的数量迅速扩大, 到遗传进化后期, 群体中绝大多数个体已成为某个超级个体, 导致算法继续优化潜能降低, 难以获得全局最优解。

首先判断种群的收敛程度, 设第t代种群由个体x1, x2, …, xn构成, 适应度分别为f1, f2, …fn, 令fmax代表该代种群最优个体的适应度, favg代表该代种群个体的平均适应度, 采用多次随机抽取策略, 及对每一代种群随机抽取一个子集, 计算最大适应度fmax, 及平均适应度favg, 计算二者的差值Δ=fmax-favg。这样反复进行多次, 若有一次出现Δ小于一定数值, 则为早熟出现, 这个子集称为早熟子集。出现早熟收敛后, 为了增加种群的多样性, 就需要在正在进化的种群中引入新的种群, 使之与其他个体具有相同的交叉、变异和选择机会, 共同进化。

在JSSP中采用SPT、LPT、MWR、LWR、MOR、LOR、EDD、FCFS和RANDOM等不同的启发式规则来产生优化种群的个体。

2.3 适应度函数的设计

适应度函数是区别解的好坏的标准, 本算法以最小制造周期 (Makespan) 为目标函数。它是在可行解的解空间中, 找出一个可行解, 该解的所有工件的最大的结束时间与其它所有可行解相比为最小, 用数学式子表示为

其中i∈J, Cmax (s) =max (ci) , i∈J。

则适应度函数为

2.4 遗传操作

2.4.1 选择

选择是从当前群体中选择适应值高的个体以生成交配池的过程.最基本的选择方法是适应值比例的选择。选择过程体现了生物进化过程中“适者生存, 优胜劣汰”的思想, 并且保证优良基因遗传给下一代个体。

算法采用的选择操作:首先用当前种群中适应值最高的个体代替适应值最差的个体, 选择到目前为止适应值最高的个体, 进入下一代, 这样最优个体能一直繁殖下去;然后用轮盘赌选择方法选择p-1个不同个体进入下一代, 其中p为种群大小。这样父代中的个体具有同等的选择机会, 既能将最优个体保留到下一代和淘汰最劣的个体, 又能保证子代的多样性。实验证明, 与传统的轮盘赌比较, 这一改进在收敛速度和质量上都有较大提高。设群体大小为p, 个体i的适应度为fi其被选择的概率为

2.4.2 交叉与变异

交叉操作是进化算法中遗传算法具备的原始性的独有特征。通常采用的遗传算子包括单点交叉、两点交叉、多点交叉、一致交叉等形式。现采用单点交叉。自适应交叉概率Pc取0.8。

变异操作采取互换变异, 即随机选择个体某一位, 将其基因与相临的基因互换。变异概率Pm取0.15。在交叉和变异操作中, 都保证在算子的作用下生成可行解, 即随机选择交叉的父体, 或变异基因位置, 进行交叉或变异操作;若新个体不是可行解, 则继续进行随机选择, 直到生成可行解, 保证交叉和变异操作在可行解空间的交叉和变异概率。

3 仿真分析

改进的遗传算法选择遗传代数为终止条件, 采用matlab编程实现, 程序运行在p4 1.8G, 内存512MB的计算机上。其种群规模p、遗传代数Gen、交叉概率Pc和变异概率Pm相同 (P=400, Gen=50, Pc=0.8, Pm=0.15) , 分别对标准实例ft10进行20次计算, 结果如图1所示。可见改进算法 (HGA) 具有较高的搜索效率。

4 结束语

分析了作业车间调度问题的特性, 在进行遗传算法操作时, 通过优化种群, 避免了局部最优, 保证了遗传算法的收敛性。研究结果表明本算法收敛速度快, 并具有较强的搜索能力, 具有工程实际应用前景。

摘要：为了解决遗传算法的早熟收敛问题, 提出一种改进遗传算法。通过设定种群过早收敛指标, 在种群出现过早收敛时, 及时的对其进行优化。仿真示例说明了该遗传算法在求解Job-Shop生产调度方面的可行性和有效性。

关键词：遗传算法,作业车间调度,优化种群

参考文献

[1]王凌.车间调度及其遗传算法.北京:清华大学出版社, 2003:56—101

[2]王小平, 曹立明.遗传算法——理论、应用与软件实现.西安:西安交通大学出版社, 2002:28—38

作业车间调度篇8

进人21世纪以来, 制造业生产模式随着科技的飞速发展和科技的进步在不断发生变化。快速多变且无法预测的买方市场由当初的大批量订购向着个性化、多样化方向转变, 这就使得制造企业所面临的诸多问题比如社会环境、生产条件、物质供给等方面都发生了显著变化。因此, 在这种情况下, 一种以大批量生产的效益、提供满足客户个性化需求的产品和服务的定制生产方式应运而生[1]。由于生产车间有很多不确定因素, 因此在生产调度问题上面临着巨大的挑战。过程规划和作业车间调度承担着巨大重任。过程规划的主要作用是完成对机器的分配过程, 实现资源的优化配置;车间调度的工作是确定每台机器处理的工件和加工开始时间, 为了完成所有进程并实现既定目标的优化。针对遗传算法的收敛速度不快、局部搜索能力差, 生成最优解不精确等特点, 本文提出一种新的算法基于遗传算法和贪婪算法的作业生产调度, 它是在遗传算法原算法的基础上, 引进贪婪变换进行个体解码来提高遗传算法在解的收敛速度和寻优能力。

1 基于混合遗传算法的车间调度问题

作业车间调度可以描述为1台机器加工N种工件 (N是工件的集合) , 使用B种夹具以及C种刀具对工件进行加工 (B是夹具的种类, C是刀具的种类) , 工件的总加工时间是T (T是所有工件加工用时间总和) 。工件之间的操作序列, 满足一定的约束。工件开始加工及加工工件前的准备工作是机器加工的第一个操作, 工件在加工完成后都有它的特定的交货期, 且不同工件的交货期不一样。当然在加工过程中使用的工具最少, 步骤最精, 工作时间最短, 机器利用率最高这些都说明了生产调度性能最优[2]。本文主要研究一般性的Job Shop调度问题, 在此问题满足以下特点[3]:

1) N为工件集, 工件的种类记为K (K是所有工件细分后的种类) , 每个种类都有不同数目的工件, 每个工件的操作步骤或许不相同但是步骤的顺序是固定的。

2) 处理机器配有不同的处理工具, 可以处理多种工件, 工件加工时间来确定所需的约束, 在处理计划中确保所有处理任务的完成。

3) 每个工件有规定的到期时间, 由于需要在规定的期限内完成工作任务, 所以要求相同类工件的到期时间相同, 方便机器统一加工;反之则不同。

4) 在给定的时间内, 1台机器只能够加工1个工件的1道工序, 直到加工完此工序方可加工其他工序。满足以上四种条件的这种作业车间调度问题, 都可以按工件交工延迟最短、机器加工最多工件、总加工时间达到最小为目的设计目标函数[4]。其目标函数为:

式 (1) 不仅考虑了操作工件所用总时间为最少, 使工件的加工时间最集中、工具应用效率最高, 还使得工件的加工量不会超出机器自身的承受能力, 且保证了各工件完工期限的总延误最小。其中:i是工件号;j是工件加工的总天数计数;si是工件i的交工时间;Xi是工件i加工日的集合;wi是机器加工工件所用刀具数量的集合;ci是刀具加工工件工序的集合;v是机器在加工零件过程中的最大承受能力;ti是1台加工机器完成工件i操作加工的时间, 它包括在加工工件不同工序时的机器等待时间, 以及工件的安装时间和工件加工时间。

2 溶合遗传算法和贪婪算法

遗传算法是将自然进化论的理论应用到理论算法的一种随机搜索算法, 它已成功地应用于作业车间调度, 本文把贪婪变换G引入到遗传算法中, 不仅能够发挥遗传算法在各种调度方案之间选择的优势, 还能够弥补遗传算法的缺点, 使得在调度方案中跳出局部最优的陷阱。

2.1 编码

编码的对象是工件, 把每个工件看做对应的生物染色体, 而个体的染色体的表示采用矩阵, m×n的矩阵Y=[yij]。i=1, 2, …, m, j=1, 2, …, n (m为工件加工的天数, n为工件的加工顺序) 。一般来说, 任何个体X, 未必有X∈Ω (Ω是设计目标函数中的机器加工最多工件数) 。于是引进贪婪变换G:{0, 1}n→Ω;G (X) =Y= (y1, y2, …, yn) 。若X∈Ω, 则G (X) =X;若X埸R, 则按照ρi=ci/wi (xi=1) 从小到大的次序变换xi=1到xi=0, 一直到正好满足为止, 即得到G (X) =Y。显然X∈Ω是可行解。于是得到混合贪婪算法[5]的遗传算法, 即在原来的遗传算法的搜索的各个步骤加上贪婪变换G。

2.2 初始种群的生成

编码成功以后, 紧接着需要产生一个最优解[6], 作为实际操作中整体的一个个体。

第一步:使矩阵 (工件在任何一天中使用的夹具数记为bij) 的所有元素bij记为0;

第二步:矩阵bij的列方向按降序排列, 依次分析每个工件。

第三步:在第一行的工件, 对于任何一个元素, 完成相应时期的随机选择处理, 然后执行下一个加工工件。

第四步:接着的加工工件需要在完工期限内进行加工, 然后执行下一个工件的处理。

第五步:当所需加工工件的调度处理完成时, 检查刀具、加工时间等条件是否满足, 如果满足结束调度, 否则返回第三步重新进行调度。

2.3 选择操作

对最优化作业车间调度问题的选择上主要依据是适应度计算。对于最小化问题, 常见的适应度函数有F (X) =-f (x) ;F (X) =max (cmax-f (x) , 0) ;F (X) =1/ (1+c+f (X) ) , (c+f (X) ≥0) 等。适应度决定了问题的最优化, 也就是个体生存能力的最强选择。一般在最优化问题上会选择轮盘赌方式, 按实际操作顺序 (即个体Aj的适应度J (Aj) ) 占整个操作顺序 (即 (种群) 总适应度的比例划分整个赌盘, 然后接着转动赌盘N次, 在随机转动轮盘的过程中最好是能够转1圈以上, 这样可以防止转盘不足1圈带来的概率不准确等缺点, 最终选出赌盘的指针所指示的计数 (个体) 。即每次转动赌盘, 选中Aj的概率。在本文中按照适应度函数, 独立地从当前种群中选取M个母体。

2.4 交叉操作

基因重组是来自父代的提供的交配种群中的信息然后重新组合产生新的个体的过程。而每个个体都代表着不同的内容, 他们在实际生产调度中都会有相应的约束, 而在矩阵中代表工件不同操作顺序的某2个个体, 让所有的操作顺序都并列而排出, 选择任何一个交叉点实行交叉即上下交换操作顺序, 代表个体的每个基因都以相同的概率Pc进行交换。

2.5 变异操作

变异就是按个体基因按小概率 (变异概率Pm) 扰动产生的变化, 在变异过程中对整体矩阵实施贪婪变换G (Y (k+1) ) = (G (X1 (k+1) ) , …, G (XN (k+1) ) ) 。实施贪婪变换的矩阵可以满足操作步骤、加工顺序等约束, 但是可能不满足整个加工的完成期限的约束。因此, 还要进行随机交换另外的个体产生新的子个体, 直到满足完工期限的约束。

3 调度实例及模拟结果

现有如下调度问题:机器加工6个工件, 其中在某月的加工计划数据表如表1所示。

在遗传算法中取个体的数目为90, 交换概率Pc=0.98, 变异概率Pm=0.02.群体经过400代的进化, 算法收敛。得到6个工件调度结果的Gantt图 (见图1) 。经模拟计算, 得到该问题的最佳调度如表2所示, 同时可得群体中指标函数最小值为780。

有了数据库中的数据, 可以方便地根据这一数据生成基于工件的甘特图, 图1中横轴表示工件代号, 纵轴表示天数。从甘特图可以看出, 工件在机器的加工上得到了合理的安排, 既提高了机器的利用效率, 又使得工件得以在最短时间加工完成。因此比较符合预期的结果。

4 结论

本文通过在遗传算法中引入贪婪变换, 使得改进后的遗传算法在对作业车间调度问题求解上能够跳出局部最优的陷井, 进而得到最适合的问题求解方法。将实际生产中的作业任务转化为染色体编码串, 引进贪婪变换G, 在原来遗传算法的选择、交叉、变异等步骤中加入贪婪变换, 使得在解的质量和求解速度方面都有非常大的改进, 从而给出了一个适合于生产调度问题求解的新算法。

参考文献

[1]Bhote K R, Bhote A K.World Class Quality:Using Design of Experiments to Make It Happen[M].New York:AMACOM, 2000.

[2]Cai Zixing, Gong Tao.Advance in research on immune algorithms[J].Control and Decision, 2004, 19 (8) :841-846.

[3]曹金全, 初红艳, 费仁元.启发式算法和遗传算法在生产调度中的应用[J].中国机械工程, 2006 (增刊2) :211-214.

[4]阳明盛, 罗长童.最优化原理、方法及求解软件[M].北京:科学出版社, 2006.

[5]周明, 孙树栋.遗传算法原理及应用[M].北京:国防工业出版社, 1999.

作业车间调度篇9

作业车间的调度问题一直是生产管理及组合优化等领域的热点之一。传统的作业车间调度(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算法的比较,证明了该方法的有效性和适应性。

【作业车间调度】推荐阅读：

车间作业调度问题09-14

作业调度07-31

作业调度算法06-23

车间调度问题06-02