Purpose driven smart scheduling algorithm design based on DIKWP

• May 2021

• DOI: 

• 10.13140/RG.2.2.15579.85286

• Thesis for: Bachelor

• Advisor: Yucong Duan

• Project: 

• DIKWP: Semantic Computation-Existence Computation-Essence Computation-Cognitive Computation

海 南 大 学

毕 业 论 文（设计）

题    目：   价值驱动的智能调度算法设计 

(Purpose driven smart scheduling algorithm design based on DIKWP)                                       

学 号：   20171684310099                                                       

姓  名：   王兴斌 (Xingbin Wang)                                                      

年 级：   2017                                    

学    院：   计算机科学与技术学院           

系    别：   计算机科学与技术       

专    业：   计算机科学与技术           

指导教师：   段玉聪 (Yucong Duan)       

完成日期：  2021年5月26日 

摘要

基于语义理解、逻辑推理和以知识为中心的多模态数据，本文描述了一种价值驱动的调度算法。本文将常见数据分为数据、信息、知识和意图四种类型，以数据图谱、信息图谱、知识图谱和意图图谱的形式建模参与调度的调度实体和调度事务，并基于调度实体模型和调度事务模型使用DIKW运算输出调度方案。通过这种方法，调度算法可以将包括但不限于数字、文字、图片在内的数据转化为DIKW图谱形式的数据，再使用这些不完整、不正确、不明确的数据，实现不同场景、不同需求下的调度。在本文中，我将就DIKW图谱的构成、意图体系的构成和算法的实现展开讨论；下文的第二部分和第三部分，讨论了DIKW图谱和意图体系的构建，第四部分就基于DIKW图谱和意图体系的算法展开讨论，第五部分就电梯实例演示并分析了本算法的优缺点。

关键词：DIKW图谱；DIKW运算；调度算法；价值驱动；

Abstract

Based on semantic understanding, logical reasoning and knowledge-based multimodal data, this paper describes a value driven Scheduling Algorithm. In this paper, the common data is divided into four types: data, information, knowledge and purpose. The scheduling entities and scheduling transactions are modeled in the form of data graph, information graph, knowledge graph and purpose graph. Based on the scheduling entity model and scheduling transaction model, DIKW operation is used to output the scheduling scheme. Through this method, the Scheduling Algorithm can transform the data including but not limited to numbers, words and pictures into data in the form of DIKW atlas, and then use these incomplete, incorrect and ambiguous data to achieve scheduling in different scenarios and different needs. In this paper, we will discuss the constitution of DIKW Graph, the constitution of Purpose System and the realization of algorithm; In the second and third parts, the construction of DIKW Graph and Purpose System is discussed. In the fourth part, the algorithm based on DIKW Graph and Purpose System is discussed. In the fifth part, the advantages and disadvantages of this algorithm are demonstrated and analyzed by an elevator example.

Keywords: DIKW Graph; DIKW Calculation; Scheduling Algorithm; Value driven.

目录

1 综述

1.1 背景

1.2 背景分析

2 DIKW图谱与DIKW计算

2.1 基于类型化资源的DIKW图谱

2.2 DIKW计算

2.3 DIKW的动态平衡状态

3 意图模型与意图计算

3.1 意图模型定义

3.2 意图模型构建

3.3 意图模型伪代码

4 调度算法设计

4.1 算法基础模块划分

4.2 调度模型设计

4.3 总体流程设计

4.4 异常处理和反馈机制

4.4 基于Java的调度算法部分实现

5 电梯调度实例

5.1 基于电梯调度案例的拓展模块划分

5.2 基于电梯调度案例的拓展设计

5.3 基于电梯调度案例的调度算法设计

6 结论

致谢

参考文献

1 综述

1.1 背景

随着人们生活水平的提高，人们的日常需求已经从“有”进化到“精”，同时，信息化技术也逐渐替代人力成为提高效率的必要元素。面对越来越丰富的用户的多样化需求，我迫切需要一种具有可以快速适应多维度用户需求、可扩充的信息化调度方式来处理用户的个性化需求。为信息化调度问题，可以抽象调度问题为：调度主体利用调度资源在一定的调度事务逻辑下输出调度价值最大的计划。

如今，调度问题出现在包括且不限于电梯、网约车、以及各类需要“预约”的日常场景。在不同的场景下，有各个场景所特有的需求、逻辑和约束。例如，在电梯场景下，调度资源（电梯）为多个调度主体（电梯乘客）所公有，每一个调度主体的需求均会对调度计划产生显著影响；而在网约车场景下，调度主体（网约车乘客）独占调度资源（网约车）。

本调度方式可以适用于包括且不限于电梯、网约车、以及各类需要预约的日常场景，在保障效率的同时满足用户的个性化需求。

