改进遗传算法解决柔性作业车间调度问题

第14卷第2期2009年4月工业工程与管理

IndustrialEngineeringandManagementVol.14No.2 Apr.2009

文章编号:1007-5429(2009)02-0059-08

改进遗传算法解决柔性作业车间调度问题

刘 琼,张超勇,饶运清,邵新宇

(华中科技大学机械学院数字制造装备与技术国家重点实验室,武汉430074)

摘要:柔性作业车间调度问题是经典作业车间调度问题的扩展,它允许工序在多台机器中的任意一台上加工。针对柔性作业车间调度问题的特点,提出一种扩展的基于工序的编码及其主动

调度的解码机制,并设计一种初始解产生机制和两种有效的交叉和变异操作。为了克服传统遗传算法早熟和收敛慢的缺点,设计了精英解保留策略和子代产生模式结合的改进遗传算法应用于该调度问题。最后运用提出的算法求解基准测试问题验证算法的有效性。

关键词:柔性作业车间调度;遗传算法;交叉操作;变异操作中图分类号:TP301 文献标识码:A

FlexibleJob-ShopSchedulingProblemwithImprovedGeneticAlgorithm

LIUQiong,ZHANGChao-yong,RAOYun-qing,SHAOXin-yu

(StateKeyLaboratoryofDigitalManufacturingEquipment&Technology,SchoolofMechanicalScienceandEngineering,HuazhongUniversityofScienceandTechnology,Wuhan430074,China) Abstract:TheFlexibleJob-shopSchedulingproblem(FJSP)isageneralizationoftheclassicalJSP,whereoperationsareallowedtobeprocessedonanyamongasetofavailablemachines.AccordingtothecharacteristicsoftheFJSP,anextendedoperation-basedcodinganditsdecodingmechanismofactiveschedulingispresented.Also,amechanismofgeneratingtheinitialsolutionsandtwoeffectivecrossoveroperatorsandmutationoperatorsaredesignedforthegeneticalgorithm.Inordertopreservethegoodcharacteristicsofthepreviousgenerationandreducethedisruptiveeffectsofgeneticoperators,animprovedgeneticalgorithmwhichcombineselitistmodelandgenerationalterationmodelofgeneticalgorithmisproposedtosolvetheFJSP.Theproposedalgorithmistestedonasetofstandardinstancetakenfromtheliteratureandcomparedwithotherapproaches.Theresultshaveshowntheeffectivenessofthealgorithms.

Keywords:flexiblejob-shopschedulingproblem;geneticalgorithm;crossoveroperator;mutationoperator

SchedulingProblem,JSP)的优化。在经典JSP中,每个工件的工序顺序是预先确定,并且每道工序在指定的机器上加工。而在实际生产中,允许工序在多台机器中的任意一台上加工,这类问题就是柔性

作业车间调度问题(FlexibleJob-ShopScheduling

1 引言

生产调度优化是先进制造技术和现代管理技术的核心技术,国内外许多学者进行了研究,但是大多

数研究针对的是经典作业调度问题(Job-Shop

收稿日期:2008-04-20; 修回日期:2008-11-30

基金项目:国家高技术研究发展计划(863)(2007AA04Z107,2007AA04Z190);国家自然科学基金(70772056)作者简介:刘琼(1965-),女,重庆人,博士,副教授,主要研究方向为物流管理、网络协同设计与制造。

)

第14卷刘 琼,等:改进遗传算法解决柔性作业车间调度问题

Problem,FJSP)。FJSP减少了机器约束,扩大了可行解的搜索范围,增加了问题的难度。

