当前位置：文档之家 › 用于柔性流程工业生产调度的并行多目标遗传算法

用于柔性流程工业生产调度的并行多目标遗传算法

  • 格式：pdf
  • 大小：181.01 KB
  • 文档页数：7

　2001年6月系统工程理论与实践第6期　文章编号:100026788(2001)0620007206

用于柔性流程工业生产调度的并行多目标遗传算法

李艳君,吴铁军(浙江大学智能系统与决策研究所,浙江杭州310027)

摘要:　分析了柔性流程工业区别于一般制造系统在生产调度方面的特点,在此基础上针对这类系

统所具有的多目标、混合动力学特性、调度实时性等特征,提出了一种新的并行多目标遗传算法Λ在解决多目标解的评价时,采用了目标分级评价技术,求解过程始终将解的最优性和决策者对目标的偏好信息结合在一起Λ为反映这类问题的混合特性,提出了一种新的双层编码方案Λ在算法中采用的递阶分解并行技术,使计算时间至少减少一个数量级Λ计算机仿真结果表明,对于这一类复杂的柔性流程工业生产调度优化问题,本文提出的方法具有很好的实际应用前景Λ关键词:　多目标优化;遗传算法;过程调度;并行计算

中图分类号:　TP202 文献标识码:　A

α

ANovelParallelMulti2ObjectiveGeneticAlgorithmforProcessIndustryProductionScheduling

LIYan2jun,WUTie2jun(InstituteofIntelligentSystemsandDecisionMaking,ZhejiangUniversity,Hangzhou310027,China)

Abstract　Thispaperanalyzesthefeaturesoftheproductionschedulingproblemsinprocessindustrieswhicharedifferentfromgeneralmanufacturingsystems.Aparallelmulti2objectivegeneticalgorithmisproposedbasedonthedistinctivecharacteristicsoftheprocessscheduling,suchasmultipleobjectives,hybriddynamicsandrealtimecomputation.Anobjectiverankingevaluationtechniqueisdevelopedtoassociatethetradeoffinformationtoabettersolutionwithpreferencearticulation.Anoveldouble2layerchromosomecodingmethodisusedtoexpressthesystemhybridness.Computationtimeisatleastreducedto10percentofitsoriginalvaluebyadoptingahierarchicaldecomposedparallelcomputingtechnique.Simulationresultsshowthatthealgorithmillustratedinthispaperhasaprospectivefutureintheapplicationstosuchcomplexoptimizationproblemsinprocessscheduling.Keywords　multi2objectiveoptimization;geneticalgorithm;processscheduling;parallelcomputation

1　引言随着市场经济体制的迅速发展,流程工业企业如炼油、化工、造纸、酿造、制药等行业的生产运行方式已经发生根本性的变化,这主要表现从按长期的、规律性的生产计划组织生产,转变为按短期的、带有随机性和突发性的订货合同组织生产;从以大批量、单一品种、规范规格为特征的生产方式,转变为以小批量、多品种、不规范规格为特征的生产方式;从生产控制的重点为保证生产方案的实施,转变为在有限的原材料供应、能源、人力、资金和仓储等生产资源约束的情况下最大程度获取经济效益Λ因此柔性流程工业在新的模式下的生产计划和生产调度,即在给定的连续生产约束条件下,根据生产状态、市场需求、原料供应情

α收稿日期:1999211212

资助项目:国家高科技研究发展计划(863-511-845)© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.况的变化,及时地调整生产方案(包括设备操作条件、工艺方案、产品种类、生产计划等),以获取最大的综合经济效益,是一个具有挑战性的重大课题[1]Λ由于实际生产运行控制的优化目标中,有些可以以明确的数学公式定量地表示,而有些难以测定,甚至难以明确地加以定义,使得人们难以直接利用经典的数学规划方法来求解Λ在这一领域,以遗传算法为代表的进化计算方法,模拟自然界生物种群进化的过程,因此不需要关于待求解问题精确的、解析的数学模型,以及诸如连续性、导数存在和单峰等假设条件;此外,算法还具有搜索过程并行性,可以通过编码技术和繁殖机制,以较高的效率来解决此类困难的优化问题,包括多目标优化问题[2-4]Λ

2　柔性流程工业生产调度问题描述在市场经济条件下,柔性流程工业生产线的生产模式通常是面向订单(Order2oriented)

的,为简化问题

的表达起见,在本文中将柔性流程工业生产调度问题的命题描述如下Λ命题2.1　设已到达L个订单,其中第l个订单Ol可以四元组Ol={Sl,Vl,Tl,Cl}表示,l=1,2,…,