1.2 背景分析

在传统的调度算法中，我们使用预设的数据，以预设的逻辑完成在特定场景下的调度问题。这样的算法存在“不完整、不正确、不明确”的问题。程序只能对明确的，编写代码时确定的部分数据使用“预期的”逻辑做出解答。当有更多的数据或蕴含更多信息的模糊数据引入时，我们需要编写额外的代码逻辑和数据处理逻辑来暂时的解决“不完整、不正确、不明确”问题。而在本文的背景下，新算法需要解决的问题有：

（1）让计算机处理非“预期的”数据，执行非“预期的”的逻辑。

（2）综合“预期的”和非“预期的”数据和逻辑计算调度事务价值。

综合易知，实际我们需要解决的问题为“不完整、不正确、不明确”的问题。为解决这个问题，可得如下分析：

（1）现有许多的技术可以使得计算机接受未被预先定义的数据，并对相应的数据进行处理。在这里，我选用知识图谱来完成这一过程。知识图谱是一种对问题、实体内部隐藏的知识进行全方位建模的工具。与特定问题、实体相关的数据都可以轻松的加入到对应的知识图谱之中；

（2） 使用与特定调度主体和调度资源相关的知识组成的DIKW图谱代替调度主体和调度资源与系统进行交互，以适应非“预期”的数据和信息，解决“不完整、不正确、不明确”的问题。

由此，本文讨论的调度问题可以转化为以下三个子问题：

（1）基于DIKW图谱的调度事务建模和价值评估；

（2）基于意图计算的调度主体意图识别和价值评估；

（3）基于价值的调度方法；

2 DIKW图谱与DIKW计算

如图2.1，DIKW体系是关于数据、信息、知识和智慧的，类似于金字塔结构的体系。自顶向下，每一层都是在下一层的基础上被赋予了部分特质而构成的，数据层作为最底部的一层，是其他各层的来源和基础。如此，DIKW体系是一个让我们了解、分析事物的模型，其常被用于资讯科学和知识管理^[1]。

图2.1 DIKW体系结构图

罗素·艾可夫（Russell L. Ackoff）教授认为，人类思维内容可以分为5个层次^[2]：

（1）数据（Data）：任何形式存在的、未被赋予实际意义的符号；

（2）信息（Information）：经处理的，被赋予了实际意义的有用的数据；

（3）知识（Knowledge）：信息使用者出于某一意图而得到的信息的集合；

（4）理解（Understanding）：基于插值、概率的认知、分析过程；

（5）智慧（Wisdom）：经过一个推断性、非确定性、非概率的过程，得到曾经未理解的“理解”的过程。

融合DIKW体系和计算机技术，Gene Bellinger，Durval Castro和Anthony Mills提出了“理解”不作为一个单独层次的想法^[2]。他们如此理解罗素·艾可夫的理论：

（1）数据：类比计算机中以不同形式存储的数据，原始、且除其存在之外没有任何意义；

（2）信息：类比存储于关系型数据库中，以Key-Value形式通过关系链接而被赋予意义的数据；

（3）知识：类比编程、建模中出于某一意图而使用的部分信息，知识是被“意图”赋予了额外意义的信息的集合；

（4）理解：类比于人工智能，它们通过潜在的逻辑，从以前存储的信息和知识中合成符合某一意图的新知识。“理解”和“知识”区别在于“学习”和“记忆”的区别，有理解的个体可以从以前已知的“理解”中综合新“知识”，获取新“信息”，建立新“理解”。即理解可以建立在目前掌握的信息、知识和理解本身的之上。

（5）智慧：类比于人类编撰法律、道德规范的过程。它促使我们理解以前所没有理解的。与前四个层次不同，“智慧”提出的问题没有明确、正确的答案。或者说，追寻“智慧”的答案这一行为本身就是不智慧的。

如它们所叙述，理解作为一个过程，不应作为单独的层次出现在体系之中，而应该成为为数据、信息、知识、智慧之间每个阶段之间以“意图”为依据的过度，见图2.2。

图2.2 DIKUW图变体示意图

图2.3 意图驱动的DIKW图谱示意图

由上，我构建了如图2.3的意图驱动的DIKW图谱来解决上文提到的调度问题。

2.1 基于类型化资源的DIKW图谱

2.1.1 数据图谱（Data_DIK）

数据不具有任何实际意义，但数据有各种各样不同的表现、存储形式。^[3]为结合计算机科学的习惯，定义未数据模型化的数据为元数据（Meta Data），它可以是不同数据结构形式呈现的关系或非关系数据。元数据经过数据模型化（Materialize）后转化为以数据模型形式组织的数据模型的一部分，此时它被称为模型化数据（Modeled Data），再由模型化数据构成数据图谱。

