欢迎来到天天文库
浏览记录
ID:55643247
大小:278.78 KB
页数:9页
时间:2020-05-22
《连续型资源约束与最优资源分配排序问题-论文.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,+⋯
此文档下载收益归作者所有