基于本体的生产调度建模及XML描述

蒋易强

（1.乐山职业技术学院机电工程系四川乐山614000；2.四川大学制造科学与工程学院四川成都610065）

调度问题多为复杂的优化组合问题，应用于多个领域，主要包括制造、电力、通信、交通、水利、港口等领域。生产过程调度是研究最为深入的领域之一。为适应运筹管理、优化、自动化及计算机技术发展，生产过程调度是整个先进生产制造系统的核心。有效的调度及优化方法研究及应用对缩短产品生产周期、确保产品交货期、降低生产成本等均具有重要的意义；它是实现先进制造和提高生产效益的基础和关键。

生产过程调度方法研究是生产过程调度问题研究的核心内容，主要包括生产过程调度问题的建模方法及其优化方法。生产过程调度问题的传统建模方法主要包括数学规划方法、排队网络、Markov链、Petri网和仿真方法等［1］。当实际生产过程环境过于复杂，生产过程调度问题通常表现为多约束、多目标的优化问题。基于上述传统建模方法建立的生产过程调度模型的规模一般比较大。随着模型的规模增长，求解的工作量呈指数级增长，调度时间的要求难以满足。因此，传统建模方法均难以得到有效应用。

目前，生产过程调度建模还存在以下诸多问题。（1）调度问题的复杂性和系统求解思想往往为研究者所忽视［2］。（2）现有建模方法难以同时处理数据和语言两方面的信息，并且缺少统一的系统模型，而且调度研究的分类经常是模糊不清的，某些调度研究是在很具体的层次上，通用价值很小［3］；（3）重复编码现象严重、开发效率低是生产调度管理软件开发面临的一大难题［4］。因此，迫切需要进一步研究适应于复杂生产过程调度需求的调度问题建模与优化方法。

针对上述问题，提出基于本体的生产过程调度的建模思想。目前，本体在机械制造行业的应用主要集中在企业本体、工程设计本体、产品本体、产品设计资源本体和（分布式）工作流程本体等。下面研究生产调度问题的本质、描述、概念，确定本体的领域和范围，抽出领域中重要概念术语，规范概念及概念之间在领域中的关系，然后建立本体模型。为构建一个调度问题的统一语义模型，生产调度模型的构建采用本体思想，建立本体的效率得到提高，大规模调度对模型的共享和重用的需求得到有效满足，进而提高集成过程中的自动化程度［5］。

一、关于本体的概述

本体原本是哲学理论上的一个术语。它是以体系化的形式说明万事万物及其关系的学说。通过收集相关领域信息，提炼出领域知识的共同内涵，确定共同概念，最后把这些共同概念和概念之间的关系表达在形式化模式的不同层次上是建立领域本体的目标。从内涵上来看，本体作为领域内不同主体（人、代理、机器等）之间达成的共识，是其进行交流的语义基础。领域内公认的实体概念的有限集合是本体模型的核心，通过概念实体间的关联关系来表达领域内公认的语义信息。

二、生产调度问题核心概念

一个领域内公认的本体概念集是本体模型的核心，通过该集合中的概念本体之间的关联关系来表达领域内公认的语义信息。概念提炼过程包括对生产调度领域内的信息的收集、挖掘、整理，以及重要信息和概念的确定、整合等步骤，形成领域本体的核心概念集；然后用精确的图表或术语表示重要概念之间的基本关系，从而使得抽取的概念能被生产调度有关人员所共同理解。概念本体构建是本体模型的基础，整个模型是否具有共享性和重用性将由其是否成功构建决定。

关于调度问题的典型概念描述：生产过程调度问题是指在满足工艺和资源等相关约束条件下，通过确定各工件的加工机器和在相应机器上的加工顺序、加工开始时间、工件组批方式和投料策略及其他关键资源的使用计划等调度策略，使某个或多个调度性能指标达到最优［1］。

关于生产调度的本质问题的表述如下：涉及任务、资源和时间等三维空间的多目标决策是单元制造任务调度问题的本质。工件在其关联设备上的加工顺序和时间在制造单元有限资源的约束下被确定，以实现调度目标（如最短完工时间、最小成本等）的最优是其目标［6］。

在形式化描述方面，调度就是在满足约束条件下，在各机器上合理地安排加工工序，并合理地安排加工时间和次序，同时优化性能指标。因此，可以作如下形式化描述：调度问题及其扩展问题可用三元组α／β／γ的形式进行描述，其中α代表机器工作的环境，工件的加工特性用β表示，加工性能指标用γ表示［7］。

