雷达传输系统中的相关调度问题的算法设计与分析

发布时间：2020-03-23 18:53

【摘要】：本文主要研究一类源于雷达传输系统中的调度问题。研究了问题的一般情况和特殊情况下的两个模型。研究的核心是问题的近似算法和启发式算法设计和分析。全文共分为四章,具体如下。第一章主要简单介绍了调度问题的基本概念和雷达传输系统中相关的调度问题的问题背景和研究现状,并抽象得到两个本文具体需要研究的调度问题。第二章主要研究单机环境下两阶段间加工具有延迟且时间相同的调度问题。在该问题中,工件需要在一台机器上进行加工,工件的加工需要经历两个阶段,阶段与阶段之间具有一个精确的延迟时间,即延迟时间结束工件必须让第二阶段加工。同时我们考虑工件第一阶段的加工时间等于第二阶段的加工时间,目标函数为极小化最大完工时间,用三参数可以表示为1 |exactl_j,a_j=b_j| C_(max)。首先针对问题的部分特殊情况,设计了相应的改进近似算法,给出问题的性质以及不同情况下算法的最坏情况界证明。对部分特殊情形进行了数值模拟分析,说明本文提出的改进算法的有效性。第三章主要研究单机环境下两阶段间加工具有延迟的调度问题。与前一章不同,本章研究的是问题的一般情形,即不需求工件两阶段具有相同的时间,用三参数可以表示为1|exactl_j|C_(max)。首先给出问题1|exactl_j|C_(max)的整数规划模型。其次分析并得到该问题最优解的多个性质,并进行证明。根据问题最优解的性质设计并改进了禁忌搜索算法,用禁忌搜索算法求解该问题。在禁忌搜索算法的设计中,我们充分运用了问题最优解性质来设计禁忌表,设计编码和解码规则,从而保证解质量的同时,大大加快算法的收敛速度。大量多角度的数值模拟实验和对比,说明本文设计的算法具有较好的性能。第四章主要给出了本文的总结与展望。
【图文】：

分块,加工示意图,算法解,工件

中的工件均满足第二段阶段连续加工（如下图2.1（a））。当工件无法按照第二段加工过程连续加工的方式放置在该分块中时，则将该工件作为下一个分块的起始工件。最终，根据上述过程可将所有的工件构建出个分块，分块与分块之间连续进行加工，，其分块的总长度构成了最终算法解。（如下图2.1 （b）当构建出5个分块的情形）根据算法，其每个分块的大小可表示为： = + + +1 1∑ = ，其算法解假设由个分块构成，则其算法解为： max( ) = ∑ =1 = ∑ =1( + + +1 1∑ = )，6

示意图,工件,示意图,完成时间

+ 1两个工件构成，如下图2.3(a)。设工件 + 满足 + ≥ + 1∑ = ，并将工件 + 放入分块中仅保证其 + 紧接在前一个工件的 + 1之后，如下图2.3(b)。下分析工件 + 的 + 是否与其他工件有重叠。图 2.3: 工件与工件 + 1排序示意图此时 + 开始时间和完成时间别为：8
【学位授予单位】：浙江理工大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TN95;TP301.6

【相似文献】