数据图谱由模型化数据、关系（Relation）和实体（Entity）三种类型的元素组成。实体由模型化数据组成。每个实体包含若干模型化数据，且不存在没有归属的实体而游离存在于数据图谱的模型化数据。实体由元数据按来源划分得到。数据图谱中的关系表现形式为“own”，仅表示数据体系中的归属关系。假设有实体E₁包含模型化数据MD₁，关系记作如公式：

如图2.4，实体用户A、实体用户B和实体电梯C分别拥有来自于某数据来源（可以来自不同数据来源）的3条、2条和2条字符串数据。

图2.4 Data_DIK示意图

2.1.2 信息图谱（Information_DIK）

信息（Information）反映实体之间的关系，而关系都是建立在一定的意图之上的。信息是基于实体的某特定意图，记录、表达的实体之间的关系。这里的实体并不局限于表示一个人，还可以是一个事物。信息图谱是由系统动态生成的、基于系统内实体和意图生成的信息的集合。

信息图谱由实体、意图（Purpose）、信息和关系四种类型的元素组成。其中，关系“is”是一个三元运算符，由两实体和意图参与运算得到信息。假设有实体E₁在意图P₁下与实体E₂运算得到信息I₁，关系式记作如下式：

如图2.5，实体用户A与实体用户B因为拥有不同的Data_DIK，在相同的意图“使用电梯”下，得到了不同的信息。

图2.5 Information_DIK示意图

如上图的两条信息可以得到关系式如下式：

2.1.3 知识图谱（Knowledge_DIK）

Knowledge_DIK由Data_DIK和Informtion_DIK经过插值、推导演绎得到。Knowledge_DIK以类似对象-类模型的形式对Data_DIK和Information_DIK进行了进一步的完善。

知识图谱由对象（Object）、类（Class）和语义关系（Semantic Relations）组成。对象与Data_DIK和Information_DIK中的实体相对应。函数CreateInstance用于创建Class的对象，函数TypeOf用于获取对象所属的类，函数GetRelation用于获取对象与对象、对象与类、类与类之间的语义关系。如下式所示，对象O₁、O₂属于类Class₁，K₁、K₂、K3分别表示类Class₁与类Class₂、类Classs₁与对象O₁、对象O₁与对象O₂之间的语义关系SR₁、SR₂、SR₃。

上式可以得到如图2.6的Knowledge_DIK。

图2.6 Knowledge_DIK示意图

类似于对象-类模型，类的继承仍然存在与Knowledge_DIK中，此时对应的语义关系为继承（extends）或继承自（extend）。子类将继承其父类的全部属性和关系，且可以拥有其父类所不具有的独特的属性和关系。

2.2 DIKW计算

DIKW计算是发生在Data_DIK、Information_DIK、Knowledge_DIK和Purpose_DIK之间的运算，运算参与者可能包括Data、Information、Knowledge和Purpose中的若干部分，运算结果总是Data、Information和Knowledge中的一个。即在DIKW体系中，数据、信息和知识可以在意图的帮助下进行多种转换，生成新的数据、信息和知识。本文共描述了9种DIKW计算，以完成跨模态的数据处理与转换。

由于数据图谱，信息图谱，知识图谱之间转换方法繁多且高耦合度，故DIKW图谱中数据图谱、信息图谱、知识图谱三者并不是“完整的”图，但每一个转换的请求，都会有新的数据、信息或知识，使得DIKW图谱完整一分，为解决不完整、不明确问题提供了可能。DIKW图谱会在一次次跨模态转换请求下逐渐达到动态平衡状态。

2.2.1 Combine_DIK运算：Data_DIK计算得到Data_DIK

从Data_DIK转化为新的Data_DIK的运算没有很多的限制，故Combine_DIk可以发生在单个数据元素之上或多个数据元素之间，其亦可以发生在同一实体之内，或发生在不同实体之间。参与运算的Data_DIK亦可以为单个或多个。以上计算如下式所示：

如下式所示实例，从一个人的性染色体型可以得到这个人的性别，从一个人的出生年月和另一个人的出生年月可以推算得到他的年龄差，从每个港口的年吞吐量可以得到整个港口公司的年吞吐量。

2.2.2 Plus_DIK运算：Data_DIK计算得到Information_DIK

由Data_DIK计算得到Information_DIK需要同时借助Purpose_DIK的帮助。当要构建以某实体为中心的Information_DIK时，需要借助Purpose_DIK建立中心实体与其他Data_DIK中的实体之间的关系。在考量单个Information元素的生成时，可能需要同时引入一个或多个实体和一个或多个意图元素。由Data_DIK得到Information_DIK的表示如下式，其中PurposeGroup、EntityGroup是参与运算的参数，E_x是信息I₁所归属的实体。