FJSP是经典JSP的扩展,它不仅需要确定工序加工的顺序,还要给每个工序分配机器,因此是比JSP更复杂的NP-hard问题[1]。目前,解决的方法主要可归为两类:精确方法和近似方法。精确方法包括分支定界法、整数规划法等,但只能求解较小规模的FJSP问题。近似方法包括优先分配规则法、遗传算法、禁忌搜索算法和模拟退火算法[8]等,能较快地得到问题的较优解,满足实际问题的需要。目前求解FJSP的近似方法可以分为两类:分级方法和集成方法。分级方法的原理主要基于每道工序的加工机器确定后,FJSP就转化为经典的JSP[7];集成方法是将分配工序机器(路径柔性)和确定工序在机器上的加工顺序同时考虑,该方法难度较大,但是一般能得到更好的结果

[6]

[2]

[3-5]

[6,7]

能指标:最大完工时间Cmax(Makespan)最小、机器最大负荷(Workloads)最小和总拖期(totaltardiness)时间最小,在实际应用中可针对具体问题

要求选择相应的性能指标。

表1 柔性作业车间调度问题的加工时间表

工件

工序O11

J1

O12O13O21

J2

O22O23O31

J3

O32O33

加工时间

M13)22)))))

M2)3)355)24

M3524463355

M449234)6)2

M56)3)43)44

。

遗传算法借鉴了/物竞天择、适者生存0的进化准则,具有隐含并行性和全局解空间搜索的特点,在生产调度领域得到广泛的应用。但是FJSP问题不仅要给给每个工序分配加工机器,还需要确定每台机器上工序的加工顺序,比传统的调度问题更具复杂性。尽管目前国内外已有许多学者进行了研究,但如何利用遗传算法高效求解FSJP,仍被认为是一个具有挑战意义的课题。本文针对FJSP的特点,提出了有效的编码、解码和初始解产生机制,设计了两种交叉和变异操作,运用一种改进遗传算法解决不同目标的FJSP问题,并通过求解基准实例验证算法的有效性。

对于n个工件、m台机器的柔性作业车间调度问题,这三种性能指标如下。

(1)设Ci是工件Ji的完工时间,则最大完工时间Cmax最小的目标函数为:min{maxCi,i=1,,,n};

(2)设Wj是机器Mj上的负荷(或机器Mj上的工作量),则机器上最大负荷WM最小的目标函数为:min{maxWj,j=1,,,m};

(3)设Di为工件Ji的交货期,则工件总拖期时

n

间最小的目标函数为:miniE(max{Ci-Di,0})。=1

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

柔性作业车间调度问题可描述如下:n个工件

在m台机器上加工,每个工件分为k道工序,每道工序可以在若干台机器上加工,并且必须按一些可行的工艺次序进行加工;每台机器可以加工工件的若干工序,并且在不同的机器上加工的工序集可以不同。调度的目标是将工件合理地安排到各机器,使系统的某些性能指标达到最优。此外,在加工过程中还需满足以下约束条件。

(1)每台机床一次只能加工一个工件;

(2)工序一旦进行不能中断;(3)假定工件之间具备相同的优先级;(4)不同工件的工序之间没有先后约束。

一个3个工件在5台机器上加工的柔性作业车间调度实例如表1所示。本文考虑以下常用的性)

)

3 基于改进遗传算法的柔性作业车间

调度问题

3.1 初始解

由于FJSP问题的复杂特性,初始解质量对于算法求解FJSP有很大影响,随机的初始解群体通常提供较差质量的解。目前初始解一般采用Kacem等提出的局部(localization)化方法

[4]

,这种

方法同时考虑每台机器的最小加工时间或总加工时间产生调度解,但是该方法产生的解缺乏多样性,可能使算法早熟而无法求出最优解。本文提出一种简单实用的初始解产生策略:首先随机产生工序的加工顺序,然后在每个工序的机器集中随机选择两台机器,如果产生的随机值(在0~1之间随机产生)小于0.8,则选择加工时间短的机器,否则选择加工时间长的机器。测试结果显示这种初始解产生机制不仅能达到更好效果,并且增加了解的多样性。

工业工程与管理第2期

3.2 编码和解码

编码是遗传算法成功实施优化的首要和关键问题。对于传统的JSP现在应 …… 此处隐藏：13839字，全部文档内容请下载后查看。喜欢就下载吧 ……