L;其中Sl为订货规格,Vl为订货数量,Tl为交货日期,Cl

为延期交货的罚金(以单位时间累计)Ζ一个生产

方案P可以表示为生产线中一系列子任务的一个列表P=

(

P1,P2,…);子任务P

i

的内容可表示为一个

三元组pi={si,vi,ti},该三元组中各符号依序代表加工规格、加工数量和起始加工时间Ζ设订单Ol的完工期为Fl,订单Ol在交货期到达时完成的数量为ZlΖ根据柔性流程工业生产调度的特点,求解命题2.1需解决以下问题:

2.1　多目标问题柔性流程工业生产调度通常面临多个优化目标,有些可以以明确的数学公式定量地表示,如在命题2.1中,我们可考虑以下目标:第一,最小化延期交货的总罚金,即:min6Cl3(Vl-Zl)(1) 第二,总交货时间最接近各订单规定,即:

min6󰃜Te-Fe󰃜(2)而有些目标难以明确地加以定义,例如最小化生产方案切换导致的各装置总冲洗时间和冲洗用物料消耗这一目标Ζ因此为保证生产方案的实施,需要在有限的原材料供应、能源、人力、资金和仓储等生产资源约束的条件下,根据生产状态、市场需求、原料供应情况的变化,从多目标优化角度考虑问题,最大程度获取综合的经济效益Ζ2.2　生产过程特性柔性流程工业的生产调度与一般的调度过程不同,它通常(在系统动态学的意义上)包括两种性质不同的部分:连续时间过程;这一部分代表了柔性流程工业生产装置的大部分机理特性,即生产中的过程状态随着时间和外部输入的改变连续地发生变化,从而使其与机械部件加工装配生产线等有不同的特点Λ离散事件过程;这一部分代表了柔性流程工业生产装置遵守生产计划和调度的指令而切换其生产方案的过程特性,即调度状态随着生产过程中发生的事件(如预定任务的完成)和外部输入的改变间断地发生变化,

从而实现了同一作业线生产不同的产品的柔性生产Λ通常情况下柔性流程工业生产线的以上两种过程特性是交互影响的,生产中连续状态的变化与生产方案的切换有关,同时生产调度状态的变换也受到连续生产过程的影响Λ因此从整体上看,柔性流程工业生产线呈现一种混合动力学系统(HybridDynamicSystem)

的特性Λ这一特点使人们难以直接利用在制造系统生产调度领域已有的研究成果来解决柔性流程工业生产运行控制问题Λ例如在命题2.1中,对于生产方案P来说,子任务pij={si,j,vi,j,ti,j}中的加工数量vij是一连续变量,

产品的加工规格sij代表不同产品之间的切换,是一离散变量Ζ因此生产调度优化过程中对于子任务加工数量的划分是实数空间R+上的连续变量优化问题,而加工规格切换方式的优化是一个整数空间Z+上的组合优化问题,从而给这一命题的求解带来很大困难Ζ

8系统工程理论与实践2001年6月

© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.2.3　对求解速度的要求由于命题2.1的求解是一个兼有组合优化和连续变量优化的复杂问题,同时实际的柔性流程工业生产调度问题中产品的加工规格sij和加工数量vij的搜索空间很大,不可避免地带来组合爆炸问题Ζ此外,目前柔性流程工业企业是按短期的、带有随机性和突发性的订货合同组织生产,因此命题2.1的优化必须考虑求解的速度,以满足对突发事件(如一个订单Ol的到达)进行生产调度实时性的需要Ζ以上两方面是互相矛盾的,因此寻找新的、可综合处理这两方面需求的优化算法对解决命题2.1的问题是至关重要的Ζ

3　并行多目标遗传算法遗传算法是近年来特别引人注目的一种适用于解大型组合优化问题的技术Ζ根据对第二节中命题2.1

求解问题的特点,本文提出一种并行多目标遗传算法Ζ以下是该算法关键技术的说明,以及基于这些关键技术的并行多目标遗传算法具体步骤Ζ3.1　一种染色体的编码方案遗传算法求解命题2.1的第一步就是选取一个适当的解的表示方案Ζ根据本问题中解的混杂特性(解由连续变量和离散变量两部分构成),本算法中染色体由两类基因构成,分别代表第R种求解方案中第l

种订单在第i种数量分配下的加工规格和加工数量Ζ整个染色体设计为双层结构,上层由规格基因组成,每一位基因为一整数,代表了加工规格SRli;下层由数量基因组成,每一位基因为一实数,代表了相应的加工数量VRliΖ遗传算法求解时,染色体数量基因的生成采用随机分配策略Ζ这里,对于第R种求解方案,首先

