资源描述：
《外文文献及中文翻译-scheduling parallel jobs with timeresource tradeoff via nonlinear programming本科学位论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、通过非线性规划调度有时间-资源权衡的并行工作AlexanderGrigoriev,MarcUetz马斯特里赫特大学、数量经济学,P.O.Box616，6200MDMaastricht,荷兰{a.grigoriev@ke.unimaas.nlm.uetz@ke.unimaas.nl},我们考虑到一个调度问题的任何工作的加工时间是依赖于使用离散的可再生资源,例如:人员。一定数量的k单位资源分配到在任何时候的工作,分配给一份工作的资源越多,处理时间越小。这样做的目的是找到一种资源配置和时间表,最大限度地减少了最大完工时间。我们确实需要简洁地未编码的时间-资源权衡函数,它需要的是未被使用
2、过数学规划技术。利用一种(非线性)整数数学程式,我们用性能约束(3+ɛ),ɛ>0为调度问题取得第一个多项式时间的近似算法。我们的方法依赖于一个完全多项式时间近似方案来解决数学规划松弛。这一结果本身是令人感兴趣的,因为我们同时也表明,潜在的数学规划是一个np难问题来解决。我们也获得的近似下界。关键词:调度;数学规划;近似算法,计算复杂度概述:1、简介和相关工作考虑一个调度问题n个工作j∈V需要在m个并行机器上处理。每个工作致力于得到处理一个确切的机器。有一个可再生资源,如离散人员,可以分配到工作以减少他们的加工要求。我们假设之间的利弊权衡使用的资源和由此产生的加工要求的工作j都可以
3、描述为一些非负时间-资源权衡功能(·)意味着,当x资源分派工作j,其加工要求成为(x)。在任何时间点,只有k单位资源是可用的。我们可以推断时间-资源权衡(·):{0,1,…,k}!首先得到是产生积极的作用。一旦资源已经被分配到工作,如果它不消耗更多的比目前k单位的资源在任何时间,42时间表被称为可行的。目标是找到一个资源配置和相应的可行的时间表,最大限度地减少了最大完工时间,也就是说,这工作的完成时间,完成交货。这个问题描述典型情况,在那里额外生产的物流资源,如人员,可以被利用,以降低生产周期时间。作为一个事实,一个不可再生资源调度问题,如全面预算约束,在文学界作为time-co
4、st权衡问题受到了很多人的注意,例如,[2、12、13、22条、23条]。令人惊讶的是,在相应的问题,一种可再生资源,如人员的约束,虽然从一个实际的观点他们不是缺乏吸引力,但受到的关注少。我们将把它们认为是时间-资源权衡问题,在类推到前者。相关工作文献[8]中,我们考虑过的更普遍的问题是不相干的机器排序问题和受资源约束的处理时间。在那里,工作都可以在任何机器加工,并且如果一个工作是原定于机器i,用s的机器的k可用资源的单位,处理时间是。假设处理时间在资源的非增加性,文献[8]证明了3.75-近似算法的存在性。该方法提出了基于线性规划松弛,使用nk变量。在本文中,然而,我们明确地允
5、许时间-资源权衡功能(·)可以被更简洁的编码。比如,如果这些函数是线性的,这个问题本质上是由输入的O(n)数字组成:每个工作,我们必须指定其机器i和两个整数系数和,这样就时间-资源权衡功能等式(x)=−x。因此,在文献[8]中的算法提出了一般不是多项式时间算法。在Grigorievetal.的一份受限制的版本的手边问题的演讲手稿[7]。他们假设额外资源是二进制的,那就是,任何工作都可以要么有或没有使用处理资源,减少了加工时间若资源被使用。最后,在论文中机器的数量m被认为是固定的,不是部分输入的。在那个问题上,他们衍生出一个近似(3+ɛ),并对这个问题和m=2个机器,他们获得NP-
6、hardness和一个完全多项式时间近似方案[7]。受资源约束的处理时间的调度工作也被称为可锻铸或可平行任务调度;例[11、18、19日,24]。在这些模型中,独立,对其采用非中断的工作可以被处理在一个或多个平行处理器,而且他们在处理器使用数量上用了更少的进程时间。任何处理器只能处理一个工作,目标是最小化最大完工时间的时间表。Tureketal[24]介绍了这个问题,他们获得2-近似算法。事实上,[24]中的模型与本文有联系但不同于本文。如果[24]42中并行处理器作为一个通用的必须分配工作的“资源”,当被限制用线性时间-资源权衡函数,[24]中的问题是这篇文章的问题的一个特例:
7、所对应的是这样的情形,n个工作被m=n个机器,而不是m
