连续型资源约束与最优资源分配排序问题-论文.pdf

《连续型资源约束与最优资源分配排序问题-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第30卷第2期(2014)河西学院学报Vo1．30No．2(2014)连续型资源约束与最优资源分配排序问题张忠文(甘肃中医学院公共课部，甘肃兰州730000)摘要：本文重点研究了形如liP，=(“)，∑“，chainsI’fcf型在链不可中断的，=1⋯情况下连续型问题的算法及其算法复杂性，分别讨论了P，=／(甜，)是线性函数、非线性函数的情况，给出了最优排序和最优资源分配及其稳定点的定义，同时证明了由此所求出的资源分配水确系最优资源分配．关键词：连续型；最优资源分配；最优排序；算法复杂性；链不可中断；下降算法；稳

2、定点中图分类号：022文献标识码：A文章编号：1672—0520(2014)02—0032—091模型描述在连续型资源约束resourcecons~ained)排序问题中，资源是不可再生(nonrenewable)的，任务的加工时间依赖于分配给它的资源，即任务的加工时间是它所得到的资源量的函数．文章只讨论含有单处理机链不可中断的连续型资源约束排序问题．设被加工的任务集为={，，⋯，)，用Graham三元组法表示，这类问题可描述为：lIPj=fj(u∑“-

3、任务的资源分配量，U是不可更新的资源总量．是任务的加工时间，C，是任务．的完工时间，w，是对应的权重，该问题的目标函数是加权总完工时间．对于任务集T={，，⋯，)，用Z：(Z1，z2，z3，⋯，)表示任务的下标集，由一个下标集可以确定任务的一个可行排列，用Z表示所有可行排列的集合，满足资源约束的资源分配向量记为U=(u1，u2，⋯，Un)，所有资源分配向量集记为．问题的一个解可以记作(z，U)∈Z×U．用表示目标函数，(z，)的值记作(z，)，其最优解记作(z，U)，Z‘表示最优任务排序，求解问题1．1实际上是找

4、向量(z，材)∈Z×U，使目标函数w，c，达到最小．对任意的下标排列．z∈Z，文献[14]所给的算法能求出相应于这个下标排列的最优资源分配．其算法复杂性为O(nlogn)，在前人研究的基础上，重点提出并讨论了p，=／，)是线性函数、非线性函数的情况，给出了最优排序和最优资源分配及其稳定点的定义，同时证明了由此所求出的资源分配U木确系最优资源分配．收稿日期：2013—06—20作者简介：张忠文(1974一)，男，甘肃民勤人，讲师，从事运筹学与排序研究工作·32·张忠文：连续型资源约束与最优资源分配排序问题如果2链不

5、可中断的情况定义1．1链不可中断是指：一旦∑加卢工一一∑某尸个链，就必须加工完该链的所有任务，然后再加工另一个链的任务．—p定义1．2设>：C，为对应于给定下标排列z∈z的最优资源分配∑时的最优目标函数值，木是x,-t~Tz母∈z的最优资源分配，如果对一切z∈Z，且满足定义1．1的条件，有∑。∈∑，，，∑则称(z宰，木)为问题1．1的最优解．=一A—引理1．1对于问题1Iprec，P，=一aju，∑，ehainslCm+，在链不可中断的情况下，=++，则由任务，，⋯，组成+的链在由任务+l，+，⋯组成的链之++前

6、加工．证明在顺序7r[，‘，2，⋯，，+：，⋯，]下，加∑权总完工时间等∑于+++而在顺序71-r[+：，⋯，，，，⋯，】下，加权总完工∑时间等于∑++++k+k∑两式相减得：(∑)一C)，=(∑)(∑)一(I2p∑)．j=lj=k+lj=k+lj=l∑在假设的条件下，上式右端的值小于零，故(∑)<(∑)，．证明完毕．3算法及算例分析我们首先讨论问题11prec，P=-ajuj∑U，chainsI．=l设z∈Z是任意一个优先约束可行的下标排列，不妨设z=I1，2，⋯，nl，用下边的算法可求出对应于这个排列的最优资

7、源分配．算法(1．1)[14]对j=l，2，⋯，n，置：=0．(1)求∈T，使a=max，『)．一^A^、(2)置U^：=min{u，U)，U：=U-U母，T：=T-I}(3)如果T≠，而且>0，转(2)，否则停止计算．显然算法复杂性为O(nlogn)．定理1．1[t]对任意的可行下标排列z，算法3．1所得到的(，木)是问题(1．1)的最优解．证明对任意的可行下标排列z，都有·33·河西学院学报2014年第2期Cm=P1+P2+⋯+P=∑(一，甜)=1=∑一∑u．(1．2)=lj=l算法1·1把资源优先分配给aj

8、大的任务，从1．2式日】以看出算法1．1得到的U宰是最优资源分配．下面我们重点讨论：形如11Pj===一ajuj，chainslC的最优资源分配与排序问题．m定理1．2对任意的可行下标排列z，当函数===()：=：一，且()在z，c[O，mj1(=√)连续非减时，由算法1．1所得到的(z木，zf水)仍然是问题1．1的最优解．证明对任意的可行下标排列z，都有=PI+P，+⋯