将订单l∈[1,L]随机划分为NRl块,NRl∈[1,Vl],因此染色体的长度等于6L

l=1NRl;然后确定每一子任务相

对于分配因子ΚRli的加工数量VRli的大小,即:

VRli=Vi3ΚRli

(3)

对订单Ol来说,

6NRl

i=1ΚRli=1Ζ然后通过交换染色体基因的位子产生遗传操作的种群Ζ这里子任务的加工数

量定义为所有具有相同规格、相邻的数量基因所对应的实数之和,加工规格即为相应的规格基因Ζ在加工顺序的考虑中,将子任务执行的顺序隐含在编码方案中,即每个子任务相应的染色体基因在整个串中的顺序就代表了它的加工顺序Ζ表1给出了某一个染色体的产生方法Ζ表1　实数编码方案

合集下载

面向无等待多目标柔性车间调度问题的遗传蜂群优化算法

面向无等待多目标柔性车间调度问题的遗传蜂群优化算法

面向无等待多目标柔性车间调度问题的遗传蜂群优化算法毕孝儒;张黎黎;贺拴;贺艳果【摘要】为了解决无等待柔性车间调度的多目标优化问题，构建以最大完工时间、生产成本、总拖延时间为目标函数的多目标调度模型，结合灰色关联分析和熵理论，提出灰互信息适应度值分配策略，以评价Pareto解的优劣。

在此基础上，运用遗传蜂群优化算法求解，该算法给出以关键路径为导向的变异操作，并将该变异操作和遗传算子中的IPOX和MPX交叉操作嵌入到人工蜂群算法中，以增强其全局寻优能力，提升搜索后期收敛速度。

一个车间调度实验验证调度模型和算法的有效性和适应性。

%To solve no-wait and multi-objective flexible flow shop scheduling problem(NWMFJSP), proposes an optimization model, which takes fin-ished time of maximum, machine cost and total delayed time as the objectives. Then presents the distribution strategy of the grey mutual information relational adaptive value combined with the grey correlation and information entropy to evaluate feasible solution. Based on it, applies genetic artificial bee colony algorithm(GABC) to solve the problem, the algorithm, which presents the mutation based on key path, embeds artificial bee colony with the nutation, IPOX and MPX crossover to enhance ability to search optimal solution globally and raise convergence rate inlate search. The validity and adaptability of the scheduling structure and algorithm are proved by a case of job-shop scheduling.【期刊名称】《现代计算机（普及版）》【年(卷),期】2015(000)008【总页数】6页(P11-16)【关键词】无等待柔性车间调度;多目标优化;遗传蜂群优化【作者】毕孝儒;张黎黎;贺拴;贺艳果【作者单位】四川外国语大学重庆南方翻译学院管理学院，重庆 401120;四川外国语大学重庆南方翻译学院管理学院，重庆 401120;四川外国语大学重庆南方翻译学院管理学院，重庆 401120;四川外国语大学重庆南方翻译学院管理学院，重庆 401120【正文语种】中文当前，无等待柔性车间调度问题（No-Waiting Flexible Flow Job-Shop Scheduling Problem，NWFJSP）广泛存在于塑料塑造、钢铁铸造、化工制造等领域，它不仅需要确定工序的加工顺序，还要给每个工序分配机器，是更为复杂的NP-hard问题［1］。

基于遗传算法的柔性装配线优化布局

基于遗传算法的柔性装配线优化布局

基于遗传算法的柔性装配线优化布局引言柔性装配线是现代工业生产中一种智能化、高效率的生产模式。

其成功的关键之一是合理的布局设计。

在柔性装配线布局设计中，如何将工位的安排与生产效率和资源利用率达到最佳匹配是一个重要的挑战。

本文将基于遗传算法的优化方法，探讨柔性装配线的优化布局。

一、柔性装配线的定义与特点1.1 柔性装配线的定义柔性装配线是指由多个可以执行不同任务的工位组成的生产线。

在柔性装配线上，工位可以根据产品需求进行自动调整和重新布局。

1.2 柔性装配线的特点柔性装配线具有以下特点：灵活性高、资源利用率高、生产效率高。

二、优化布局的目标与限制2.1 优化布局的目标优化布局的目标是提高资源利用率和生产效率，减少工位之间的物料输送距离和时间，提高整个装配线的工作效率。

2.2 优化布局的限制优化布局的限制包括：工位数量限制、工位布局的限制、物料输送的限制等。

三、基于遗传算法的柔性装配线布局优化方法3.1 遗传算法的原理遗传算法是一种模拟生物进化过程的优化算法。

