当前位置: 圆柱模板 » 建筑资讯 » 工程 » 正文

一种基于改进遗传算法的车间调度问题研究_模拟退火

放大字体  缩小字体 发布日期:2018-11-05T20:19:01  主题关键词:退火  作者:支模网  浏览次数:258
核心提示:论文导读::作业车间调度是一类求解困难的组合优化问题,本文在考虑遗传算法早熟收敛问题结合模拟退火算法局部最优时能概率性跳出的特性,最终使算法能够趋于全局最优。在次基础上,将遗传算法和模拟退火算法相结合

论文导读::作业车间调度是一类求解困难的组合优化问题,本文在考虑遗传算法早熟收敛问题结合模拟退火算法局部最优时能概率性跳出的特性,最终使算法能够趋于全局最优。在次基础上,将遗传算法和模拟退火算法相结合,提出了一种基于遗传和模拟退火的混合算法,并用实例对该算法进行了仿真研究。结果表明,该算法有教好的收敛精度,是可行的,与传统的算法相比较,有明显的优越性。
论文关键词:遗传算法,车间调度,模拟退火
 

1. 引言

作业车间调度(Job Shop SchedulingProblem,JSSP)通常指车间生产过程的作业计划,解决如何合理地分配车间有限的资源,使资源利用率最高,成本最小等问题[1]。随着制造型企业之间竞争的加剧,调度决策水平的高低己经成为现代企业决定生产经营过程能否实现降低成本,对市场实现快速响应,从而实现稳定高效地运转的决定性因素之一。为提高调度水平,新的生产调度策略和优化算法不断被提出并被研究,以提高资源的利用率及操作管理的水平,生产出更具有竞争性的产品。因车间调度优化问题在提高生产效率,降低生产成本等方面至关重要,所以车间的调度优化工作成为现代企业制造中的重要研究课题之一。

2. JSSP问题的数学描述

JSSP问题可以描述为如下:

1)一个工件不能两次被同一机器加工;

2)不同工件的加工工序之间没有先后约束;

3)工序一旦进行不能中断;

4)每台机器一次只能加工一个工件;

5)下达时间和交货期都不是确定的。

问题的数学描述为:

模拟退火 (1)

:机器先于机器加工工件

(2)

工件先于工件在机床上加工

模拟退火, (3)

式中

(4)

其中,式(1)表示目标函数,式(2)(3)(4)表示工艺约束条件决定的各工件的各操作的先后加工顺序以及加工各个工件的各机器的先后顺序。式中,符号分别为工件在机器上的完成时间和加工时间。

3.用改进遗传算法(MGA)求解

3.1编码方式

如何将所研究问题的解转换为由编码形式表达的染色体是遗传算法的关键问题[2]。对JSSP问题,遗传算法的编码常见的有以下几种:基于工序(或操作)的编码、基于工件的编码、基于先后表的编码、基于工件对关系的编码、基于优先规则的编码、基于机器的编码、基于完成时间的编码、随机键编码、基于析取图的编码[3]。这些编码方法都存在这样或者那样的不足,鉴于以上车间调度问题编码方法所存在的问题,提出一个既能保证后代的合法性,又能表征全部解空间,解码又相对简单的编码方法很有必要。本文考虑一个基于工序(或操作)的编码[4,5]方法用来保证搜索空间是一个完整的解空间,并且任何操作者的所有交换可对应于合适调度,对于每个基因对应一道工序,代表该工序在进行调度操作时的处理优先级,对于n个工件m台机器的调度问题,一个染色体由个基因组成。

考虑3个工件和2台机器问题的机器加工次序矩阵:

以及加工的时间矩阵:

假设一个任意基于操作的解分别为s = (1,3,2,2,1,3), 其中1,2和3分别代表工件1,2和3论文开题报告范例。通过一个半活动解码过程[4,5],工件的加工次序对于机器1对应3-2-1,对于机器2对应1-2-3。它们对应的makespan(工件完工时间)为7的甘特图如图1所示:

模拟退火

Figure 1. Halfactivities scheduling correspond to tmakespan

图1 半活动调度对应的makespan

我们认为,活动调度编码是半自主调度编码的一个子集,因此,最优调度方案必须是一个活动调度编码对应的工件完工时间[4]。活动调度编码的应用可以在下一个操作之前检查可能的空白的间隔时间所在最后位置模拟退火,并且在最后操作之前填补前一个空白间隔时间直到最后一个操作转化为半活动调度,导致makespan的长度可以变得更短。 因此,Gantt图(图1)被改变为如下图2所示,同时,对应的makespan 为6 (最优值)。

模拟退火

Figure 2. Activitiesscheduling correspond to tmakespan

图2 活动码调度对应的makespan

3.2解码算法

染色体只包含数字编码。在解码时首先要把基因与工序对应起来,即把优先级赋给对应的工序。

设:——包含t个已调度工序的部分调度;——阶段t可调度工序的集合对应给定的

解码步骤如下:

步骤1:令t=0,开始为空的部分调度。初始的包括无紧前工序的所有工序。

步骤2:比较中所有工序的调度优先级,把具有最大优先级的工序(假设为,其上道工序的结束时刻为)尽可能早的加入到中,即从时刻开始对该工序所对应机器上各加工空闲依次判断能否将此工件插入加工。若能,则在空闲中插入加工,并修改该机器上的加工队列;否则,把该工序加入到该机器加工队列的末尾,构造一个新的部分调度

步骤3:按如下步骤更新数据集

 

 
关键词: 退火 调度 遗传
 
[ 订阅地图 ]  [ 加入收藏 ]  [ 告诉好友 ]  [ 打印本文 ]  [ 违规举报 ]  [ 关闭窗口 ]

 
退火  相关信息
0条 [查看全部]  相关评论

 
推荐图文
浅谈不定积分运算中的灵活性_凑微分法 一类非线性刚性有效的数值求解方法_Brown算法 一类新的自适应信赖域算法_全局收敛性 一种基于改进遗传算法的车间调度问题研究_模拟退火 三角形分布的双方叫价拍卖模型在电力交易中的应用* 两个不同成本结构订货商的供应链协调[1]_订货批量
推荐建筑资讯
点击排行
资讯热搜
产品热搜
百度合作产品

本站点已加入百度原创合作,切勿转载抄袭!