例如，一名男子谈论时提到了单词“Bachelor”，若不清楚这名男子谈论的目的，则无法确定此男子当时语境下单词“Bachelor”的意义。如下式所示，若此男子当时谈论情感状况，则此时的“Bachelor”意为“单身汉”；若该男子谈论学位话题，则此时的“Bachelor”意为“学士学位”。

2.2.3 Count_DIK运算：Data_DIK计算得到Knowledge_DIK

当Data_DIK中的数据规模达到一定的程度时，使用统计学相关原理可以从Data_DIK中统计、推理生成Knowledge_DIK。以此法生成的Knowledge_DIK可以挖掘Data_DIK中的内在规律和总体发展、变化趋势，以概率、知识规则的形式预测实体可能的行为和意图。例如，根据往年的销售额能够预测出今年的销售额变化趋势，如下式所示。

2.2.4 Append_DIK运算：Information_DIK计算得到Information_DIK

信息元素可以和若干个信息元素和数据元素结合得到新的信息元素，如下式：

2.2.5 Decompose_DIK运算：Information_DIK计算得到Data_DIK

Data_DIK与Purpose_DIK结合，可以得到Information_DIK。同样的，从Information_DIK中剥离意图，即可以把Information_DIK恢复为Data_DIK这样的实体-数据的形式。如下式所示：

2.2.6 Abstract_DIK运算：Information_DIK计算得到Knowledge_DIK

Information_DIK可以通过抽象，聚类的形式进行归纳分析，得到Knowledge_DIK。如下式所示，通过Abstract_DIK，从Data_DIK中提取出了包含三个对象与一个类的Knowledge_DIK,并从三个实体的共有特征提取了Class_Fruit的数据域“Color”。

2.2.7 Supplement_DIK运算：Knowledge_DIK计算得到Knowledge_DIK

当Knowledge_DIK有足够多的数据后，知识元素可以与数据元素、信息元素、其他知识元素之间结合，形成新的知识元素。如下式所示。

例如下式所示，已知有K₁：生物种群在物质趋于饱和情况下会出现自我毁灭倾向，K₂：国家可以看作人类生物种群。

2.2.8 Predict_DIK运算与Backstepping_DIK运算：Knowledge_DIK计算得到Data_DIK

要由Knowledge_DIK计算得到Data_DIK可以有如下式的预测法（Predict_DIK）和Count_DIK的反过程反推法（Backstepping_DIK）。

2.2.9 Forecast_DIK运算：Knowledge_DIK计算得到Information_DIK

根据现存的Knowledge_DIK可以推测实体之间的关系，这一如下式所示过程称为Forecast_DIK。

2.3 DIKW的动态平衡状态

DIKW的动态平衡状态指在没有外部输入的情况下，DIKW体系内部在经过一段时间的DIKW运算后，数据图谱、信息图谱和知识图谱达到的平衡状态。此时即使发生DIKW运算，数据图谱、信息图谱和知识图谱也不会出现进一步扩充和改变。

在DIKW图谱通过如图2.7的DIKW计算而逐渐达到动态平衡后，Data_DIK ，Information_DIK，Knowledge_DIK共同构成了如下式的以某一实体为核心的DIKW图谱。

图2.7 DIKW运算示意图

此时可以通过遍历DIKW图谱中的元素，得到与此实体相关的数据、信息和知识。

3 意图模型与意图计算

意图是所有行动的驱动力^[3]，亦是DIKW体系中必要的一环^[2]，如何将意图引入信息资源的处理过程成为了我关注的下一个问题。要将意图引入信息资源处理过程，首先需要解决意图的形式化表示问题^[4]。当前已有的研究中，有两种方式可以在一定程度上形式化表示用户意图需求：一种是用例模型^[5], 另一种是在KAOS 方法^[6]中用到的多范式语言^[7]。它们虽然均可以用于建模用户意图需求，但抽象程度较低^[8]。这两种方法均为软件需求建模中评估用户意图的方法，其局限性使其并不适用于软件需求建模以外的场景。图也是常用于意图建模的工具，但单张图所承载的信息往往不足以准确描述用户意图^[9]，目前的形式化方法尚不具备对复杂实体建模的能力^[10]。

为了计算机能够更快捷、精确地理解用户的目的，我构建了意图模型来评估主体的目的，即意图计算。在这里，定义二元计算符～完成意图计算：主体画像 ~ 主体的意图示=用户意图。由此，意图计算问题可以分为以下两个子问题：

​ （1）具有可计算性的意图形式化表示；

​ （2）基于意图形式化表示的计算方法；

​ 意图计算的意义在于结合多方位的数据估计主体的真实意图。由于拥有相同意图的不同用户可能拥有不同的行为（即输入），不同用户的相同的行为（输入）也可能对应该用户不同的意图。故意图计算的难点在于：