生产调度本体模型的构建主要体现在对相关领域本体概念的抽取和关系的继承，抽取概念时，要在尽量简化本体的同时使得本体尽量包含足够多的信息。从生产调度问题的本质、描述、概念中抽象出以下核心概念类：任务（Task）、指标（Index）、规则（Rule）、方案（Schedule）和资源（Resource）。本体的存在是依赖于生产调度过程而存在的。本体的内容、概念、联系也会随着调度和用户需求的变化而变化，因此本体需要根据调度和用户需求变化进行自适应评价和修订，以保证调度的有效共享。

三、生产调度本体关系模型

根据前文分析，从生产调度问题中抽象出以下核心概念类：任务、指标、规则、方案、资源。核心概念类及相互关系为：以所需完成生产任务为导向，将任务分解为各类指标，这些指标必须满足约束规则，在规则的约束下优化组合成方案，根据方案分配资源，最后资源执行方案，完成生产任务。调度概念本体模型的框架如图1。

图1 调度概念本体模型框架

四、概念集的XML表达

本体模型的概念及其之间关系常常用框架方法表示，这正好对应XML的树型文档结构；其次，本体模型对知识描述的要求有丰富的扩展性和内部关联性，XML文档结构也非常适合以上要求；再次，因为XML有严格而规范的操作处理，定义、使用、处理和共享基于XML的本体模型变得更加简便［8］。所以，生产过程调度的本体模型采用XML格式表达。

用XML格式表示以上本体模型中概念集，下面具体以任务集为例研究本体模型表达。通过对任务逐级分解，形成的任务集合如下：

Task＝｛TaskInfo，T＿RelSet，SubTask1，Sub－Task2，…，SubTaskn｝

其中Task是指生产调度任务；TaskInfo表示任务的基本信息描述；T＿RelSet是指活动或子任务之间的关系集，表达子任务之间约束、时序或分解关系；SubTaski（i＝1，2，…n）表示经过任务分解后形成的活动或子任务。

任务信息描述包括任务名称（TaskName）、任务特征（TaskFeature）、任务类型（TaskType）、服务质量（TaskQuality）及其任务数量（TaskQuantity）等，用以下五元组形式表达：

TaskInfo：：＝（TaskName，TaskFeature，Task－Type，TaskQuantity，TaskQuality）

以上任务集的形式化描述，采用XML表达的主要片段如下：

通过分析生产过程调度建模存在的问题，提出基于本体思想的模型建立方法。首先通过收集生产调度领域内的相关信息，然后充分掌握该领域内知识，整理所有领域概念和信息，最后确定、整合、抽取核心概念和信息；在充分理解领域知识之后，该领域中重要概念之间的基本关系被整理，建立了领域本体构建框架模型和本体概念类框架模型，并用精确的图表或术语表示领域本体的核心概念；从而使得被抽取的概念能被生产调度有关人员所共同理解。为调度问题的构建提供统一的语义模型，并用XML进行表达，实现调度组合的语义一致性，有效满足了大规模调度对模型的共享和重用的需求。

［1］刘 民.基于数据的生产过程调度方法研究综述［J］.自动化学报，2009（9）：785－806.

［2］黄云峰，车间调度和谐范式与多智能体系统情智集成的研究［D］.重庆：重庆大学，2010.

［3］黄云峰，徐俊刚，戴国忠，王宏安.生产调度理论和方法研究综述［J］.计算机研究与发展，2004（2）：257－267.

［4］黄云峰，郑 锋，孙树栋.混合型企业生产调度问题综述［J］.制造业自动化，2004（2）：1－4.

［5］黄云峰，胡庆夕，王 海，龙 飞.基于IDEFS的快速制造企业流程本体建模［J］.中国制造业信息化，2008（12）：6－11.

［6］黄云峰，周光辉，张国海，王 蕊，等.采用实时生产信息的单元制造任务动态调度方法［J］.西安交通大学学报，2009（11）：56－60.

［7］黄云峰，Allahverdi A，et al.A survey of scheduling problems with setup times or costs.European Journal of Operational Research［J］.2008（3）：985－1032.

［8］黄云峰，林春梅，何 跃，等.创建企业本体模型的研究［J］.计算机应用研究，2003（1）：57－60.