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

摘要

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

目录

声明

摘要

第1章绪论

1．1调度问题的概述

1．2算法设计与分析

1．3雷达传输系统中的相关调度问题简介

1．4论文结构

第2章单机环境下两阶段间加工具有延迟且时间相同的调度问题

2．1 引言

2．2符号定义

2．3 1 |exactlj，aj=bj|Cmax的算法设计

2．4 1 |exactlj，aj=bj|Cmax的算法分析

2．5 1 |exactlj，aj=bj|Cmax特殊情况下的数值计算分析

2．6本章小结

第3章单机环境下两阶段间加工具有延迟的调度问题

3．1 引言

3．2符号定义

3．3问题的整数规划模型

3．4 1 |exactlj|Cmax的若干性质分析

3．5禁忌搜索算法设计

3．5．1编码方法

3．5．2解码方法

3．5．3初始解的设计

3．5．4禁忌表以及选择策略的设计

3．5．5算法的具体描述

3．6数值模拟及其结果分析

3．7本章小结

第4章总结与展望

参考文献

附录

致谢