​ （1）用户行为的输入可能是多样且可扩展的，而计算机可以存储的信息的形式是有限的，故需要一个可扩展、有效且高效的模型来适应可能输入的多维度的数据；

​ （2）因为针对相同输入，随着使用系统的主体的变化，系统可能存在不同的输出，故需要对使用系统的主体建模；

在本文中，我仅对意图模型做必要的描述。

3.1 意图模型定义

我们使用基于意图合成的意图图谱和意图主体画像来进行意图的形式化表达。意图图谱和意图主体画像分别对应意图本身和拥有意图的用户。意图主体画像是以需要被评估意图的用户为核心的Knowledge_DIK，意图图谱是依据意图主体画像，以层次结构组织的用户意图的图形化表达。

图3.1 Purpose Graph示意图

​ 意图图示是一个如图3.1的无向有权图，意图图示中的点由意图主体画像直接得出或由意图分解得到，意图图示不同节点之间的关系有两种类型：

（1）由分解产生的概率分布关系，每一个分支上的概率均在区间（0~1）之间；

（2）由意图主体画像直接得到的关系有AND、OR和EQUAL，用于描述意图树中意图节点间的实际关系。在忽略不是由意图分解而产生的意图间的关系时，此图会退化为数个意图树组成的森林。其中，每棵树的根节点为主体的实际意图（Actual Purpose, AP），叶子节点为元意图（Meta Purpose, MP）。元意图(MP)指在当前所有知识下，分解到极限的最小意图（例如在如图3.1电梯实例中，元意图的最终形态应为系统的最小操作），同时也是意图计算中的基本元素。

3.2 意图模型构建

意图模型的构建需要经过以下三个步骤：

​ ​（1）提取（Extract）：即从外部输入的知识中抽取与意图相关的知识的过程。提取过程需要遍历所有知识，并将意图相关知识加入意图主体画像（在大多数场景下，由Data_DIK和Information_DIK经过Count_DIK和Abstract_DIK产生的Knowledge_DIK的元素最有可能与意图相关）。

​ ​（2）分析（Analyze）：分解操作是分析过程的主要操作。在分析过程中，意图将被逐层分解为不同的子意图并构成意图树。

​ ​（3）组合（Integrate）：组合是意图体系构建的最后一步。组合操作将依据意图主体画像，补全意图图示的意图分解概率分布和意图间的其他关系。

​ 经过第一次构建后的，可以通过输入额外的知识并重复执行步骤（1）~（3）对意图体系进行补充和修改。

3.3 意图模型伪代码

意图体系拥有以下接口：

（1）构造器接口：伪代码（一）使用KnowledgeGraph K作为参数，依次调用方法PurposeGraph和SubjectProfile（PurposeGraph和SubjectProfile的构造方法），构造意图体系。其中PG、SP、RT分别为构造方法执行后构建的PurposeGraph、SubjectProfile和RelationshipTable。

伪代码1 Purpose_DIK构造器伪代码

①伪代码（二）使用Knowledge Graph K作为参数，完成了SubjectProfile的构建。方法Extract是复杂的方法，未以伪代码的形式给出，详见文档定义。

伪代码2 Subject Profile构造函数伪代码

②伪代码（三）使用SubjectProfile SP和RelationshipTable RT作为参数，完成了PurposeGraph的构建并补充了RelationshipTable。方法Analyze和Integrate是复杂的方法，未以伪代码的形式给出，详见文档定义。

伪代码3 Purpose Graph构造函数伪代码

（2）意图评估（Purpose Assess）接口：伪代码（四）使用PurposeSystem P和ActualPurpose AP为参数，输出意图主体实际意图对应的全部元意图。

伪代码4 Purpose Assess函数伪代码

（3）意图预测（Purpose Forecast）接口：伪代码（五）使用Purpose System P和Data[] D为参数，输出意图主体的实际意图。

伪代码5 Purpose Forecast函数伪代码

4 调度算法设计

本部分描述一种基于意图驱动的知识图谱的调度方式，其包括一个针对调度主体建立的模型（调度主体画像），一个用于调度的调度事务建模。系统总体应包括以下两类功能：

（1）功能性需求：输入调度主体相关的多维度数据，输出实际调度计划；

（2）附加需求：

①易于扩充的调度主体的多维度数据：系统输入的数据除预设的时间、空间等，需要可以便捷的添加多维度数据到系统之用，用于系统的用户画像和调度决策过程；

②基于等待时间的最大用户等待时间保障：系统应保障用户最大等待时间，防止用户在调度过程中长时间处于低优先级状态，等待过长的时间；

4.1 算法基础模块划分

如图4.1，算法包含调度主体模型、调度事务模型和基于调度事务模型、调度主体模型的调度算法三部分。

