实时调度的在线链划分模型" - 任务调度中的在线算法与区间图着色问题

理论计算机科学电子笔记140（2005）15-29www.elsevier.com/locate/entcs实时调度的在线链划分模型Przemyslaw Broniek普热梅斯拉夫·布罗涅克1，2波兰克拉科夫雅盖隆大学计算机科学系摘要我们认为在线链分割的偏序集作为一个理论模型的一些变种的任务调度。将我们自己限制在由它的表示给出的区间序上，这个问题等价于区间图的着色问题。我们证明了由它的表示给出的区间序的在线链划分的增长变体具有最优解（最近拟合算法）。我们还考虑了在线链划分的区间订单没有表示，并证明了增长的版本（3W/ 2）的下界。此外，我们表明，没有在线算法构造表示的区间订单和图。保留字： 在线算法，调度，链划分，上生长，区间序1引言我们考虑一组任务，它们之间有一些关系。单个任务必须由单个处理器计算。在实时情况下，我们一次得到一个任务，并立即决定在哪个处理器上计算它我们的决定是不可改变的。我们的目标是尽量减少使用的处理器数量。我们希望使用关于任务之间关系的额外知识，因此我们在调度中添加了一条规则独立的任务必须被调度到不同的处理器。那是因为[1]我要感谢我的顾问Pawel Idziak，他向我介绍了这个问题，进行了多次讨论，并帮助我更好地理解这个问题。2电子邮件地址：broniek@ii.uj.edu.pl1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.06.02716P. Broniek/Electronic Notes in Theoretical Computer Science 140（2005）15−这样的任务可以并行计算，并且我们希望为了效率的目的而提供这一点。这种情况也可以被解释为两个人的游戏。第一个人提出任务，第二个人为他们分配处理器一个以点为任务的偏序集是这个问题的一个完美的数学模型。由单个处理器计算的任务形成一个链。因此，调度可以被认为是链划分。链划分的o-线版本有一个多项式时间算法，它给出了w（偏序集的宽度）链（Dilworth [2]）。在线（实时）版本更令人兴奋。最著名的在线算法给出指数链数（Kierstead [5]，（5w 1）/4）。当偏序集不增长时，我们也可以考虑限制性问题在这种情况下，解是具有上下界的二次方程（Felsner [3]，w（w+1）/2）。将我们自己限制在由其表示给出的区间阶，一般问题是线性的，等价于区间图的着色问题（Slusarek [8]，3w- 2）。我们证明了由其表示给出的增长区间序的在线链划分具有基于贪婪策略的最优解（Nearest-Fit算法）考虑到不带表示的区间序的在线链划分，情况发生了很大变化。最近拟合算法不起作用。我们证明了不存在构造区间序和区间图的表示的在线算法，这迫使我们设计新的算法。我们还证明了增长版本的问题的下界的变化。在第二节中，我们收集了关于偏序集和链划分的必要的基本事实第3节继续研究这个问题的在线版本，并提供我们的游戏的详细描述第四节研究了区间序类接下来的部分讨论这个类中的链划分问题提出了一种精确的最近拟合算法。最后，第四节讨论了区间序的表示不确定时的问题。我们证明，没有在线算法构造这样的表示。给出了增长区间序的在线链划分的一个下界（3w/2）.2基本事实我们称一对P=（X，P）偏序集（简称偏序集），如果X是一个集合，P是X上自反、反对称、传递的二元关系。集合X称为P的基集，X的元素称为点。关系P称为X上的序。P. Broniek/Electronic Notes in Theoretical Computer Science 140（2005）1517631≺∈ǁ||例2.1设X={ 1， 2， 3， 4， 5， 6}，P={（x，y）∈ X × X：x整除y}。当（x，y）∈P时，记x≤y，y≥x。 符号x y表示x≤y和xy。设x，y∈P，其中x/=y。我们说x和y是当x> y或x> y时，在P中可比较。两个元素是不可比拟的（表示为x y），当它们不具有可比性时。我们说x被P中的y覆盖，记为x y在P中，当x y，并且没有点z X，对于x z y在P中。我们利用Hasse图在欧氏平面上画偏序集P。 该图是有向无环图（简称dag）G =（X，E），其中E={（x，y）∈ X × X：x <$y}。下一张图是例子2.1中偏序集的图。我们总是假设在这样的图表，方向的边缘是从底部到顶部，不画他们。42 5对于偏序集P=（X，P）和X的非空子集Y，P对Y的限制（记作PY）是Y上的偏序，我们称（Y，PY）为（X，P）的子集.偏序集P=（X，P）称为链，如果X中任意两点在P中可比较。如果P是链，我们也说P是X上的线性序（全序）。 类似地，我们称一个偏序集为反链，如果任意两个X的点在P中是不可比较的。一个非空子集Y<$X称为链（分别为反链），如果子集（Y，P |Y）是链（分别为反链）。一个链C是一个最大链，如果没有其他链包含更多的比C。 最大反链的定义类似。一个点x∈X称为极大点（极小点），如果没有点y∈X使得x y在P中（x>y在P中）。偏序集（X，P）的高度是最大链中的点数偏序集（X，P）的宽度是最大反链中的点数当P和Q是同一集合X上的偏序时，我们称Q是P的扩张，如果P<$Q，这意味着对所有x，y∈X，x y在P中蕴涵x y在Q中。18P. Broniek/Electronic Notes in Theoretical Computer Science 140（2005）15222∪ ∪∪联系我们关于我们关于我们--Q是P的线性扩张，如果它是线性序。在例2.1的偏序集中，最大点是4、5和6。子集1、 2、 4、1、 6、5是链（以及其他）。亚组4、 5、 6、2、 3、 5，4、 6是反链。子集A=3，4，5是最大反链。我们也有高度（P）= 3和宽度（P）= 3。现在我们可以解决链划分的问题给定P=（X，P），我们想找到集合X的一个划分，划分成非空的、不相交的链Ci，使得X=Ci。此外，我们希望这个划分具有最少数量的链。我们可以清楚地看到，必须至少有宽度（P）的链，因为最大反链的每个元素必须属于不同的Ci。从下一个定理我们知道，这个下界总是可以达到的。定理2.2（Dilworth [2]）若P =（X，P）是偏序集且宽度（P）= n，则存在划分X = C1C2.Cn，其中Ci是链，i = 1，2，.，n.虽然它不是直接从这个定理，我们可以很容易地得到划分成链组成的只有不相交的链。一个算法（例如[7]中描述的）可以在O（|X|5/2）步骤。例2.1中偏序集的链划分例如是：2，4，1，3，6，5。我们可以用颜色（这里用1、2和3表示）来识别链，并用相应的数字标记属于每条链的点，如图所示。下图：11 3由于这种等价性，我们在处理链划分的在线算法时有时会用颜色来识别链假定偏序集的o-线链划分可以很容易地用多项式时间算法计算，其大小等于偏序集的宽度。3问题的在线版本偏序集的在线链划分可以看作是两个人之间的博弈：Alice（A -攻击者）和Bob（B -防御者）。游戏分为几轮，从空偏序集开始在每一轮爱丽丝P. Broniek/Electronic Notes in Theoretical Computer Science 140（2005）1519121121ǁ用一个新的点x来扩展前一轮的偏序集。她描述了x和前几轮得分之间的Bob通过将x分配给一个链来响应。他可以把它放到现有的链上，也可以创建一个新的链。他不允许在链条之间移动任何点在每一步，我们感兴趣的是他创建了多少链（游戏的值），对应于需要多少链来覆盖偏序集，它等于偏序集的宽度鲍勃需要创建的最小可能数量的链来覆盖在线偏序集，简称为偏序集的在线宽度图为随后的两轮比赛。Bob构造的链用自然数表示。如前所述，我们称它们为颜色，因此用每种颜色着色的点形成一个链。爱丽丝给出的新我们可以看到，Alice迫使Bob使用更多的颜色（构造更多的链），这是需要的，以覆盖偏序集，我们知道偏序集是3。41 31 3实施例3.1这个例子展示了游戏的本质。爱丽丝的策略迫使鲍勃的防守策略Kierstead在[6]证明了Bob的一个贪婪First-Fit策略可以强制使用无限数量的链来划分一个具有O-线宽2的偏序集正如在引言中提到的，偏序集P=（X，P）的在线链划分可以用作调度任务的理论模型。 一组任务就是基集X。任务之间的关系由它们的顺序P描述。简单的xy意味着任务x必须在任务y之前计算，例如因为任务y使用任务x的结果。另一方面，xy意味着任务可以并行计算，因为它们是独立的。我们可以想象，在实际情况下，每个任务都必须由单个处理器计算。我们希望通过告诉哪个处理器以什么顺序计算哪些任务来调度它们。我们假设我们事先不知道计算每个任务所需的时间（我们将在第5节放松这个假设）。这是很自然的，因为如果x，y，我们还没有计算任务x，那么我们就不知道所有的输入，这可能会影响到20P. Broniek/Electronic Notes in Theoretical Computer Science 140（2005）15−2任务y的执行时间。此外，我们将只计划计算，而不会在计算过程中改变我们的时间表。这给我们的调度带来了一个限制：独立的任务必须由不同的处理器计算。在这样的环境中，调度可以被认为是链划分。由每个处理器计算的任务形成一个链。我们希望将任务集划分为最小数量的链，从而使用最少数量的处理器。在实时的情况下，我们一次得到一个任务，并合理地分配处理器给它。这种情况是我们的在线游戏的实际实现。爱丽丝是任务的破坏者，鲍勃是任务的在线调度者下一个定理总结了我们目前对链划分博弈的价值的认识定理3.2（Szemer′edi，Kierstead[5]）F或eachw∈N：.w+12≤在线宽度（w）≤5周1.4正如我们所看到的，下限和上限之间的距离是巨大的。这个问题已经防御了20多年的攻击，并且仍然以其指数漏洞吸引着到目前为止，唯一的进展是解决了一个特殊情况：定理3.3（Felsner [3]）线上宽度（2）= 5。如果我们改变游戏规则，我们可以说得更多。第一个有价值的修改，由Felsner在[3]中给出并解决，限制了Alice的合法移动。规则是Alice给Bob点数的序列是该顺序的线性扩展这意味着在每一轮中，Alice给出的新点在我们的实际情况中，这意味着我们不允许在先前给定的任何其他任务之前计算新任务这个博弈的变体被称为向上生长，因为在偏序集的哈塞图上，新的点总是在前一个点之上。在例3.1中，根据这个规则，爱丽丝的移动是合法的我们的最后一个预备定理给出了具有“增长”限制的问题的解定理3.4（Felsner [3]）对于每个w∈N：宽度up-gr owingon-line（w）=.w+1P. Broniek/Electronic Notes in Theoretical Computer Science 140（2005）1521631∈∩4区间订单一个偏序集称为区间序，只要它能在一条实直线上用区间表示。 更精确地说，对于偏序集P=（X，P），存在一个函数F赋予每一点x X一个实直线R的非退化闭区间F（x）= [ax，bx]，使得x y在P中当且仅当bx ay在R中。函数F称为偏序集P的区间表示。然而，如果取R的退化或开的甚至无界的区间，则没有区别关键的性质是R的连通子集。区间表示（如果我们只关注区间而不是函数F）可以解释为区间图。一个图G=（V，E）称为区间图，如果存在一个函数F给每个顶点v∈V赋予一个区间F（v）=[av，bv]，所以xy是G边当且仅当F（x）F（y）F称为图G的区间表示。- 是的相似函数下图显示了偏序集和图的公共区间表示例2.1中的偏序集恰好是interval。P：G：42 44 62 51 3 63 552 1下一个定理给出了区间序令人惊讶的特征定理4.1（Fishburn [4]）偏序集P =（X，P）是区间序当且仅当它不包含S2= 2 + 2作为子偏序集。S2=2+2：22P. Broniek/Electronic Notes in Theoretical Computer Science 140（2005）151115最近拟合算法在给出区间序之后，我们可以在这类偏序集上玩我们的游戏这还假设，在每一轮中，Alice给出的偏序集必须是一个区间序。我们假设Alice通过表示给出偏序集这意味着我们得到新的点x作为对F（x）= [ax，bx]。在下一节中，我们将看到，如果新的点没有区间表示，那么博弈的价值是不同的。首先注意，区间序的链划分问题等价于区间图的图着色问题。事实上，区间序中的链由一族不相交的区间表示这样一个族显然对应于从偏序集的区间表示得到的区间图中的因此，区间图的在线染色等价于区间序的在线链划分。最优着色与相应偏序集的最优链划分我们可以在下面的图片中清楚地看到它：P：G：22 22 12 31 1 11 332 1区间图的在线着色在更早的时候就被研究过了，我们知道这个问题的精确上下界定理5.1（Chrobak，Slusarek [1]，[8]）对于每个n∈N：区间图表示在线着色（n）= 3 n − 2。[8]中给出的算法甚至更强。它为我们在上一节中定义的更广泛的圆弧图类这就完成了由表示给出的区间序的在线链划分的研究，因为我们可以使用该算法，并且只改变所描述的结果的解释。对成长版的博弈进行分析，由于攻击者的行动受到限制，得到了更好的结果P. Broniek/Electronic Notes in Theoretical Computer Science 140（2005）1523≤定理5.2对于每个w∈N：区间有序表示宽度在线上生长（w）= w。证据结果是通过使用Bob的Nearest-Fit算法实现的。它是一个贪婪算法，这意味着它不会使用新的颜色（构造新的链），直到它被迫这样做。每当有多种颜色选择的可能性时它选择这样一种颜色，用一个最右端的间隔表示。如下图所示：2 2111？3该算法从可用的1和2中选择颜色编号1。色数3是禁止的，因为我们的新区间与色数为3的区间相交，因此不能形成链。很明显，如果不给出表示，算法将无法工作这种表示使得防御变得更加容易，因为它带来了更多关于偏序集的信息。我们将通过对偏序集在任意轮后的宽度w的归纳来证明这一命题如果，在一轮之后，我们有w= 1，那么偏序集是一个链，我们在游戏中只使用一种颜色这是微不足道的，因为每个新的间隔都在前一个的右边。假设命题对每个w n成立，我们将证明它对w=n+1。每轮之后，颜色的数量和宽度最多增加让我们用c表示颜色的数量。假设，与我们的主张相反，在Bob移动之后，只有当c=w+ 1时，它才可能发生，这意味着在这个特定的回合中，偏序集的宽度没有增加，鲍勃被迫使用一种新的颜色。让我们在下面的图片上分析一下这种情况：213X24P. Broniek/Electronic Notes in Theoretical Computer Science 140（2005）15∈∈\n在底部有一个新的区间（用x表示），还有一些其他的（不是所有的）区间是Alice之前添加的。让我们用E表示Bob在前几轮中构造的每个链的最右边区间的集合。包括新颜色在内的颜色数为c。因此，E中的间隔为从1到c-1。每一个区间e ∈ E与x相交。由于向上增长规则，没有区间可以在x的右边。当Alice给出新元素时，它必须是最大的假设一个区间y位于x的左边，颜色为z。因为它是最右边的区间，颜色为z，鲍勃可以选择z来给x着色，这与鲍勃被迫为x生成新颜色的假设相矛盾。这证明了这一说法。我们要证明有一条垂直线，它至少以w+1的间隔与所有点这将与我们关于偏序集的宽度为w的假设相矛盾。设f表示距离E的区间，使得f的右端是eE中可能的最小值。考虑一条垂直虚线穿过f的右端。它与f，x相交，可能还有其他距离E的区间。G实际上，我们将展示这条虚线必须与每种颜色的间隔相交。假设区间g E不与虚线相交。这意味着g完全位于f的右边。由于偏序集是以一种向上生长的方式表示的，我们知道g是Alice在f之后给出的。另一方面，我们知道g和f获得了不同的颜色，否则g将在E中表示它的颜色（而不是f）。设G是与g颜色相同的区间链，G1={g1∈G：g1>f}. 由于g∈G1，我们可以在G1中选取最小的g1。如果G G1=，则g1是其颜色的第一个区间。但这是不可能的，因为没有必要创建这种颜色，例如f的颜色可以用于g1。因此，在G\G1中存在最大的元素，例如g0。FeXP. Broniek/Electronic Notes in Theoretical Computer Science 140（2005）1525∈F的g0G1eX注意g0的左端并不大于f的右端（虚线），否则g0G1。此外，g0的右端不小于f的右端，否则最近拟合策略将为g1提出另一种颜色，例如f的颜色。因此，虚线与g0相交。这表明c种颜色中的每一种都出现在与虚线相交的间隔因此偏序集的宽度是最小的c，与我们的假设w c相反。Q这完成了我们对区间序的链划分的研究在我们的实际应用中，这种限制也很有趣。我们只需要考虑在具有额外时间维度的公共环境中调度任务在这种情况下，我们获取每个任务的执行开始和结束时间的信息我们的Nearest-Fit算法为我们提供了这样的任务的最佳调度。6不带区间表示的区间订单在这一节中，我们考虑同样的问题，即区间序的在线链划分，但这一次鲍勃没有得到爱丽丝给他的点显然，我们的最合适策略不再起作用。我们首先考虑的是增长的版本。在这种情况下，爱丽丝可以强迫鲍勃构建更多的链，给他一个区间顺序：定理6.1对于每个w∈N：3w间隔有序宽度在线上生长（w）≥ 2.证据让我们首先证明：区间订单宽度在线增长（2）≥3.如下图所示26P. Broniek/Electronic Notes in Theoretical Computer Science 140（2005）15}--−−312121311212Alice首先给出两个不可比的元素，Bob被迫使用两种不同的颜色，比如1和2，来表示这些点。现在Alice添加了一个新点，它支配着两个旧点。Bob要么使用第三种颜色（这样我们就完成了），要么使用一种旧颜色。在不失一般性的情况下，这个旧颜色可以选择为1。然后Alice添加第四个点，该点仅支配着色为1的最小点之一。这显然迫使Bob在此时使用第三种颜色。很容易检查给出的偏序集的宽度是2，并且它是区间。这个构造可以扩展得到我们的定理如下。首先，反链A ={a1，...，一个w= 2 n的元素被呈现给Bob，所以他被迫在它们上使用w不同的颜色。然后爱丽丝用n个新点的反链B = b1，...，b n支配所有点A.鲍勃可以用新颜色或旧颜色给B上色。设k是B的旧颜色的number，设A1={ai∈A：存在与ai相同颜色的bj∈B}.以来|的1|= k≤n存在一个n元集合AJ1使得A1<$AJ1<$A.这使得Alice有可能提出n个新点的反链C ={c1，...，Cn}使得

下载后可阅读完整内容，剩余1页未读，立即下载