星地一体成像侦察任务规划组合求解方法

成像侦察任务流的航天资源任务规划问题是将有限的航天资源分配给需要侦察的不同目标,最大化满足任务需求.采取了星地一体任务规划思路进行问题建模与求解.提出星地一体虚拟资源聚合模型和算法,并在此基础上,给出了星地一体的虚拟资源冲突检测与消解方法,提出了星地一体任务规划模型的模型分解与组合求解方法,针对分解后的主问题模型给出了一种适应可变冲突约束的遗传算法;针对子问题模型给出了一种基于时间序列排序的任务调度方法,并对上述两种算法进行了设计与实现;最后,结合试验案例进行验证.     

采用组合优化策略的电子侦察卫星规划方法

对电子侦察卫星任务规划问题进行了分析,建立了问题的多目标规划模型;设计了一种基于带后优化过程MOEO(Multi-objective Extremal Optimization)的多目标规划算法对模型进行求解,该算法包含MOEO主算法过程和基于禁忌搜索(TS)的后优化过程两部分:MOEO主算法中采用插入变异、模式变异及删除变异等算子对解空间进行搜索,基于Pareto最优概念的解排序确保了解在多个目标上的有效优化,精英策略避免了丢失进化过程中产生的非劣解;TS后优化过程中提出了多种邻域结构,使用各种邻域算子或算子的组合,对主算法Pareto最优解进一步优化,以得到更好的解。最后给出了仿真实例证明本文模型及算法对解决电子侦察卫星任务规划问题的有效性。     

侦察卫星探测资源调度研究

侦察卫星探测资源调度是一类基于约束满足的优化问题。对卫星探测资源和探测任务的特点进行分析,在此基础上构建卫星探测资源调度的目标函数和约束条件,利用约束满足问题的建模思想对该调度问题进行建模。针对约束满足模型规模大、求解复杂的情况,结合卫星探测资源调度问题的特征,提出一种基于启发式禁忌搜索算法的模型求解方法,并通过仿真算例进行说明与分析。该调度模型和算法充分考虑了星载资源与对应任务的特点,尽量回避假设与简化条件的提出,具有较好的适用性,将为侦察与预警卫星网络任务规划与资源调度的研究奠定基础。     

电子侦察卫星动态调度问题的快速启发式算法

卫星电子侦察中针对动态突发事件重新制定侦察计划是侦察任务规划所要解决的基本问题.分析导致动态调度的扰动因素,把不同扰动下的动态调度问题归结为一类复杂约束下的任务插入问题.建立混合整数规划模型,提出快速启发式任务插入算法(含三个基本算法--直接插入任务算法、移位插入任务算法和替换插入任务算法);基于初始调度方案的优良特性,极大降低动态调度复杂性.仿真实验表明:该算法能有效解决电子侦察卫星动态调度问题.     

基于RGI的浮空器任务规划问题研究

侦察任务规划是浮空器军事应用中的重要问题,对于最大化满足侦察任务需求、提高浮空器资源利用率具有重要作用。针对浮空器侦察系统的任务规划问题,考虑任务需求约束、载荷约束等条件下,构建了浮空器连续侦察监视的混合整数规划模型,并采用贪婪随机插入(RGI)算法对模型进行了求解。该算法结合了贪婪算法和模拟退火算法的设计思想,既保留了一定贪婪特征又提高了跳出局部最优解的能力。最后通过一个多浮空器多目标的仿真实例验证了算法的有效性。     

帝国竞争算法在无人机三维航线规划中的应用研究

针对实际飞行环境中无人机的三维航线规划问题,提出了一种创新启发式优化算法——牛顿帝国主义竞争算法(NICA,Newtonian imperialist competitive algorithm).该算法能够根据无人机的飞行轨迹,从起始位置到任务目标位置生成平滑的航线路径,约束航线规划,使得目标完成任务的时间最小化.该算法也能为无人机在真实地形上的航线提供最佳轨迹路径.最后通过与ICA、GA和PSO算法进行比较,验证了改进算法的有效性.结果表明:改进帝国算法提高了全局最优解的搜索能力,在收敛速度和精度上优于其他3种算法,适合用来解决无人机的三维航线规划问题.     

航班滑行路径规划和停机位分配联合优化