图4.1 调度算法模块划分

算法将为所有参与调度的调度主体建立独立的调度主体模型，并结合调度事务模型，输出调度事务约束条件，并依据调度事务约束条件做出调度决策。

4.2 调度模型设计

4.2.1 调度主体模型设计细节

（1）模块主要功能：根据输入的多维度数据产生调度主体的模型（调度主体画像）；

（2）使用的技术：意图驱动的DIKW图谱；

（3）用途：调度主体模型通过对多维度调度主体数据进行预处理，产生调度主体画像。调度主体画像可以很好的反应调度主体的特点，以供调度事务模型使用。

（4）构建方式：系统基于输入的批量的调度主体数据动态生成，并根据后续使用过程中加入的额外数据更新、调整。

4.2.2 调度事务模型设计细节

（1）模块目的：根据调度事务的实际细节产生调度事务的模型

（2）考虑使用的技术：知识图谱

（3）用途：调度事务模型是对一次调度的完整建模，系统结合调度事务模型和调度主体，综合评估一次调度事务的价值，

（4）组成：调度事务模型由一系列调度过程中的限制、价值评估维度组成，其包括且不限于：空间需求（限制），时间需求（限制），基于事件的价值评估等；

4.3 总体流程设计

4.3.1 初次使用流程设计

如图4.2所示，在DIKW构建过程中，算法将以DIKW是否已经达到动态平衡状态为依据，重复从不同数据来源中构建DIKW，并尝试使用DIKW运算使得DIKW达到动态平衡。 

图4.2 DIKW构成流程图

如图4.3，用户第一次参与调度时，算法将分别构成调度主体模型和调度事务模型的DIKW体系。

图4.3 初次使用流程图

4.3.2 后续使用流程设计

图4.4 后续使用流程图

如图4.4，有下文的正常使用流程：

Step 1 输入调度主体信息，查询调度主体是否已经有构成过调度主体模型；

Step 1 – 1调度主体已经存在模型，调用已经产生的主体模型；

Step 1 – 2 调度主体未生成模型，使用调度主体信息生成调度主体模型；

Step 2 输入本次调度相关需求信息，主体模型计算用户意图并评估用户价值、意图价值

Step 3 输入本次调度事务的基础信息，事务模型结合调度主体模型、调度事务的基础信息、当前系统运行情况综合评估用户价值； 

Step 4 调度系统按照用户价值、用户需求和调度规则产出调度计划；

4.4 异常处理和反馈机制

在调度过程中的异常可以分为以下两类：

（1）主体性异常：由调度主体产生的异常。对主体性异常的反馈只会作用在调度主体模型上，并影响本调度主体所参与的所有调度；

（2）事务性异常：事务性异常仅对一次事务产生影响，其具有强时效性。事务性异常仅会作用在事务模型上。

在处理这两类不同的调度异常时，需要采用不同的策略。

4.4 基于Java的调度算法部分实现

本部分利用Java实现了预留DIKW接口的调度算法。可以通过创建未预先定义的调度主体需求类、调度事务约束类和相配套的价值评价方法的形式，实现使用蛮力法计算调度方案。

4.4.1 算法实现分析

由于本算法使用的调度主体模型和调度事务模型没有完成开发，在这里通过Mock模拟调度主体模型和调度事务模型模型的输出代替实际的调度主体模型和调度事物模型。

由于需要简易的适配同种多样的调度需求、调度事务约束和价值评估方法，而需求、约束和价值评估方法往往是有联系的，故需要建立公有的Needs、Limit和Controller类，通过继承的方式实现具体的Need、Limit和Controller子类。

4.4.2 算法运行环境

表4.1 运行环境表

算法运行环境如上表4.1所示。

4.4.3 算法实现设计

本调度算法通过如图4.4、4.5、4.6、4.7的主程序包类图、Dispatcher类图、Mock类图和Dispatch类图和未绘制成图的Limit、Needs、Controller等类构成。

图4.4 主程序类图

图4.5 Dispatcher包类图

图4.6 Mock包类图

图4.7 Dispatch包类图

除上图外，如图4.8的Dispatcher类是程序的核心方法。程序的调度逻辑亦在本部分实现。

图4.8 Dispatcher类图

4.4.4 算法示例

本算法的实现使用调度事务中较为常见的时间、空间需求和约束作为示例条件。程序中使用的数据集如下调度主体表4.2和调度资源表4.3所示。

表4.2 调度主体表

表4.3 调度资源表

经过算法运行可得运行结果如图4.9。

图4.9 程序运行结果图

5 电梯调度实例

5.1 基于电梯调度案例的拓展模块划分

针对电梯调度案例中的部分特质，在公有的调度算法基础上明确并拓展了各个模块。如图5.1。

