车间调度中的数据挖掘技术研究

2010，46（22）1引言敏捷制造作为21世纪企业的先进制造模式，综合了JIT、并行工程、精益生产等多种先进制造模式，其目的是要以最低成本制造出顾客满意的产品，是完全面向顾客的。在这种模式下如何进行组织管理，包括如何组织动态联盟、如何重构车间和单元、如何安排生产计划、如何进行调度都是面临的主要问题。其中车间作业调度与控制技术是实现生产高效率、高柔性和高可靠性的关键，有关资料表明，制造过程中95%的消耗是在非切削过程中[1]。因此，有效的调度方法与优化技术的研究和应用，已成为先进制造技术（AMT）实践的基础和关键。调度问题的研究始于20世纪50年代，Johnson[2]提出了解决n/2/F/Cmax和部分特殊的n/3/F/Cmax问题的优化算法，代表调度理论研究的开始；70年代建立了调度理论的主体（经典调度理论）并重视调度复杂性的研究随着70年代后期调度理论研究的深入及各种交叉学科的发展，又涌现出许多新的车间调度理论与方法[3]。Biskup对具有学习效果的单机调度研究揭开了对具有学习效果的调度问题研究的序幕。由于分派合适的规则已成为提高柔性制造系统工作指标的重要问题，Choudhary[4]在一个车间仿真生产过程中提出一种基于知识产生系统行为的数据挖掘和进化优化的方法。Liu等针对属性车间调度中的数据挖掘技术研究王雯1，栾飞1，2，傅卫平1WANGWen1，LUANFei1，2，FUWei-ping11.西安理工大学机械与精密仪器工程学院，西安7100482.陕西科技大学机电工程学院，西安7100211.SchoolofMechanicalandInstrumentalEngineering，Xi’anUniversityofTechnology，Xi’an710048，China2.Mechanical&ElectricalEngineeringCollege，ShaanxiUniversityofScienceandTechnology，Xi’an710021，ChinaE-mail：[e-mail]，LUANFei，FUWei-ping.Studyondataminingtechnologyinworkshopscheduling.ComputerEngineeringandApplications，2010，46（22）：217-220.Abstract：Man-machinecooperationtechnologybasedonMulti-AgentSystem（MAS）issuitabletosolvecomplexschedulingproblems.Inordertobettercompletehighefficientandaccurateshopschedulingbyman-machinecooperation，usingthealgo-rithmC4.5，asimulationmodelofman-machinecooperationsystemofbasedonmachinelearningandMAStechnologyforjobshopschedulingissetupandrealized.ThenusingWeka，JADEasthedevelopmentplatform，intheJavaenvironmentap-plyingEclipseasthedevelopmenttoolsandAccessasthebackgrounddatabase，thedevelopmentofthesystemhasbeencompleted.Thoughsimulationofinstancesandanalysisofexperimentalresult，theresultsofdynamicschedulingbymachinelearningalgorithmisslightlybetterthanthebestresultsofthestaticscheduling，whichprovesthevalidityandsuperiorityofthesystem.Keywords：datamining；machinelearning；man-machinecooperation；shopschedulingMulti-AgentSystem（MAS）摘要：基于Multi-AgentSystem（MAS）的人机合作技术适合于解决复杂调度问题。为了使人与机能够更好地合作来完成高效、准确的车间调度，引入C4.5算法，建立并实现了基于机器学习和MAS的人机合作车间调度系统仿真模型。在Java环境下，以Weka、JADE为开发平台，以Eclipse为开发工具，Access为后台数据库，完成了系统的开发。通过实例仿真和结果分析，运用机器学习算法动态调度的结果稍优于最佳的静态调度结果，证明了系统的正确性和优越性。关键词：数据挖掘；机器学习；人机合作；车间调度；多Agent系统DOI：10.3778/j.issn.1002-8331.2010.22.063文章编号：1002-8331（2010）22-0217-04文献标识码：Ａ中图分类号：TP18基金项目：陕西省教育厅科学技术研究计划项目（theScienceandTechnologyResarchProjectofShaanxiMunicipalEducationCommissionun-derGrantNo.09JK661）；陕西省自然科学基金（theNaturalScienceFoundationofShaanxiProvinceofChinaunderGrantNo.SJ08A32）。作者简介：王雯（1966-），女，博士研究生，副教授，研究方向为供应链系统动力学、现代物流系统工程与技术；栾飞（1983-），男，硕士研究生，助教，研究方向为现代物流系统工程与技术；傅卫平（1957-），男，博士，教授，博士生导师，研究方向为非线性动力学、现代物流系统工程与技术。收稿日期：2010-01-13修回日期：2010-02-23⦾工程与应用⦾ComputerEngineeringandApplications计算机工程与应用217ComputerEngineeringandApplications计算机工程与应用2010，46（22）选择问题提出一种基于模糊数学和遗传算法SAMA方法，开发了一个基于数据趋势估算技术，并把它和放大失真以及基于模糊推理的自适应网络技术结合的系统，由于在加工的开始阶段仅仅能获得很少的数据点，大大提高了敏捷制造系统在小规模数据调度中的精度[5]。在国内，龚宇等从制造领域发展趋势的角度出发，阐述优化车间调度系统的必要性，介绍了一种具有机器学习能力的智能车间调度系统的设计，论述了开发一个具有机器学习能力的车间调度系统能够解决车间调度的知识贫乏问题[6]。谷强提出一个多Agent协同实现、多种学习机制集成的车间调度模型框架[7]。周摄人提出了将数据挖掘技术应用于供应链库存控制当中，对现有的两种重要数据挖掘软件weka和xelopes做了对比分析，选择了weka作为数据分析工具，将weka成功应用到供应链库存控制当中[8]。刘晓华提出了将数据挖掘技术应用于现代物流系统的数据分析当中，将数据挖掘的开源软件weka用来作为数据分析工具，成功地对公司的物流数据进行了分析预测[9]。已有的研究大多停留在智能制造系统中机器学习方法探讨上，有少量对具有机器学习能力的智能车间调度系统的研究，也是通过一些很复杂、特别的方法来达到目的，没能提出一种通用的较为易实现的方法，主要原因有两方面：一是数据挖掘的软件相对较为昂贵，很难找到一种免费的、功能齐全的、开放源代码的数据挖掘软件；二是数据挖掘技术相对较新、较难，需要较强的数学和软件编程能力才能对其进行深入研究。首先对车间调度系统的结构进行了分析，进而建立了基于Agent的人机合作车间调度系统模型；随后将基于weka的数据挖掘技术引入系统当中，建立了基于机器学习的人机合作车间调度系统模型，随后，在Java环境下，以weka、JADE为开发平台，以Eclipse为开发工具，以Access为后台数据库，完成了对系统的开发，为进一步开发实用的机器学习车间调度软件奠定了一定的基础。2机器学习的定义及其结构2.1机器学习的定义学习是人类具有的一种重要智能行为。按照人工智能大师Simon的观点，学习就是系统在不断重复的工作中对本身能力的增强或改进，使得系统在下一次执行同样或相类似的任务时，会比原来做得更好或效率更高。机器学习研究的是如何使机器通过识别和利用现有知识来获取新知识和新技能[10]。2.2机器学习系统的基本结构现在以Simon的学习定义作为出发点，建立如图1所示的简单的学习模型。图1表示学习系统的基本结构[11]。环境向系统的学习部分提供某些信息；学习部分利用这些信息修改知识库，以增强系统执行部分完成任务的效能；执行部分根据知识库完成任务，同时把获得的信息反馈给学习部分。在具体应用中，环境、知识库和执行部分决定了具体的工作内容，学习部分所需要解决的问题完全由上述三部分确定。3机器学习模型的建立3.1C4.5算法原理C4.5算法的工作过程为：首先在数据集中找出使得数据的信息增益率最大的属性作为根节点，对数据进行分类得到多个子集，在每个子集中，又通过计算选择出使信息增益率最大的属性，将子集进行分类，一直进行到所有子集仅包含同一类型的数据为止，并且在分类的过程中对模型中错误分类的实例进行修剪，最后得到一棵修剪后决策树[12]，可以用它来对新的样例进行分类。3.2机器学习模型的建立在建立模型之前，先定义一个重要的概念——学习实例采样点。学习实例采样点是调度过程中的一类特殊时刻，在这类时刻TIMEc，某一加工任务LOADc的某一工步JOB-STEPc加工完成，某一个资源RESOURCEc得到释放，并且此资源前面的等待队列的长度大于1。显然某一调度时刻是采样点时刻，是在该时刻需要进行规则选择的充要条件。采用机器学习C4.5算法为学习的核心算法来进行分类学习，首先将已有的人类专家的调度经验进行相对化处理，生成学习实例集，进而调用weka软件的C4.5算法来对其进行分类学习生成决策树相应模型。以此为基础，在车间加工的过程的采样时刻点，计算出车间当前的相应状态参数，将其转化为学习实例的形式，进而调用机器学习模块来完成对其的学习预测，随后，设备依据预测的结果来完成对待加工工件的排序，机器学习模块的结构如图2所示。4基于weka机器学习的车间调度系统模型实现及其关键技术4.1基于机器学习的车间调度系统模型车间调度系统是一个庞大的、离散性系统，从它的构成来看有管理模块和设备模块。在管理模块中，它要进行订单信息接收、生产调度、设备状态的监控、各设备之间关系的协调、对紧急事件的应急处理等；在设备模块中，包括机床、装卸机器人、流水线以及相关的辅助设备等；各个模块从系统开始运行起，都要进入工作的状态，只要满足一定的条件，该模块就要去完成相关的任务。对于这样一个复杂的系统用MAS进行建模比较方便一些，如图3为用MAS技术对系统建模后得到的系统模型图。4.2系统实现的关键技术实现基于机器学习人机合作车间调度系统，所涉及的关键技术主要包括：weka平台下，机器学习C4.5算法的实现技术、weka平台与Agent的实现平台JADE之间的集成技术。程序要实现机器学习智能决策的功能，首先要解决的问题就是机器如何学习，这里采用数据挖掘软件weka来达到这环境学习知识库执行图1学习系统的基本结构已有调度经验学习实例相对化计算C4.5算法分类学习决策树模型新的学习实例车间当前状态相对化计算文件转换分类预测前后排序调度规则设备加工图2机器学习模块结构图2182010，46（22）一目的，要让weka实现对程序当中输出数据进行学习分析，首先必须要将输出数据转换成weka软件能够处理的形式输入软件，这其中需要一个文件