它通过模拟进化过程中的选择、交叉和变异等基本操作，逐步搜索到最优解。

3.2 遗传算法在柔性装配线布局中的应用在柔性装配线布局优化中，可以将柔性装配线视为遗传算法的一个个体，通过遗传算法的基本操作，不断调整工位的顺序和布局，以寻找最优解。

四、柔性装配线布局优化的具体步骤4.1 定义适应度函数适应度函数用来评价每个个体的适应程度。

在柔性装配线布局优化中，可以将适应度函数定义为资源利用率和生产效率的综合考虑。

4.2 生成初始种群初始种群是遗传算法的起始点。

在柔性装配线布局优化中，初始种群可以通过随机生成不同工位的排列组合形成。

4.3 进行选择、交叉和变异操作通过选择、交叉和变异等操作，可以模拟生物进化过程，搜索到更好的解。

选择操作根据适应度函数的值进行筛选；交叉操作将两个个体的某一部分交换；变异操作对某个个体进行随机变动。

4.4 迭代优化通过不断重复选择、交叉和变异操作，直到达到终止条件，进行迭代优化。

柔性作业车间调度问题简明分析

柔性作业车间调度问题简明分析


1、编码
1、编码
在遗传算法中，问题的解需要用二进制或十进制的编码来表示。在柔性作业 车间调度问题中，我们可以将生产任务和生产设备分别用二进制或十进制的编码 表示，每个编码对应一个任务或设备。
2、初始种群生成
2、初始种群生成
遗传算法的初始种群是随机的，可以通过随机分配任务和设备来生成。在生 成初始种群时，需要保证每个任务都有对应的设备，每个设备都有对应的任务。
四、结论
四、结论
本次演示提出了一种新型的柔性作业车间调度方法——基于遗传算法的柔性 作业车间调度方法。该方法通过采用遗传算法作为优化算法，能够找到最优的调 度方案，提高生产效率和降低生产成本。通过应用案例的验证，该方法具有很高 的实用价值和推广价值。
谢谢观看
柔性作业车间调度问题简明分 析
01 引言
03 问题分析
目录
02 概念解析 04 技术实现
05 案例分析
07 参考内容
目录
06 总结
引言
引言
在现代化制造业中，柔性作业车间调度问题一直是生产过程中的核心难题之 一。该问题的合理解决有助于提高生产效率、降低成本、增强企业竞争力。本次 演示将对柔性作业车间调度问题进行简要分析，旨在帮助读者更好地理解和解决 这类问题。
结论
结论
本次演示对车间作业调度的技术问题进行了简要的综述。尽管在调度算法、 任务分配和调度优化等方面取得了一定的研究成果，但仍存在许多挑战和需要进 一步探讨的问题。例如，如何针对实际生产环境中的动态变化进行调度优化，
结论
如何综合考虑多个优化目标等问题。此外，随着智能制造技术的发展，如何 将先进的人工智能方法应用于车间作业调度也是一个值得研究的方向。
5、交叉操作
遗传算法解决调度问题GA_图文

遗传算法解决调度问题GA_图文


典型优化问题的模型与算法-R03
3
经典调度问题的分类
流水车间调度问题 作业车间调度问题 机器调度问题
扩展调度问题：
群体作业调度 资源约束的项目调度 多处理器调度 车辆与路径调度 ……
典型优化问题的模型与算法-R03
4
制造业生产模式
按生产计划方式分类
面向订单生产，
在实际的生产调度系统中存在很多随机的和不确定的因素，比如 作业到达时间的不确定性、设备的损坏/修复、作业交货期的改变 、紧急定单等。
多目标性:
实际的计划调度往往是多目标的。生产调度的性能指标可以是成 本最低、库存费最少、生产周期最短、生产切换最少、设备利用 率最高、最短的延迟，最小的提前或者拖期惩罚等。这种多目标 性导致调度的复杂性和计算量急剧增加。
典型优化问题的模型与算法-R03
17
GA求解--Gen-Tsujimura-Kubota方法
编码
采用工件的换位表达，此类问题的自然表达方法。
1: 2: 3: 4:
vk = 3 2 4 1
表示工件的加工顺序为： j3j2 j4 j1
调度S为：
S = (t31(0-3), t21(3-4), t41(4-10), t11(10-15), t32(3-9), t22(9-11), t42(11-16), t12(16-20))
Cut point
parent 1 1 2 3 4 5 6 7 8 9
offspring 1 2 3 4 5 7 9 6 8
parent 2 4 5 7 1 3 9 2 6 8
典型优化问题的模型与算法-R03
20
GA求解--Reeves方法