针对机场的航班滑行路径规划和停机位分配的联合优化调度问题,构建基于冲突回避的滑行道与停机位联合调度模型,并提出改进的自适应差分进化算法求解问题.以最小化航班的滑行时间和旅客转机的行走时间为优化目标,建立非线性混合整数规划联合调度模型.设计考虑了滑行冲突的路径规划算法,完成航班的滑行路径分配,并通过自适应动态调整差分进化...     

启发式列生成算法求解带恶化效应的同构并行机调度问题

针对实际生产中广泛存在的一类带恶化效应的同构并行机调度问题,以最小化最大完工时间为优化目标,构建该问题的整数规划模型,并提出一种启发式列生成算法(HCGA)进行求解.在HCGA中,首先,利用Dantzig-Wolfe分解方法,将原问题分解为一个主问题(MP)和多个子问题;然后,设计启发式算法获得初始列,其中每列为一台机器上的一个调度方案,基于初始列构建限制主问题(RMP)模型;接着,设计快速有效的动态规划算法求解子问题,以得到需添加至RMP的列集,同时,考虑传统列生成算法收敛速度较慢,设计一系列方法来加速列生成过程;最后,基于所获取的MP线性松弛解,设计深潜启发式算法确定原问题的整数解.HCGA与商用求解器GUROBI的对比实验结果表明,HCGA可在较短时间内获得更优的解.     

面向多星任务规划问题的改进遗传算法

卫星数量的快速增加为管控卫星的工作增加了很大的难度,如何有效地进行任务规划,有效管理卫星资源,成为了卫星领域的一个重要问题.针对此问题,本文构建了多星任务规划的数学模型,将最大化任务收益作为优化目标.本文分析了问题的难点并提出了一种包含两种优化策略的改进遗传算法,包括全局优化和局部优化两部分.全局优化和局部优化根据种群改进情况进行自适应切换.通过两种优化方法的结合可以提升任务规划的效果.本文还提出了一种任务规划算法,用于为改进遗传算法得到的任务序列选择合适的任务执行时间.仿真实验证明本文提出的改进遗传算法可以很好地解决多星任务规划问题,与对比算法相比可以得到更优的规划结果.改进遗传算法有很好的工程应用前景.     

基于GA的电子侦察卫星任务规划问题研究

电子侦察卫星是现代战争中获取电子情报的重要手段,在快速作战决策方面具有独特的作用.电子侦察卫星任务规划问题是一类重要的任务规划问题,涉及各种复杂的约束条件.首先通过对电子侦察卫星工作原理的分析提出了基本假设和预处理的基本方法,并建立了CSP模型,然后采用遗传算法(GA)对模型进行求解.算法针对电子侦察卫星任务规划的特点设计了符号型编码以及相应的OBC交叉算子及多点交换变异算子.最后采用所设计的遗传算法和简单贪婪算法分别对不同规模的问题进行了求解,实验结果表明算法有效地解决了针对固定目标的电子卫星侦察任务规划问题.     

Two-machine flowshop scheduling with bicriteria problem

This paper attempts to solve a two-machine flowshop bicriteria scheduling problem with release dates for the jobs, in which the objective function is to minimize a weighed sum of total flow time and makespan. To tackle this scheduling problem, an integer programming model with N²+3N variables and 5N constraints where N is the number of jobs, is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, a heuristic scheduling algorithm is presented. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. The average solution quality of the heuristic algorithm is above 99% and is much better than that of the SPT rule as a benchmark. A 15-job case requires only 0.018 s, on average, to obtain an ultimate or even optimal solution. The heuristic scheduling algorithm is a more practical approach to real world applications than the integer programming model.     

A note on a single-machine lot scheduling problem with indivisible orders

In this paper, a lot scheduling problem on a single machine with indivisible orders is studied. The objective is to minimize the total completion time of all orders. We show that the problem is NP-hard in the strong sense. Then, a binary integer programming approach and four simple heuristics are proposed to solve the problem. The binary integer programming approach with running time limit is considered as one heuristic method. As compared to a lower bound, the average performances of the heuristic method are really good and better than those of the four simple heuristics.     

Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties

The present paper studies the single machine, no-idle-time scheduling problem with a weighted quadratic earliness and tardiness objective. We investigate the relationship between this problem and the assignment problem, and we derive two lower bounds and several heuristic procedures based on this relationship. Furthermore, the applicability of the time-indexed integer programming formulation is investigated. The results of a computational experiment on a set of randomly generated instances show (1) the high-quality results of the proposed heuristics, (2) the low optimality gap of one of the proposed lower bounds and (3) the applicability of the integer programming formulation to small and medium size cases of the problem.     

