文摘

我们考虑一个调度问题资源依赖的释放时间和两个代理同时存在。两个代理共享一个共同的单一机器,每个代理希望最小化代价函数依赖于自己的工作。每一个的释放时间一个代理的工作相关的资源消耗。目标是找到一个时间表的问题最小化一个代理的资源消耗总量限制B代理的极小化。最优属性和最优多项式时间算法提出了解决调度问题。

1。介绍

可替换主体机调度问题近年来受到越来越多的关注。不同的代理共同处理机器,每个代理希望最小化代价函数取决于其工作。调度与多个代理首先引入了贝克和史密斯(1)和Agnetis et al。2]。贝克和史密斯(1)考虑的问题最小化代理人的目标函数的凸组合。他们提供了一些优势属性和证明变得计算困难的问题。Agnetis et al。2)解决调度问题的两个代理竞争使用共享的处理资源和优化每个代理都有自己的标准。他们研究了约束优化问题和Pareto-optimization问题在单个机器上和购物环境。Agnetis et al。3]分析的复杂性,一些可替换主体调度算法在单个机器上的问题并提出解决方案。李等人。4)为可替换主体提供近似算法调度最小化加权总完工时间。Gawiejnowicz et al。5)考虑单机two-agent调度问题比例恶化作业处理时间。阴et al。6)考虑几个two-agent调度分配在单个机器上截止日期的问题。程等。7]研究two-agent单机调度问题与释放时间最小化加权总完工时间。Yu et al。8]调查几个单机two-synergetic-agent调度问题。阴et al。9)考虑two-agent单机调度问题无限制的到期日期的任务。

资源消耗的调度问题研究了多年。[" Janiak Cheng和10]研究工作完成的resource-optimal控制在单个机器上最大作业完成时间的约束。Vasilev和富特11]调查一个单机调度问题,资源消耗取决于工作的释放时间。Kaspi和Shabtay12)考虑调度工作的问题在一个机器作业处理时间可控通过共同的分配有限的资源。小王和程13)考虑单机调度问题与资源依赖的释放时间和处理时间。魏et al。14)考虑单机调度time-and-resource-dependent处理时间。J.-B。小王和安茂忠编。王(15)考虑单机调度与约束凸资源消耗最小化总加权总流程时间。阴et al。16)考虑单机由于窗口分配和调度问题的一个共同的流津贴和可控的工作处理时间。陆et al。17)考虑单机earliness-tardiness和交货期进行任务调度问题,处理时间的一份工作是一个函数的位置在一个序列及其资源分配。

然而,我们所知,没有工作已经完成模型与资源依赖的释放时间和可替换主体的这两个方面的文献。这两个类别的调度问题被广泛,分别研究在过去的二十年。two-agent调度问题在这篇文章中,我们研究与资源依赖的释放时间,在单个机器上的目标是找到一个时间表,将一个代理的目标函数最小化目标函数的限制其他的代理不能超过一个给定的绑定。考虑的问题属于资源消耗和多个代理的调度问题。这样一个调度问题常发生在钢铁行业。[" Janiak18)描述了实际调度问题与资源依赖在钢厂释放时间,在批锭必须预热才能在初轧机热轧,锭预热时间成反比的资源消耗总量。

本文的其余部分组织如下。节2,我们将描述该问题。节3,我们开发的最优多项式时间算法two-agent单机调度问题。部分4给出了一些结论。

2。问题描述

我们现在正式描述我们的问题。有两个独立的家庭和无优先工作和要处理在一个共同的单一机器。的工作和被称为代理的工作,分别代理的工作。与每一个相关的工作,让表示处理时间和。发布时间相关资源的数量,消耗在工作。严格递减连续函数。我们将作为资源消耗函数。我们假设。每一个代理的工作可以在任何时间开始后的释放时间的工作,和工作之间的空闲时间是被允许的。由于消费函数严格不断减少,我们可以假设每个工作开始就可用。也就是说,我们可以,在那里的起始时间是工作吗。与每一个相关的工作,让和表示处理时间和释放时间,分别。让表示一个可行的时间表的就业机会。让表示的完成时间代理的工作根据日程安排。代理人的目标函数减少资源消耗的总量。代理人的目标函数是最小化最大完工时间的吗。

我们的目标是减少资源消耗的总量的代理最大完工时间的限制的代理不能超过一个给定的绑定。如果该值太小,调度问题的一个实例可能没有可行的解决方案。如果至少有一个可行的解决方案,我们说实例可行的。根据延用符号格雷厄姆et al。19),调度问题是表示。

3所示。主要结果

在本节中,我们开发一个最优多项式时间算法来解决这个问题。

给定一个序列,对于每一个代理的工作,完成时间可以递归地完成吗,,。

因此工作的完成时间也可以作为吗。

此外,让最大作业完成时间用;然后。

引理1。给定一个序列和一个常数,定义。然后,如果,序列对应于一个不可行的计划。

现在我们可以定义边界的约束。定义。以下部分将分析局限于案件中。

引理2。一个最优调度存在的代理的工作处理nonincreasing处理时间。

证明。资源消耗函数是一个严格递减连续函数代理的工作。自发布代理的工作早消耗更多的资源,代理的工作应该尽可能晚发布。因此代理的工作应该在nonincreasing发布的顺序。

引理3。一个最优调度存在的代理的工作在不减少的释放时间的顺序处理。

证明。代理的考的最大完成时间吗在单独的机器代理人的工作;也就是说,代理的极小化最后的完成时间吗代理的工作。使用成对的工作交换参数,我们可以处理代理的工作在不减少的释放时间。

接下来,一个算法来确定一个最优问题的时间表开发如下。

算法4。
步骤1。安排代理的工作根据的nonincreasing顺序和表示代理的工作不减少的顺序排序的作为一个虚拟的工作。
步骤2。定义序列和计算为代理。序列是一个最优计划开始的时间代理的工作给出了,,。

定理5。算法4生成最优时间表问题在时间。

证明。最优的证明很简单的前题的结果1- - - - - -3。我们现在时间复杂度。时间序列的工作集根据的nonincreasing顺序是。时间序列的工作集根据不减少的订单是。创建虚拟工作会导致操作。所以整个算法的计算复杂度4是有界的。这就完成了证明。

4所示。结论

在本文中,我们将安排两个重要的问题,最近收到研究人员越来越多的关注:资源依赖的释放时间和多个代理。我们的目标是找到一个时间表的问题最小化代理的资源消耗总量限制代理的极小化。我们建议最优属性和最优多项式时间算法的调度问题。

未来的研究可以指导分析等目标函数最小化问题的后期工作,总加权完工时间和迟到。一个有趣的研究课题也分析调度问题有超过两个代理或其他机器环境。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

作者感谢编辑和评论员对他们有帮助的意见和建议。这项研究是由中国国家自然科学基金(批准号71001074),辽宁高校优秀人才项目(批准号WJQ2013003)。