图5.1 电梯实例模块划分

5.2 基于电梯调度案例的拓展设计

（1）在电梯调度场景中，调度主体即乘梯用户。在此场景下，调度主体模型主要关注用户信用情况、乘梯习惯评价的参数。

（2）在电梯调度场景中，用户一次乘梯的过程即一次调度事务。

（3）在电梯调度场景中，异常情况处理和反馈机制主要体现在以下两方面：

①主体性异常：用户未按规划乘梯、用户不良乘梯习惯、用户利用电梯紧急情况处理机制获取优先级别等；

②事务性异常：有用户出发紧急情况时电梯进行紧急调度等；

（4）系统稳定性保障：

①基于行为库的用户信用分系统可以在一定程度上阻止用户的不当行为（行为识别）；

②一定时期内多次出发恶意行为或信用分低至一定阈值的用户封停策略可以阻止可能存在的恶意攻击（风险控制）；

③价值的引入有效提高了恶意用户的攻击成本；

（5）智能代理：智能代理可以用于减少用户自主决策花费的时间和精力。用户通过委托自己的需求给智能代理，由智能代理代替用户进行竞价流程，并在预期代价超出用户设置基线代价时询问用户需求。智能代理输入用户需求和系统反馈，代替用户做出决策^[14]。

①实现方式：智能代理通过调度系统接口获取调度信息，结合用户需求和用户设置的基线价值，模拟用户的竞价决策过程；

②流程：

Step 1 用户提交基线价值和用户需求给智能代理；

Step 2 智能代理向调度系统发送数据并请求初次价值评估；

Step 3 智能代理结合用户需求和系统返回，判断价值是否达到基线：

Step 3–1 需求价值超过基线价值，代理提示用户，由用户选择提高基线或降低需求；

Step 3–2 需求价值低于基线价值，代理代替用户竞价并循环执行3，直到超出基线价值或用户顺利进入调度用户名单；

Step 4 代理处理用户需求成功或退出代理；

上文智能代理的流程可以用流程图5.2所示。智能代理基于调度主体愿意付出的基线价值和用户的需求，与参与调度的其他调度主体循环竞价，直到调度主体决定放弃本次调度或调度主体进入调度名单。

图5.2 智能助理流程图

（6）多梯协作

①多梯协作需要解决的问题

a.多部电梯情况下，不是每一部电梯都前往所有的楼层；

b.多部电梯协作完成全体用户运输过程；

c.用户的空间需求由更多的实现可能；

②解决方案：

a. 每一部电梯维护其自己的可达楼层序列，在调度时参考电梯可达楼层产出调度方案。

b. 一次调度所有电梯，在所有电梯停止运行后再开始下一次运行。同时使用负载均衡的算法保证所有电梯单次运行时间接近

（7）投票权转让

①一般情况：用户从众（转让投票权给系统），用户不为自己附加价值，系统保证用的最大等待时间；

②特殊情况：用户之间的绑定关系（转让投票权给其他用户），被绑定的用户需要付出不确定且不相等的价值，来保证被绑定的用户在同一次调度中（被绑定需要的总价值相同，但由于基础价值可能不尽相同，则需要付出不等量的额外价值）；

5.3 基于电梯调度案例的调度算法设计

（1）主体思想：由于在价值驱动调度中，调度的解空间有效减少、用户需求相较于传统调度显著丰富，使用蛮力法处理会是一个较好的调度方式。调度系统输入系统中被选中的高价值用户的需求，在满足所有需求的基础上，蛮力遍历所有的可能情况并找出最大价值的调度计划作为电梯调度计划^[13]；

（2）用户需求维度：由于蛮力法的完备性，要将不同的需求加入到调度之中，只需要完成不同用户需求的价值评估模型，将其加入到可扩充的价值模型中，并将相应的需求加入到调度算法中。这里的需求包括且不限于^[13]：

①空间需求；

②时间需求；

③人数要求；

（3）调度算法基础要求：

①调度以整个系统作为单位，一次调度可能包含所有电梯的多次运行（总体是从计划的起点到终点），当所有电梯完成从计划起点到终点的运行目标时，视为一次调度结束。

②等待多部电梯同步的时间即是用户竞价时间。

（4） 蛮力法遍历基础解空间的原子操作划分：

①用户角度：在楼层X上电梯，在楼层X下电梯

②电梯角度：电梯上行至X层，电梯下行到Y层

（5）调度算法流程

Step 1 根据电梯可达楼层，规划的用户起终点，遍历电梯所有的可能调度；

Step 1 - 1 动态加入用户需求到调度系统，遍历所有可能的用户乘梯计划；

Step 1 - 2 输出当前电梯调度下价值最大化的用户乘梯计划；

Step 2 输出最优调度计划下的最优用户乘梯计划；

