基于数据挖掘技术与petri网建模的车间调度规则提取

《基于数据挖掘技术与petri网建模的车间调度规则提取》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、拟投期刊:基于数据挖掘技术与petri网建模的车间调度规则提取王成龙1，李诚1，冯毅萍1，荣冈1（1.工业控制国家重点实验室浙江人学智能系统与控制研究所，浙江杭州310027）摘要：车间调度（JobShop）问题作为一个复杂的优化命题，至今尚未得出一种具有普适性的求解方法。本文利用时间Petri网络来描述车间调度问题，并利用一种改进的启发式搜索算法搜寻最优的调度方案。在Petri网建模和启发式搜索算法寻优的基础上，结合数据挖掘分类技术，本文提出一种基于petri网建模的车间调度规则提取方法。类似于传统的优先调度规则，本文所提取的调度规则可以直接

2、用于指导车间生产调度过程。通过与利用启发式算法得到的最优结果和利用传统优先调度规则所得到的次优结果进行比较，证明了所提取的调度规则的优越性能和实用性。关键词：车闹调度问题；PetriM；启发式搜索算法；数掂挖掘；调度规则中图分类号：TQ021.8文献标志码：ADispatchingRuleextractionbasedonDataMiningtechniquesandPetri-netmodelingforJobShopProblemWANGChenglong1，LICheng1，FENGYiping’，RONGGang1(1.StateKey

3、LaboratoryofIndustrialControlTechnology,InstituteofCyber-systemsandControl,ZhejiangUniversity,Hangzhou310027，Zhejiang,China)Abstract:Jobshopschedulingproblem，asacomplexoptimizationproposition，hasnotyetcomeupwithauniversalsolutionmethod.Inthispaper，anoveldispatchingruleextrac

4、tionmethodisproposedbycombiningdataminingtechniquewithPetri-netmodelingmethodandheuristicsearchalgorithm.TimedPetri-netisemployedtomodelthejobshopschedulingproblemwhileanimprovedheuristicsearchalgorithmisadoptedtoobtaintheoptimalschedulingscenario.Similartotraditionalpriorit

5、ydispatchingrules,thedispatchingrulederivedinthispapercanbeuseddirectlytoguidejobshopscheduling.Thesuperiorityandpracticalityoftheextracteddispatchingruleareverifiedbycomparingwiththeoptimalandsub-optimalsolutions，whichareobtainedbyfollowingheuristicalgorithmandtraditionalpr

6、ioritydispatchingrules，respectively.Keywords:JobShopschedulingproblem;petri-net;heuristicsearchalgorithm;datamining;dispatchingrule1引言车间生产调度闷题GSSP）是当前制造、Ik中所而临的一个秉要闷题。对车间调度问题的研究始于20世纪50年代，Mellorllj等对:午:间调度W题进行了总结和概述。车间调度问题可以描述为一组山一系列操作所组成的任务在一组机器上的加工顺序安排问题，即机器资源分配问题［1］。车间凋度问

7、题作为一种NP难问题，足一类非常S杂的优化命题。一个好的生产凋度方案可以有效的提高:午:间的生产效率和资源的利用率，改莕车1川的操作管理水平，W此，车间生产调度问题研究一直以来都受到了学者们的普遍关注［2］。传统的车间调度问题研究主要包拈以F三种方法：1.数学规划方法。Kim［3］等提出了描述车间调度问题的混合整数线性规划模型。2.优化算法。传统用于解决车间调度问题的优化算法以分支足界法为主

8、4］。Brucker［51等提岀了一种快速分支定界算法用以解决-个10*10的基准调度问题。似足，当问题规模较大时，以上W种方法均存在解空间爆炸问题，即无

9、法在可接受的吋间内求得调度结果。3.近似优化算法。近似优化算法楚在可接受的吋间范围内寻求凋度问题的近似最优解，如Nowicki［4］等提出-•种快速禁