Single machine stochastic scheduling to minimize the expected number of tardy jobs using mathematical programming models

This paper studies the single machine scheduling problem for the objective of minimizing the expected number of tardy jobs. Jobs have normally distributed processing times and a common deterministic due date. We develop new approaches for this problem that generate near optimal solutions. The original stochastic problem is transformed into a non-linear integer programming model and its relaxations. Computational study validates their effectiveness by comparison with optimal solutions.     

Exact and heuristic algorithms for the just-in-time scheduling problem in a batch processing system

Batch processing systems are commonly used in many different environments such as chemical and semiconductor industries. In this research, a just-in-time scheduling problem in a batch processing system is investigated. Minimization of total earliness and tardiness of the jobs with respect to a common due date is considered as the objective function. First, the research problem is formulated as a mixed integer linear programming model. Then, to find the optimal schedule for a predetermined set of batches, a dynamic programming algorithm is proposed. Based on the proposed dynamic programming algorithm, several heuristics are also developed. A lower bounding method is presented, and then a branch and bound algorithm is proposed to solve the problem optimally. To demonstrate the performance of the proposed algorithms, several computational experiments are conducted.     

基于整数线性规划的VLIW DSP指令分簇调度

在分簇VLIW DSP上,指令分簇是一项对程序性能有重要影响的编译优化,但现有的指令分簇算法只能处理顺序的程序区域,且难以获得最佳的分簇方案。针对这些问题,提出一种基于整数线性规划的统一指令分簇与指令调度的方法。该方法使用零一决策变量表示函数中指令的分簇、指令的局部调度以及簇间传输指令的全局调度,并将指令之间的依赖关系和对处理器资源的竞争关系构造为线性约束,最终得到一个以最小化函数的估计执行时间为目标的整数线性规划模型。实验结果表明,求解该模型得到的分簇调度方案对程序性能的优化显著强于现有算法,并且求解模型所耗费的时间是可接受的。     

Minimizing maximum tardiness and delivery costs in a batched delivery system

High delivery costs usually urge manufacturers to dispatch their jobs in batches. However, dispatching the jobs in batches can have profound negative effects on important scheduling objective functions such as minimizing maximum tardiness. This paper considers a single machine scheduling problem with the aim of minimizing the maximum tardiness and delivery costs in a single-machine scheduling problem with batched delivery system. A mathematical model is developed for this problem which can serve to solve it with the help of a commercial solver. However, due to the fact that this model happens to be a mixed integer nonlinear programming model the solver cannot guarantee to reach the global solution. For this reason, a branch and bound algorithm (B&B) is presented to obtain the global solution. Besides, a heuristic algorithm for calculation of the initial upper bound is introduced. Computational results show that the algorithm can be beneficial for solving this problem, especially for large size instances.     

成组加工中有主从调整时间的最大延迟问题

针对钢管生产过程具有多产品和主从调整时间特性的实际批组调度问题,以最小化工件的最大延迟为目标函数,建立了问题的0-1混合整数规划模型;进而分析了问题的优化特性,提出了基于优化特性的禁忌搜索算法.仿真结果表明该算法是可行而有效的.     

A tabu search approach to the truck scheduling problem with multiple docks and time windows

While organizing the cross-docking operations, cross-dock managers are confronted with many decision problems. One of these problems is the truck scheduling problem. This paper presents a truck scheduling problem that is concerned with both inbound and outbound trucks at multiple dock doors. The objective is to minimize the total travel time and the total tardiness. The truck scheduling problem under study is described in detail and a mathematical model of the problem is provided which can be solved to optimality with a mixed integer programming solver, at the expense of a high computation time. Next, a tabu search approach is presented. Experimental results on new benchmark instances indicate that the proposed tabu search is able to find good quality results in a short time period, thus offering potential for integration in cross-docking decision support systems.     

Minimizing costs in round robin tournaments with place constraints

In this paper we consider a general sports league scheduling problem and propose solution algorithms for it. The objective is to find a feasible schedule for a round robin tournament with minimum number of breaks and minimum total costs where additionally place constraints are taken into account. We present a “first-break, then-schedule” approach which uses an enumerative procedure to generate home-away patterns and integer programming for finding corresponding schedules. Computational results are presented for leagues with up to 14 teams.