文摘
本文探讨一种单机two-agent调度问题最小化最大成本与位置相关的工作。有两个代理,每一组独立工作,竞争一个常见的机器上执行他们的工作。在我们的调度设置,一份工作的实际位置相关处理时间的特点是变量函数依赖在序列的位置工作。每个代理希望实现自己的最大成本最小化的目标工作。我们开发一个可行的方法来实现帕累托最优在多项式时间点。
1。介绍
调度理论是非常有用的在工业应用和在现实世界中提供了很多指导。传统的调度问题只有一个代理来优化自己的目标。随着现代科技的发展,越来越多的调度模型。进入21世纪后,现有的一个代理调度模型不能满足的要求。特别是在大数据时代,互联网必须处理各种指令的在线网络公民和会见不同的偏好。在这样的环境中,可替换主体调度模型出现。的终极理论结果可替换主体调度问题是所有帕累托最优点。这样的问题通常称为帕累托优化问题(PP)。自帕累托优化问题很难处理大量的调度模型,研究人员考虑有些弱调度问题简略调度问题,即优化一个代理的目的与其他代理的目标的限制。这样的问题约束优化问题(简称CP)。在现实中,CP问题的解决会更有利于PP的解决问题。有很多论文的最终决议页问题取决于CP问题的研究成果;(1)是一种最杰出的和有益的论文。
可替换主体问题,two-agent问题显然是最简单和最具代表性。Agnetis et al。1)首先定义两个问题two-agent调度模型和研究two-agent调度问题打开了大门。贝克和史密斯(2)处理two-agent调度问题,结合成一个单一的两个代理的两个目标的目标。和方法也可以获得所有帕累托最优分某些条件。元等。3]指出一些动态编程设计的缺点在2)和发展正确的方法。Biskup [4)首次引入位置相关处理时间经典调度模型和开发最优算法考虑的问题。此外,Mosheiov [5)扩展到更多的调度问题,包括单机问题,多准则问题,平行机台的问题。巴赫曼和Janiak考虑一些特殊位置相关调度问题,并证明了它是np难的强烈。但遗憾,证明不完整,缺乏一些地方的关键语句。Janiak和尤夫6)补充的关键语句,提供了一种新的完整的证明。王,夏7和王8)考虑位置相关处理时间在一些流水车间调度问题。阴et al。9广义的位置相关功能处理时间和一些理论结果出现在[4,5]。杨(10)同时考虑就业恶化和位置相关维护恶化环境下学习效果和分析一些单机调度模型的结果。Biskup [11)给一个优秀的调度理论的回顾与学习效果。刘等人。12]最初引入two-agent位置相关调度问题的模型。他们研究了单机two-agent CP调度问题中,一个代理要最小化完工时间的最大总成本的其他代理界一个常数,在乔布斯的实际加工时间是由线性函数依赖他们的位置安排。此外,广域网(13)深化的结果和显示页的版本12可以用多项式来解决。更多相关的论文,我们将阴et al。14- - - - - -16]。
在本文中,我们研究了two-agent页调度模型中引入[12,13]。两个代理的目标,双方都想减少工作的最大成本。我们开发一个多项式时间算法表明,PP可以有效解决的问题。部分2提供了一些符号和问题描述。研制了一种多项式时间算法显示页的问题是可以解决的3。
2。符号和问题陈述
有两个代理,代理和代理,安排各自的工作在一个共同的单一机器。代理的工作集和是和分别在哪里和代理的工作的数量吗和,分别。正常的处理时间用,,。每一份工作不减少的和非负成本函数定义完成时间。让和。为一个可行的时间表,下面的三个条件。(我)第一份工作是在时刻0处理。(2)的处理工作不重叠。(3)这台机器的工作过程没有空闲时间。
的条件下,任何安排与序列是一致的。通常,我们让表示的序列,以及一致的时间表。让表示的实际处理时间的工作在位置,,在那里代表了可变传动比。我们假设如果是负的实际处理时间以免一些工作是负的一些可行的时间表,在哪里。给定一个序列工作的完成时间用。工作的成本等于。因此,代理人的成本被定义为的最大成本工作;也就是说,,。对任何工作,我们定义的完成时间用上一份工作的完成时间。如果没有困惑,,,是缩写,,,分别。对于任意两个可行的时间表和,我们叫帕累托改善比当且仅当和至少一个严格不等式成立。被称为帕累托最优如果没有安排帕累托比。和是一个帕累托最优点。目标是找到所有的帕累托最优点。采用的符号1可以用),页的问题。对任何工作,让。此外,如果,然后。
引理1(见[13])。让是一套可行的安排工作;然后。
从引理1,我们知道的完成时间不依赖于工作的处理顺序的。
让是一对多;我们考虑的问题≤。的一对,我们定义产生的到期日期是与和,;。让EDD是我们的安排顺序的工作在不减少的订单产生的到期日期和安排(工作后(工作打破了领带如果它存在。类似的证明EDD规则(17),我们可以得到下面的引理。
引理2。如果问题是可行的,然后安排EDD是一个可行的时间表。
3所示。主要的结果
在本节中,我们将描述我们的算法显示页的问题可以解决的。首先,我们设计一个算法来解决这个问题问题对于任何给定的绑定。
算法 。对问题。
步骤0。初始化,,,,。
步骤1。计算当前的完成时间。
步骤2。如果和,然后停止并返回值。
步骤3。如果和,让的设置(工作的与成本。如果,然后停止并返回不可行。否则,任意选择一个工作的和进度工作在位置,,,,转到步骤1。
步骤4。如果和,我们选择一个工作的这和进度在位置,,转到步骤1。
步骤5。如果和,让的设置(工作的与成本。如果,然后选择一个工作的这和进度在位置,,,,,转到步骤1。否则,任意选择一个工作的和进度工作在位置,,,,转到步骤1。
我们可以应用算法问题只有通过交换身份的代理和代理。
定理3。算法解决问题正确。
证明。假设是导致序列通过应用算法问题。让是一个最优序列的问题;我们只需要证明。让是这样的工作,;我们表示之前的工作工作在包括工作。让是最后的工作安排在;我们表示的一组工作前的工作在包括工作通过。和。根据算法,对于每一个工作,我们有。自,。此外,必须是一个工作。通过该算法,我们知道。所以 我们完成了证明。
在下面,我们国家非常受欢迎的方法得到帕累托最优的问题。该方法首次开发(18),然后应用于(1,19,20.]。
算法 。对问题。
步骤0。调用算法来。如果算法返回不可行,然后让算法停止并返回不可行。否则让是返回值。调用算法来,让返回值,那么我们停止算法并返回。
定理4。算法返回一个帕累托最优与。此外,如果也是一个帕累托最优点,然后和。
为每一个时间表,我们定义指标函数如下: 在这里意味着是之前在反之亦然。此外,我们组。
引理5。对于任意两个帕累托最优点和,只有在和。
证明。由于成本函数的工作不减少的,,我们有对于任何工作,和对于任何工作,。因此, 请注意,和帕累托最优的两点;我们有和,。让是这样一个工作,这意味着;我们表示之前工作的一组工作在包括工作通过: 让是最后的工作安排在之前,我们表示一组的工作工作在包括工作通过:和。由(4), 这意味着不是一个工作,而是一个工作。我们表示工作的;然后 因此, 我们完成了证明。
算法 。对问题。
步骤0。初始化,。
步骤1。调用算法对问题。
步骤2。如果算法返回不可行,那么我们停止和帕累托最优输出点。否则,让从算法导致的时间表;集,,。步骤1。
定理6。算法返回所有帕累托最优的问题在。
证明。很明显,算法返回所有帕累托最优点。然后,我们分析了算法的复杂性。请注意,算法可以实现在;算法也可以实现吗。对于任何可行的时间表,。因此,由引理5,有最多的算法的实现在算法的运行。此外,我们还可以得到算法可以在完成。
利益冲突
作者宣称没有利益冲突有关的出版。
确认
这项工作是自然科学基金(批准号江西省20142 bab211017)和学校课题(批准号江西财经大学06162015)。