几种最优资源分配与排序问题-研究

《几种最优资源分配与排序问题-研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、关于学位论文使用授权的声明本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定，同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版，允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相关的学术论文或成果时，第一署名单位仍然为兰州大学。保密论文在解密后应遵守此规定。论文作者签名：导师签名：擞日期；立型：±

2、：!兰州大学2007届硕士学位论文第一章引言排序问题是一类组合最优化问题，求解排序问题的基本思路是：应用或借鉴求解其它组合最优化闯题的方法，充分利用排序问题本身的特殊性质，以确定满足约束条件的最优排序。有些排序问题可直接转化成其它的组合最优化问题求解。对具有多项式算法的排序问题，要尽可能地找出空间复杂性和时间复杂性好的算法，所谓空间复杂性是算法所占存储的多少，时间复杂性指的是计算时间的长短，它们都是输入规模的函数，本文主要考虑时间复杂。性对于还不知道是否有多项式算法的排序问题，首先要用复杂性理论进行

3、分析，看它是否是NP—难的，求解这类问题有两种基本方法：一是用分枝定界法、动态规划等巧妙的穷举法求出它的精确最优排序，这类算法计算量大，只有对规模较小的问题才是可行的；另一种方法是求出它的近似最优排序，各种局部搜索法和启发式算法都是很有效的，这类算法计算量小，并能满足一定的实际需要，为了知道所德到的近似最优排序与最优排序的近似程度，分析误差界是使用这类方法不可缺少的工作，．也是比较困难的工作。本文所讨论的是一类比较复杂的排序问题，在这类问题中，当处理任务或作业时，除需要处理机以外，还需要另外的附加资

4、源，我们把这一类排序问题称为资源约束(resourceconstrained)排序问题。资源可分为可再生(renewable)的和不可再生(nonrenewable)的两种，可再生资源指的是它在任意时刻的临时可用性受到约束，也就是说这类资源被使用它的任务释放后还可以再次被使用，不可再生资源指的是它的一次可用性，这种资源被某个任务使用以后，在任何时刻都不能分配给其它任务，如果资源的临时可用性和一次可用性都受到限制，称它为双重约束(doublyconstrained)资源。从可分性的角度来看，资源又分为

5、离散(discretely-divisible)资源和连续(continuous—divisible)资源，离散资源能从有限个可能的分配量中选择一种量分配给任务，而连续资源以任意小于或等于某个给定值的量分配给任务。排序(scheduling)问题是利用一些处理机(processor)、机器(machine)和资源(resource)，找出最优地完成一批给定的任务(task)或作业(job)的方案或调兰捕大学2007届硕士学位论文度，在执行这些任务或作业时需要满足某些条件，如任务的到达时间、完工的限定

6、时问、任务的加工顺序、资源对加工时阀的影响等，最优的完成是指使目标函数达到最小，目标函数通常是指加工时间的长短，如最大完工时间、处理机的利用率、时间表长、最大延误、加权误工任务数等。排序问题产生的实际背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域。小到普通的生产部门的计划安排、人员调度、学校课程表的制定，大到宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论和算法。近年来，排序总是受到广泛的关注，国内外广大学者将其研究成果不断地应用于各种生产与服务行业当中，并产生了巨大的经济

7、效益。处理机、任务和目标函数三要素组成了排序问题。处理机的数量、类型和环境有近十种情况，任务或作业和资源的约束条件更是错综复杂，再加上度量不同指标的目标函数，形成了种类繁多的排序类型。一般用Graham等人在[9]中首先使用的三元组来描述排序问题的类型，这样大大简化了排序问题的表示．三元组记号由三域组成：a俐7其中n域表示处理机的数量、类型和环境。卢域表示任务或作业的性质、加工要求和限制，资源种类、数量和对加工的影响等约束条件。1域表示要优化的目标函数。对于资源约束型排序问题，我们假设有s种附加资源

8、R={足，足，⋯匙}它们的数量为h=仉，如，⋯％)其中．i5}是第f种资源玛的数量，每个任务在处理机上执行时需要一定数量的各种资源五(乃)=(墨(弓)，恐(乃)，⋯E(弓))，21，2，⋯力其中矗够)(o≤碍何)≤岛，z=l，2，⋯$表示任务乃需要第f种资源局的单位数量。在这一类资源约束排序问题中，口域中用来描述资源约束的项为r黜Aap，其中res表示资源受限，A，6,p分别表示资源的种类、数量和任务对资源的需求。2兰州大学2007届硕士学位论文本文所研究的问题除形如