Step 3 随着用户竞价，重复执行Step 1 – Step 2，直到竞价结束，输出最终调度计划；

6 结论

由于技术水平所限，未能对设计的算法进行详细的实现和分析，仅仅根据大致的思想实现了简单的调度算法示例程序。在详细了解和学习常见的（多路电梯）调度算法（LOOK算法、FCFS算法、FD-SCAN算法、基于专家系统的电梯群控方法、基于模糊神经网络的电梯群控方法）^[14]后，我认为本文描述的算法优点在于可以快速、轻松的适应多样化的调度场景和调度需求，但在时间、空间复杂度上比不上于传统的电梯调度算法。

致谢

转眼四年的大学本科生活即将画上句号，回首这四年充实而又不乏遗憾的大学生活，我心怀感激与不舍。

于此，我想对学校、学院、老师、家人、同学们表达我真诚的谢意。

感谢海南大学，海大“海纳百川，大道致远”的校训在我人生最桀骜不驯的阶段告诉我了我什么是“包容”，什么是“宽以待人，克己慎独”。

感谢计算机与网络空间安全学院，为我提供丰富的教学资源与竞赛机会，让我的知识不止于书本。

感谢每一位家人对我无微不至的关心和全力支持，在每一次低潮时做接纳我这艘小船的港湾，不怨当我情绪的垃圾桶；

感谢老师的孜孜教诲；感谢四年中来自同学、朋友的帮助和鼓励。

我尤其感谢段玉聪教授，加入段老师的课题组带给我的不止是知识，更有积极向上的精神、更开阔的眼界。在这近一年的相处中，段老师的每一次教诲和鼓励我都铭记在心。很遗憾辜负了段老师的厚望，没有做出太大的成果，但我将带着段老师赋予我的，走完接下来的路。

于此毕业之际，我向四年来陪伴过我、帮助过我、教导过我的师长、父母、同学朋友致以最诚挚的感谢和祝福。即将画上的本科生活的句号，不过是我人生中的一个逗号，这篇粗浅的论文不会是我学术思考的重点。人生路漫漫，我将带着你们对我的期望与鼓励，大踏步的走向人生的下一个阶段。

References:

[1] 未知. DIKW体系 -维基百科. https://zh.wikipedia.org/wiki/DIKW/, 2020.

[2] Gene Bellinger, Durval Castro, Anthony Mills. Data, Information, Knowledge, & Wisdom. www.systems-thinking.org/dikw/dikw.htm, 2004

[3] Duan, Yucong et al. “Specifying architecture of knowledge graph with data graph, information graph, knowledge graph and wisdom graph.” 2017 IEEE 15th International Conference on Software Engineering Research, Management and Applications (SERA) (2017): 327-332.

[4] Kruglanski, Arie W., and Ewa Szumowska. “Habitual behavior is goal-driven.” Perspectives on Psychological Science 15.5 (2020): 1256-1271.

[5] DeLoach, Scott A., and Matthew Miller. “A goal model for adaptive complex systems.” Journal of Advance Computational Research 2.2 (2017).

[6] Lee, Jonathan, and Nien-Lin Xue. “Analyzing user requirements by use cases: A goal-driven approach.” IEEE software 16.4 (1999): 92-101.

[7] Darimont, Robert, et al. “GRAIL/KAOS: an environment for goal-driven requirements engineering.” Proceedings of the 19th international conference on Software engineering. 1997.

[8] Darimont, Robert, and Axel Van Lamsweerde. “Formal refinement patterns for goal-driven requirements elaboration.” ACM SIGSOFT Software Engineering Notes 21.6 (1996): 179-190.

[9] Zickert, Frank, and Roman Beck. “Evaluation of the Goal-Oriented Requirements Engineering Method KAOS.” AMCIS. 2010.

[10] [Feblowitz, Mark D., et al. “Method for declarative semantic expression of user intent to enable goal-driven stream processing.” U.S. Patent No.7,899,861. 1 Mar. 2011]

[11] Gu, Haiqian, et al. “Modeling of user portrait through social media.” 2018 IEEE International Conference on Multimedia and Expo (ICME). IEEE, 2018.

[12] Hey, Jonathan. “The data, information, knowledge, wisdom chain: the metaphorical link.” Intergovernmental Oceanographic Commission 26 (2004): 1-18.

[13] 段玉聪,王兴斌,方照霖. 面向数据与信息权益交换的智能共享装置调度方法[P]. 海南省：CN112559144A,2021-03-26.

[14] 段玉聪,王兴斌,方照霖. 面向数据、信息权利可价值交换的智能运载装置调度方法[P]. 海南省：CN112456257A,2021-03-09.

[15] 王萍. 网络环境下的领域知识挖掘[D].华东师范大学,2010.