下载文档原格式
内部控制常见问题及应对策略企瑞管理2023-05-1811:30发表于江苏企瑞管理K-RUIMANAGEMENT企瑞管理，企业一站式智慧服务中心！为您推送精品阅读问题一：不相容岗位未分离；例如：出纳和会计岗位未分离（这是最典型的一种不相容岗位未分离的情况），除此之外，企业当中的很多业务部门也存在这种问题，比如，企业如果把在销售过程中的职能设置，”销售价格、客户的赊销额度、坏账的注销“都放在一个人身上，那么就存在着不相容岗位未分离的情况；应对策略：在企业的交易中，有发起、批准、进行、记录等各个环节，要把各个环节的人员分开，才能更好的进行内控。
问题二：工作交接出现问题；职员在离职或者职员岗位轮换之后，企业找不到合适的人顶替这个岗位；这种情况下，会影响公司正常开展业务；交接期内，工作效率低下；因组织变换，人为商定的措施未贯彻。
应对策略：制定AB角制度，明确规定一旦岗位人员发生变动，该岗位的顶替人选。
问题三：岗位轮换的不及时一些岗位的员工，在该岗位担任工作的时间较长，或者一个人在一些岗位上，从未离开。
针对这个事项，可能引起的问题有，虽然在该岗位上的员工经验越来越丰富，但很难改善其工作方法。
而且该员工如果出现工作失误时，很难被人发现。
应对策略：强制轮换；强制带薪年假制度；避免过多的连续加班。
问题四：企业资源个人化常见的情况，比如企业的采购人员，以采购数量为筹码与供应商谈判，间接的收取采购提成等。
应对策略：将个人经验、技能、知识转化为企业书面信息和制度流程；或者对业务进行适当的分离；与员工签订相关协议，并健全激励约束机制。
问题五：控制全靠一支笔（个人决策）如果决策人对事项缺乏全局性的了解，不能很好的做经营决策；这种情况还可能导致企业高度集权化，缺乏制约和监督，可能导致腐败；授权无法分级，无法分散精力，过于繁忙。
应对策略：授权审批—分清主次，按金额大小、程度不同集中或分散；建立决策制约制度—前期有论证、过程有监控、后期有跟踪。
系统架构设计师案例分析真题解析2022年11月系统构设计师下午题试题一(共 25 分) ：阅读以下关于软件架构设计与评估的叙述，在答题纸上回答问题 1 和问题 2。
【说明】某电子商务公司拟升级其会员与促销管理系统，向用户提供个性化服务，提高用户的粘性。
在项目立项之初，公司领导层一致认为本次升级的主要目标是提升会员管理方式的灵活性，由于当前用户规模不大，业务也相对简单，系统性能方面不做过多考虑，新系统除了保持现有的四级固定会员制度外，还需要根据用户的消费金额、偏好、重复性等相关特征动态调整商品的折扣力度，并支持在特定的活动周期内主动筛选与活动主题高度相关的用户集合，提供个性化的打折促销活动。
在需求分析与架构设计阶段，公司提出的需求和质量属性描述如下：(a)管理员能够在页面上灵活设置折扣力度规则和促销活动逻辑，设置后即可生效；(b)系统应该具备完整的安全防护措施，支持对恶意攻击行为进行检测与报警；(c)在正常负载情况下，系统应在 0.3 秒内对用户的界面操作请求进行响应；(d)用户名是系统唯一标识，要求以字母开头，由数字和字母组合而成，长度不少于 6 个字符。
(e)在正常负载情况下，用户支付商品费用后在 3 秒内确认订单支付信息；(f)系统主站点电力中断后，应在 5 秒内将请求重定向到备用站点；(g)系统支持横向存储扩展，要求在 2 人天内完成所有的扩展与测试工作；(h)系统宕机后，需要在 10 秒内感知错误，并自动启动热备份系统；(i)系统需要内置接口函数，支持开发团队进行功能调试与系统诊断；(j)系统需要为所有的用户操作行为进行详细记录，便于后期查阅与审计；(k)支持对系统的外观进行调整和配置，调整工作需要在 4 人天内完成。
在对系统需求、质量属性描述和架构特性进行分析的基础上，系统架构师给出了两种候选的架构设计方案，公司目前正在组织相关专家对系统架构进行评估。
【问题 1】(12 分)在架构评估过程中，质量属性效用树 (utility tree)是对系统质量属性进行识别和优先级排序的重要工具。
解决方案K简介本文档将介绍解决方案K，它是一个用于解决特定问题的方案。
我们将详细讨论方案的设计和实施，以及优点和适用场景。
背景在当今信息技术发展迅速的时代，各种复杂的问题不断涌现。
解决这些问题需要一种高效、可靠的解决方案。
解决方案K旨在提供一种创新的解决方案，以应对特定的问题。
设计解决方案K基于最新的技术和方法，经过精心设计。
它采用模块化的架构，使得方案具有高度的灵活性和可扩展性。
下面是解决方案K的主要设计特点：1.模块化结构：解决方案K将功能划分为多个模块，每个模块负责特定的任务。
这种模块化结构使得方案易于维护和扩展。
2.高性能：解决方案K采用一系列优化策略，以提高性能。
它利用并行计算和缓存技术，使得处理速度更快，响应更及时。
3.安全性：解决方案K注重数据和系统的安全性。
它提供多层次的安全措施，包括身份验证、数据加密和访问控制等。
4.易用性：解决方案K以用户为中心，致力于提供友好的用户界面和简单的操作。
它提供了详细的文档和指导，帮助用户快速上手和使用。
实施实施解决方案K需要一系列步骤和资源。
以下是一般的实施过程：1.需求分析：首先，需要明确问题的具体需求和目标。
这将有助于确定解决方案的功能和特性。
2.系统设计：通过系统设计，确定具体的模块和技术。
这包括选择合适的硬件和软件平台，以及制定详细的实施计划。
3.系统开发：根据系统设计，进行系统开发和编码。
这需要一定的开发资源和工具支持。
4.系统测试：经过系统开发，需要进行全面的系统测试。
这可以确保系统的稳定性、可靠性和功能的正确性。
5.系统部署：在经过测试和调试后，将系统部署到目标环境中。
这可能涉及到硬件的安装和软件的配置。
优点和适用场景解决方案K具有以下优点：•高效性：解决方案K能够快速处理大量数据，并提供快速的响应速度，提高工作效率。
•灵活性：解决方案K的模块化结构使得方案易于定制和扩展，以满足特定的需求。
•安全性：解决方案K提供多层次的安全措施，保护数据和系统的安全。
kthread_run函数-回复kthread_run函数是Linux内核中的一个重要函数，用于创建并执行一个内核线程。
内核线程与用户空间线程不同，它们在内核空间中运行，并且不受用户空间线程管理机制的约束。
在本文中，我们将详细介绍kthread_run函数的作用、参数和实现细节，并解释如何使用它创建和管理内核线程。
首先，让我们来了解kthread_run函数的作用。
kthread_run函数用于创建一个内核线程，并将其添加到内核的调度队列中运行。
这使得内核可以在后台执行一些任务，而不影响用户空间线程的执行。
内核线程的创建和管理是Linux内核中一个重要的功能，它允许内核执行一些需要长时间运行或在后台运行的任务，如设备驱动程序的处理、定期任务的执行、内存管理等。
接下来，我们将详细介绍kthread_run函数的参数和用法。
kthread_run函数的原型定义如下：struct task_struct *kthread_run(int (*thread_fn)(void *data), void *data, const char *namefmt, ...)其中，thread_fn是一个函数指针，指向一个内核线程的入口函数。
该函数会在内核线程启动后被调用。
data是一个可选参数，可以是任意类型的指针，用于传递给thread_fn函数。
namefmt是一个格式化字符串，用于指定内核线程的名称。
要使用kthread_run函数创建内核线程，我们首先需要定义一个内核线程的入口函数。
该函数通常会循环执行某个任务，直到任务完成或被取消。
在入口函数中，我们可以使用一些内核函数来完成任务的具体实现，例如访问设备、读写文件等。
下面是一个简单的示例，演示了如何使用kthread_run函数创建一个内核线程并执行一个简单的任务：include <linux/kthread.h>int my_task(void *data){这里是任务的具体实现...return 0;}在某处的函数中调用kthread_run函数struct task_struct *task;task = kthread_run(my_task, NULL, "my_thread");在上面的示例中，我们定义了一个名为my_task的函数作为内核线程的入口函数。
2024年公司优秀员工个人工作计划模版作为刚刚加入公司的新员工，我对新环境感到兴奋和好奇。
我期待与同事们建立稳定的友谊，营造一个和谐的人际环境，并希望能够在这里找到志同道合的伙伴，共同在职业道路上前进。
带着对未来工作的憧憬，我为自己制定了一个短期的发展计划：一、深入了解并尽力履行我的本职工作。
我的职责包括：1. 负责网站内容的日常更新，确保每天更新一定数量的文章，并尽可能地包含相关关键词；2. 策划、制作和维护网站的相关专题；3. 策划和推广网站相关活动，并保证每月撰写一定数量的原创文章；4. 策划新频道或栏目，并完善内容；5. 根据网站发展方向，策划并建设负责的栏目；6. 每月制定发展计划，并进行总结。
我将运用以往的工作经验，同时积极学习新技能，如策划和创作，以提高网站管理能力。
二、建立良好的人际关系结识新朋友，不忘老朋友。
在人生的旅途中，广泛的社交有助于事业的发展。
我将保持开朗、开放和乐观的态度，积极与人交往，建立和谐的人际关系，这对我的工作将大有裨益。
在此基础上，我将促进同事间的相互关心和了解，通过多方面的交流，增进友谊，形成紧密的工作团队。
三、实现个人职业愿景工作的目的不仅是维持生计，更是精神追求的体现。
工作不仅能提供经济支持，还是实现个人价值和职业发展的重要途径。
我希望成为一名经验丰富的职业编辑，掌握网络编辑的全套工作流程，同时深入了解网站发展方向。
我将积累更多经验，不断提升自我，追求专业成长，向责任编辑、主编职位迈进。
四、合理规划业余时间业余时间对于工作效率至关重要。
适当的休息和娱乐可以有效放松身心，缓解压力，提高生活质量。
我将合理安排业余时间，确保工作与生活平衡，通过全面投入和专注于正在进行的事情，实现工作与娱乐的和谐结合。
总之，本月的计划是为了试用期内的工作安排，我期待能够在转正后，规划出更具体的工作计划和发展方向。
请您见证，这也是我为自己加油和争取的表现！公司优秀员工年度工作计划俗话讲：“笨鸟先飞”，为了在新的一年里顺利开展工作，我将提前制定年度工作计划。
[标题]：深入解析kthread_run函数的使用方法【摘要】：本文将介绍kthread_run函数的概念、使用方法和实际应用场景，帮助读者深入理解Linux内核中的线程调度机制。
1. 什么是kthread_run函数？在Linux内核中，kthread_run函数是用于创建和管理内核线程的函数之一。
内核线程是在内核态运行的轻量级进程，它们通常被用于执行一些后台任务或者处理一些不需要用户交互的工作。
kthread_run 函数是基于内核中的kthread API实现的，它允许开发人员在内核空间创建和管理线程，从而可以在内核态执行一些需要长时间运行的任务，而不会占用过多的系统资源。
2. kthread_run函数的使用方法使用kthread_run函数很简单，只需要传入一个指向线程函数的指针和一个指向传递给线程函数的参数的指针即可。
线程函数是一个普通的C函数，用于执行线程的具体逻辑，参数则可以用于传递需要的数据给线程函数。
开发人员还可以通过设置不同的线程属性来指定线程的优先级、调度策略以及绑定CPU等。
```c// 使用kthread_run函数创建内核线程struct task_struct *kthread_run(int (*threadfn)(void *data), void*data, const char *namefmt, ...);```3. kthread_run函数的实际应用场景kthread_run函数广泛应用于Linux内核中的各种模块和子系统中，例如网络子系统、文件系统和驱动程序等。
在网络子系统中，可以使用kthread_run函数创建专门用于数据包处理的线程，以避免阻塞网络服务进程。
在文件系统中，可以使用kthread_run函数创建用于数据同步和清理的线程，以提高文件系统的性能和稳定性。
在驱动程序中，可以使用kthread_run函数创建用于设备管理和状态监测的线程，以提供更完善的设备控制功能。
kthread_run函数解析-回复首先，我们要了解什么是kthread_run函数。
在Linux内核中，kthread_run函数是用于创建内核线程的函数。
内核线程是在内核空间中运行的轻量级进程，与用户空间的进程有所不同。
内核线程不依赖于任何用户进程，而是在内核中执行任务。
kthread_run函数为我们提供了一种方便的方法来创建和管理内核线程。
下面我们来逐步分析kthread_run函数的实现和使用方法。
1. 首先，我们需要了解kthread_run函数的函数原型和参数列表。
根据内核文档，kthread_run的函数原型如下：cstruct task_struct *kthread_run(int (*threadfn)(void *data), void *data, const char *namefmt, ...)- threadfn是一个函数指针，指向我们要在内核线程中执行的函数。
- data是一个指针，传递给threadfn的参数。
- namefmt是一个格式化字符串，用于指定创建的内核线程的名称。
2. 然后，我们需要明确kthread_run函数的返回值。
kthread_run函数返回一个task_struct结构体指针，表示创建的内核线程的任务描述符。
task_struct结构体是内核中用于表示进程和线程的数据结构。
3. 接下来，我们来看一下kthread_run函数的实现原理。
kthread_run 函数的实现主要分为两步：- Step 1: 创建内核线程在kthread_run函数中，首先使用kthread_create函数创建一个新的内核线程。
kthread_create的函数原型如下：cstruct task_struct *kthread_create(int (*threadfn)(void *data), void *data, const char namefmt[], ...)kthread_create函数与kthread_run函数类似，但是返回值类型为task_struct指针。
2005年7月系统工程理论与实践第7期 文章编号:100026788(2005)0720098207成对需求的局内k2服务器问题及其工作函数策略马卫民1,2,陈国青1(11清华大学经济管理学院,北京100084;21西安工业学院经济管理学院,陕西西安710032)摘要: 提出了多需求的k2服务器问题,建立了数学模型.研究了问题空间为k+2时的一个特例:即在任一时刻点都同时有两个服务需求提出.给出了此特例的工作函数策略,进行了相应的策略分析并给出了竞争比的证明.关于成对及多需求k2服务器问题的一般情形的策略设计及理论证明仍然是公开问题.关键词: 局内问题;成对需求;工作函数;竞争比中图分类号: T B11411 文献标识码: A On2line k2Server Problem with T win2request and ItsW ork Function Alg orithmMA Wei2min1,2,CHE N G uo2qing1(11School of Economics and Management,Tsinghua University,Beijing100084,China;21School of Economics and Management,X i’an Institute of T echnology,X i’an710032,China)Abstract: In contrast to the conventional k2sever problem with the assumption of only one request occurring at eachstep,we propose to investigate the k2server problem with multi2request for an on2line selection scheme.Firstly,weintroduce and explore the nature m odel of k2server problem with multi2request.Ouranalysis further focuses on the caseof twin2request,namely,at each step,tw o requests occur and the on2line player must choose tw o servers at the sametime to satis fy the requests.We employ the W ork Function Alg orithm to s olve it and give the relevant analysis andcompetitive ratio proof.The general cases oftwin2request and multi2request are still open.K ey w ords: on2line problem;twin2request;w ork function;competitive ratio1 引言近年来,局内问题及其竞争策略(On2line Problems and Their C om petitive Analysis)的研究成为优化领域里一个越来越热的研究方向.迄今涌现出了大量高水平的学术论文.国际上此类研究已经相当成熟,与本文有关的论文可参见[1～6].国内这方面的研究工作刚刚起步,可参见文献[7～13].k2服务器调度问题是局内竞争分析领域中一个重要的经典问题.有关结果见[1～4].本文是对传统服务器问题的一个推广.在传统的k2服务器调度问题中有一个基本的假设:即在一个新的服务需求到来时,所有的服务器都处于闲置状态,当此服务需求被满足后,下一个服务需求才能够到来.此处所说的“一个服务需求”是指考虑的问题空间(一般为度量空间———Metric S pace)上的一个顶点.而所有的服务需求的顶点按照服务需求提出的先后顺序排列起来就构成了所谓的服务需求序列.在上述基本假设下,局内决策者在每一次决策时,当新的服务需求提出时,只要从k个服务器中按照一定的局内策略选择一个服务器去完成该服务需求,并且在该服务需求完成之前不会有新的服务需求提出.但是,在现实生活中的很多情形下,有可能在同一时间有多于一个的问题空间上的顶点提出服务需求,因而局内决策者也需要同时调动相同数量的服务器去满足各个顶点的服务需求.根据这一背景,本文提出了多服务需求的局内k2服务器调度问题.多服务需求的k2服务器调度问题定义在一个度量空间M上.该度量空间(有可能为无限空间)由一收稿日期:2004206222资助项目:国家自然科学基金(70401006,70231010);中国博士后科学基金(2003034014) 作者简介:马卫民,清华大学经济管理学院博士后;陈国青,清华大学经济管理学院教授、博士生导师.个顶点集合Q 和一个距离函数d :Q ×Q →R +(非负实函数)构成,且该距离函数对于所有x ,y ,z ∈Q 满足三角不等式d (x ,y )≤d (x ,z )+d (z ,y ).且若d (x ,y )=d (y ,x ),则称该空间为对称度量空间.否则称该空间为非对称度量空间.显然,d (x ,x )=0成立.本文度量空间特指对称度量空间.给定度量空间M ,有k 个服务器往来服务于该度量空间上的各个顶点之间.把一个可能的k 个服务器所占据的位置称为一个结构(C on figuration ),显然可以用度量空间M 上的一个k 元顶点集来表示一个结构.总是假定k 个服务器最初占据的是一个固定的结构A 0.对于一个多元集合X 和一个顶点a ,用X +a 表示X ∪{a },而用X -a 表示X -{a }.最后,用C (X )来表示顶点集合X 中所有点对的距离的总和.在本文提出的多需求的k 2服务器问题中,一个服务需求也是用度量空间M 上的一个l 元顶点集合来表示的.记服务需求为r i ,此处r i ={a 1,a 2,…,a l },而a j ∈M ,它表示对于j =1,2,…,l ,在i 时刻每一个顶点a j 上都有服务请求提出.显然,可以假定l <k (否则,问题就变得非常简单).对一个服务需求进行服务则必须移动一些服务器去该集合中的顶点.而一个服务需求序列R 则是由k 个服务器往来服务的度量空间M 上的许多个(可能为无限个)l 2元顶点集合组成.综上所述,如果R =r 1,r 2,…,r n 是一个服务需求序列,那么k 个服务器对于R 的服务必然经历了一系列的状态A 0,A 1,A 2,…,A n ,当然r j <A j .在第j 步,完成服务需求r j 的费用实际上就是通过调动k 个服务器使得它们所处的状态从A j -1到A j ,显然这个费用为D (A j -1,A j ).那么完成服务需求序列的费用是所有的步骤的费用的总和.因为一个局内策略不能基于未来的服务需求进行决策,所以局内策略选择A j 只能依靠于初始状态A 0和服务需求序列的子序列r 1,r 2,…,r j .另外一方面,局外策略会事先知道整个服务需求序列,因而在这种情况下,局外策略则可以依据初始状态A 0和整个服务需求序列r 1,r 2,…,r n 选择A j .以C OPT (A 0,R )表示以初始状态A 0开始,并完成服务需求序列的最优局外费用.类似地,以C ON (A 0,R )表示局内策略完成服务需求序列的费用.则局内策略的竞争比可以用系数C ON (A 0,R )ΠC OPT (A 0,R )来度量[2].为了消除初始状态的影响,有必要给出竞争比一个更加严格的定义:对于任意的初始状态A 0和任意的服务需求序列R ,竞争比是满足下式的所有的c 的下确界(In fimum ),C ON (A 0,R )≤c ・C OPT (A 0,R )+β.(1)此处,β为只与初始状态A 0有关而与R 无关的一个常数.具有竞争比c 的局内策略称为c 2竞争的.显而易见,如果在度量空间M 中只有k 个或者少于k 个顶点,那么局内策略就可以在最开始时用所有的服务器覆盖(或者占据)所有的顶点.这样无论以后的服务需求序列是什么样的,决策者都不需要再对服务器作任何调动,因此该局内策略的竞争比可以达到1.另外,对于l 2服务需求的k 2服务器问题,如果l ≥k 成立,那么局内策略的竞争比也可以达到1.这是因为,按照上文对于多服务需求k 2服务器问题的描述,在同一时刻所有的k 个服务器都必须调动.综上所述,可以认为,研究l <k ≤n -2成立的条件下的多服务需求k 2服务器问题才是有意义的,此处n 为度量空间M 上的顶点数.2 预备知识本文主要研究l =2时的多需求k 2服务求问题,即成对服务需求的k 2服务求问题.给定一个度量空间M 和一个服务需求序列:R =(r 1,r 2,…,r n )=({a 1,b 1},{a 2,b 2},…,{a m ,b m }).(2)此处服务需求r i ={a i ,b i }指定了在i 时刻的提出服务需求的点对,则成对多服务需求k 2服务器问题就是对如何调动服务器以对成对服务需求作出反应的决策问题.与上文所述类似,所有服务器的初始位置可以被限定.对于任意服务需求r i ={a i ,b i },不外乎以下三种情形:1)情形1:如果顶点a i 和顶点b i 都有服务器,那么显然无需采取任何行动.2)情形2:如果顶点a i 和顶点b i 都没有服务器,则要调动或者选择两个服务器去这两个顶点进行服务.3)情形3:如果顶点a i 和顶点b i 中的一个上有服务器,而另一个顶点上没有,那么按照问题的描述,99第7期成对需求的局内k 2服务器问题及其工作函数策略两顶点中有服务器的顶点上的服务器要保持不动(因为该顶点也是服务需求提出的顶点),而从另外k-1个服务器中选择一个去那个没有服务器的顶点进行服务.满足所有的成对服务需求必须按照提出的先后顺序进行.完成一个服务需求序列的费用以所有的服务器所移动的总距离来表示.而解决成对多服务需求k2服务器问题的一个局内策略则必须是在这样一个附加的条件下进行决策,那就是在不知道未来的服务需求到来的任何信息的情况下选择并调动两个服务器去完成一个给定的成对服务需求.为了更好的描述成对需求服务器局内问题以及进行理论分析的方便,需要定义下面的函数:定义1 如果以i,j,h,l表示度量空间M上的任意的四个顶点,那么定义函数g如下所示:g(i,j,h,l)=min(d(i,h)+d(j,l),d(i,l)+d(j,h)).(3) 对于任意成对服务需求ri={a i,b i},如果一个调动策略是按照上文中所述的三种情形调动,而从不调动服务器去已经有服务器的顶点,则称该策略为懒惰策略.与传统的k2服务器问题中的有关结论[3]相似,下面的引理说明只需要把注意力集中在懒惰策略上.引理2 文献[3]对于成对服务需求的k2服务器问题和任何策略B,总存在一个改进的懒惰策略B′,其花费不大于B,并且如果B是局内策略那么B′也是局内策略.本文中策略将都是懒惰策略.本文所描述的局内策略还具有另外一个性质:如果提出服务需求的两个顶点都有服务器,则局内策略忽略该服务需求.显然,这种忽略不会影响到以后的决策.很容易证明在证明某一策略为具有某一竞争比的竞争策略时,同样只需要考虑这样的策略.如果某一策略B必须对某一需求序列中的任一服务需求多作出反应,即必须调动某些服务器才能完成该需求,那么该服务需求序列称为对于策略B的硬服务需求序列.对于所有的硬序列R和所有的策略B,论文[3]证明了如下引理:引理3 [3]如果局内策略B是一个忽略所有两个顶点都有服务器的成对服务需求的服务器策略,并且如果它也对于所有的它的硬服务需求序列是c2竞争的,那么局内策略是c2竞争的.上述引理说明:要想证明某一局内策略为竞争策略,那么只要把它们与懒惰策略在硬服务需求序列上进行比较就可以了.3 工作函数策略考虑度量空间M只有k+2个顶点的特殊情形,为了求出局内成对需求的k2服务器问题的竞争比,本文使用了著名的工作函数策略(W orkFunction Alg orithm(WFA)).K outs oupias和Papadimitriou[4]使用这一方法使得解决论文[3]中提出的著名的k2服务器猜想的研究进程向前推动了一大步.论文[4]使用这一方法给出了传统k2服务器问题的迄今为止的最好的关于竞争比的结果.本文中,也使用WFA来分析成对需求服务器局内调度问题在其问题空间为只有k+2个顶点的度量空间时的竞争比的情况.对于其它的特殊情形和该问题的一般度量空间情形下竞争比的情况则仍然是一些尚未解决的问题.在下文的证明中也使用了论文[4]中提出的延伸费用(extended cost)的概念.在此,有必要对工作函数重新定义,成对需求服务器局内调度问题与传统k2服务器问题的不同导致了工作函数的定义也发生了一些变化.定义4(工作函数(WorkFunction)) 给定一个度量空间M和一个初始状态A,对于任何包含M中的k个顶点的状态X和任一服务需求序列R=(r1,r2,…,r m),如果以ωi(X)表示完成R的子序列R i=(r1,r2,…,r i),开始于初始状态A0并结束于状态X的最优(最小)费用,那么把此定义在i时刻的所有状态的集合上的非负实函数称为完成子服务需求序列R i后的工作函数.从工作函数的定义中,可以发现一个非常重要的性质,那就是关于已经发生的调动的所有的有用的信息都被压缩进了工作函数.换言之,局内策略所要“记住”的仅仅是wi,而不是R i,因为任何别的策略都可以转化为具有这种性质的策略而不会使其竞争性有任何恶化.开始的时候,状态X的工作函数仅仅是把所有的服务器从状态A0移动到状态X的最小费用,即ωe(X)=D(A,X).按照本节开始部分的叙述和工作函数的定义,有下面的推论:推论5 工作函数具有下面的一些性质:001系统工程理论与实践2005年7月1)对于任一状态X ,如果r i ={a i ,b i },那么w i (X )=w i -1(X )if a i ,b i ∈Xmin x ∈X{w i (X -x +a i )+d (x ,a i )}if a i |X ,b i ∈Xmin y ∈X{w i (X -y +b i )+d (y ,b i )}if a i ∈X ,b i |X min x ,y ∈X {w i (X -x -y +a i +b i )+g (x ,y ,a i ,b i )}if a i ,b i |X (4) 事实上,可以把上面公式中的四种情况合并成为一个公式:w i (X )=min x ,y ∈X{w i (X -x -y +a i +b i )+g (x ,y ,a i ,b i )}=min x ,y ∈X {w i -1(X -x -y +a i +b i )+g (x ,y ,a i ,b i )}.(5) 此处X -x -y +a i +b i 表示一个具有k 个顶点的状态,该状态是通过用a i 或者b i 代替状态X 中的x 或者y 得到的;2)对任一状态X ,有w i (X )≥w i -1(X );3)对于任何状态X 和Y ,w i (X )≤w i (Y )+D (X ,Y );4)对于任何状态em ph X 和成对服务需求序列R ,有C OPT (R )≤w m (X ).证明 由工作函数的定义可以立刻得到性质1)和性质4).下面证明性质3).按照w i (X )的定义,k 个服务器在该时刻必然结束于状态X ;而且先使k 个服务器处于Y 状态然后再从Y 状态按照最小匹配的调动方法达到X 状态显然也可以完成这个过程.因此,性质3)成立.由性质3)和性质1),可以立刻得到性质2).下面给出用以解决成对服务需求的k 2服务求问题的工作函数策略.定义6(工作函数策略) 以R i -1表示一个服务需求序列,以A i -1表示某一局内策略完成序列R i -1后所处的状态.则当一个新的服务需求r i ={a i ,b i }到来时,工作函数策略将调动服务器达到一个状态A i ,并使得r i <A i 且w i (A i )+D (A i -1,A i )达到最小.按照工作函数以及函数g 的定义,易知存在顶点s i ,t i ∈A i -1使得状态A i =A i -1-s i -t i +a i +b i 最小化w i (A i )+D (A i -1,A i ).据此得到:w i (A i -1)=min x ,y ∈A[w i (A i -1-x -y +a i +b i )+g (x ,y ,a i ,b i )]=w i (A i )+g (s i ,t i ,a i ,b i ).(6)显而易见,工作函数策略完成服务需求r i ={a i ,b i }的费用就是g (s i ,t i ,a i ,b i ).因此,工作函数策略完成服务需求序列R =(r 1,r 2,…,r m )的费用为:C ON (R )=∑m i =1D (A i -1,A i )=∑mi =1g (s i ,t i ,a i ,b i ).(7) 为了求得工作函数策略的竞争比,必须考虑相应局外问题的最优策略.在此,介绍一个重要的概念:局外虚拟费用(O ff 2line Pseudocost )[4].局外虚拟费用相当简单的但是能够非常精确地计算局外费用.从状态A i -1到状态A i 的局外虚拟费用定义为:w i (A i )-w i -1(A i -1).(8)显然,局外虚拟费用的总和就等于相应的所有状态转移发生的局外虚拟费用的总和,即,局外策略完成服务需求序列R 的最优费用为:C OPT (R )=∑mi =1[w i (A i )-w i -1(A i -1)].(9) 不失一般性,假设局内策略与局外策略完成序列后它们的服务器处于同一种状态.否则,如若不然,则可以延伸局外策略对应的最终状态的服务需求序列中的服务需求,这种延伸在增加局内策略的费用的同时并不增加相应的局外策略的费用,从而达到假定的状态.现在来观察第i 步的局外虚拟费用和局内费用的和:101第7期成对需求的局内k 2服务器问题及其工作函数策略w i (A i )-w i -1(A i -1)+g (s i ,t i ,a i ,b i ).(10)此值等于w i (A i -1)-w i -1(A i -1).而后者则显然上有界,即该表达式将在问题的所有可能状态中某一状态上达到最大.因此,局外虚拟费用和局内费用的和被限定于下式:max X [w i (X )-w i -1(X )].(11) 此外,还需要介绍另外一个同样重要的概念,扩展费用(Extended C ost ):定义7(扩展费用) 完成服务需求序列R 的第i 个服务需求的扩展费用为:ψi =max X [w i (X )-w i -1(X )].(12)依此类推,完成服务需求序列R 的总的扩展费用为:Ψ(R )=∑mi =1ψi .(13)如果状态A 能够使得扩展费用的值最大,那么就说扩展费用发生在状态A 上.显然,根据竞争比的定义和扩展费用的定义可以得到如下引理:引理8 对于任意服务需求序列R ,如果总扩展费用被限制在局外策略的最优解的c +1倍加上一个常数之内,那么工作函数策略是一种c 2竞争的竞争策略.证明 只需证明Ψ(R )≥C ON (R )+C OPT (R ).Ψ(R )=∑mi =1max X [w i (X )-w i -1(X )]≥∑m i =1[w i (A i -1-w i -1(A i -1)]=∑mi =1[w i (A i )+g (s i ,t i ,a i ,b i )-w i -1(A i -1)]=∑m i =1g (s i ,t i ,a i ,b i )+∑mi =1[w i (A i )-w i -1(A i -1)]=C ON (R )+C OPT (R ).(14)证毕.事实上,扩展费用是一种对实际发生的局内费用与最优局外费用的放大估计.利用扩展费用代替实际费用的优点使得不必考虑局内服务器的所有的可能状态.换言之,为了证明工作函数策略是竞争的,只需要证明某一个不等式对于所有的工作函数都成立.当然,这种方法也有其自身的缺点,那就是扩展费用有可能放大估计工作函数的费用.4 度量空间有k +2个顶点本节考虑局内成对需求服务器局内调度问题的一个特例:即问题空间为只有k +2个顶点的度量空间.利用局内问题及其竞争策略理论中的重要方法-势能函数法-可以很快地证明:对于这一特例,工作函数法是一种k 2+3k 2-竞争的竞争策略.定理9 对于成对需求服务器局内调度问题,在只有k +2个顶点的度量空间中,工作函数策略是k 2+3k 2-竞争的.证明 考虑势能函数Φ=∑X ω(X ).(15)当对服务需求r i 进行服务时,假定两种策略调动服务器来完成这种服务.一种策略为被称为局外敌手的局外最优策略,而另外一种为工作函数策略(局内策略).按照上一节的讨论,易知如下事实:ΔΦ≥w i (S )-w i -1(S ).(16)201系统工程理论与实践2005年7月此处状态S 最大化w i (X )-w i -1(X ).然后,对服务需求序列的所有服务需求,即对上式两边求和并根据引理2～3可知:Φf -Φ0≥C ON (R )+C OPT (R ).(17)此处Φf 和Φ0分别表示势能函数的初始值和最终值.而且,有:Φf ≤k +12・max X w f (X ).(18)此处w f (X )表示对于所有可能的最终状态的工作函数值.而可能最终状态的个数为k +22.令状态T 最大化w f (X ),则由于推论5中的性质3)有:w f (T )≤w f (C f )+D (T ,C f ).(19)此处C f 表示工作函数策略和相应的局外最优策略同时达到的最终状态.所以有:Φf ≤k +22・w f (C f )+k +22・D (T ,C f ).(20)注意到上述不等式右侧的最后一项的值被限制在度量空间中任意顶点对的距离之和C (X )的k +22倍之内,所以它是一个常数,记为β.至此,证明了:C OPT (R )+C ON (R )≤Φf -Φ0≤k +22・w f (C f )+β.(21)按照工作函数和最优解的定义,有:C OPT (R )=w f (C f ).(22)最后,有:C ON (R )≤k 2+3k 2・C OPT (R )+β.(23)证毕.事实上,对问题的度量空间具有n 个顶点(当然,n ≥k ≥2,否则问题就变得意义不大了)的局内成对需求的k 2服务器问题,有相似的结果.即:定理10 对问题的度量空间具有n 个顶点的局内成对需求的k 2服务器问题,如果n ≥k ≥2成立,则工作函数策略具有竞争比nk -1的竞争策略.定理10的证明与定理9的证明类似,在此省略其详细证明过程.事实上,根据排列组合的知识,定理9为定理10的自然推论.5 结束语本文把传统的k 2服务器问题的概念推广到多服务需求k 2服务器问题.这一推广使得相关模型更加接近于现实问题.这是因为,在现实生活中,经常会发生一种“多点爆发”(Multi 2erupting )的情形,即在同一时刻同时有多于一个的顶点提出服务需求而不是传统问题中的仅有一个顶点提出服务需求.但是,显然这种推广使得问题的时间和空间复杂性变得很大,而其策略的设计也相应的变得非常困难.在本文中,即使只是考虑了成对服务需求的情形,问题仍然变得比传统的k 2服务器问题复杂很多.事实上,本文只解决了成对需求服务器局内调度问题的一个特例.该问题的其它情形还没有任何结果.在竞争比的下限的改进方面,相信对于成对需求服务器局内调度问题存在更好的(即比本文的结果稍微大一些)结果.另外一个未解决的问题是证明工作函数策略对于成对需求服务器局内调度问题的本文的特例具有更小的竞争比,或者对其它情形是竞争的.还有,是否能提出更好的策略来解决该问题或者该问题的某些特例,也可以成为未来的研究方向之一.301第7期成对需求的局内k 2服务器问题及其工作函数策略401系统工程理论与实践2005年7月参考文献:[1] S leator D D,T arjan R E.Am ortized efficiency of list update and paging rules[J].C ommunications of the AC M,1985,28:202-208.[2] Manasse M S,McG eoch L A,S leator D D.C ompetitive alg orithms for on2line problems[C].Proceedings20th Annual AC MSymposium on Theory of C omputing,1988,322-33.[3] Manasse M S,McG eoch L A,S leator D D.C ompetitive alg orithms for server problems[J].Journal of Alg orithms,1990(11),208-230.[4] K outs oupias E,Papadimitriou C.On the k2server conjecture[J].Journal of AC M,1995,42(5):971-983.[5] Ma W M,Xu X F,Wang KL,k2T ruck problem and its competitive alg orithms[J].Journal of G lobal Optimization,2001,21(1):15-25.[6] Ma W M,Y ou J,Xu Y F,Liu J,Wang KL.On the on2line number of snacks problem[J].Journal of G lobal Optimization,2002,24(4):449-462.[7] 堵丁柱.k车服务问题与竞争策略[J].数学的实践与认识,1991(4):36-40.Du D Z.k2server problem and competitive alg orithm[J].Mashematics in Practice and Theory,,1991(4):36-40.[8] 徐寅峰,王刊良.局内出租车问题与竞争策略[J].西安交通大学学报,1997,1:56-61.Xu Y F,Wang KL.On2line k2taxi problem and competitive alg orithm[J].Journal of X i’an Jiaotong University,1997,14(1):56 -61.[9] 马卫民,刘新梅.售后服务交通费用管理的竞争策略[J].华中科技大学学报,2001,29:105-107.Ma W M,Liu X M.The competitive stragegies for the management of the after2sale service team’s expense[J].Journal of Huazhong University of Science and T echnology,2001,29:105-107.[10] 马卫民,王刊良.局内管理问题及其竞争策略论[J].管理科学学报,2003,6(2):29-34.Ma W M,Wang KL.On2line management decision problem and its competitive strategies[J].Journal of Management Science in China,2004,6(2):29-34.[11] 马卫民,徐青川.局外出租车问题及其动态规划求法[J].系统工程学报,2001,16(6):481-485.Ma W M,Xu Q C.O ff2line scheduling of k2taxi problem and its dynamic programming procedure optimal alg orithm[J].Journal of System Engineering,2001,16(6):481-485.[12] 马卫民,徐青川.局内军车调度的时间优化及其竞争策略[J].系统工程学报,2002,17(5):395-400.Ma W M,Xu Q C.T ime optimization of on2line k2militaty2truck scheduling and its competitive stragegies[J].Journal of System Engineering,2002,17(5):395-400.[13] 马卫民,王刊良.局内封闭式车辆调度问题及其竞争策略[J].系统工程理论与实践,2004,24(9):72-78.Ma W M,Wang KL.C ompetitive analysis for the close on2line truck scheduling problem with time2window[J].System Engineering -Theory and Practice,2004,24(9):72-78.。
