STK/Scheduler在卫星数传调度中的应用研究

卫星数传调度问题是一类复杂的组合优化问题,即如何为卫星数传任务分配地面资源的问题,它是当前航天领域需要重点研究的问题之一.STK/Scheduler模块是STK工具包中的调度模块,对外提供了二次开发功能.针对卫星数传调度问题,研究了STK/Scheduler模块在该问题中的应用.首先在分析问题的基础上建立了卫星数传任务模型和调度模型,然后对基于STK/Scheduler的卫星数传调度系统进行了设计.最后利用AFIT基准数据进行了验证,结果表明在卫星数传任务规模不太大的情况下,TK/Scheduler为卫星数传调度问题的求解提供了一条捷径.     

一种排课问题的形式化描述体系和框架

排课问题主要解决时间和空间资源冲突,以优化教学资源和教学时间的分配,实现教学资源的负载均衡.提出一种新的排课约束的表述框架--时间地点限定表达式,可以通过形式推理缩减排课问题空间,支持基于案例和规则的排课问题求解.     

The optimal control approach to generalized multiprocessor scheduling

In this paper we present several new results in the theory of homogeneous multiprocessor scheduling. We start with some assumptions about the behavior of tasks, with associated precedence constraints, as processor power is applied. We assume that as more processors are applied to a task, the time taken to compute it decreases, yielding some speedup. Because of communication, synchronization, and task scheduling overhead, this speedup increases less than linearly with the number of processors applied. We also assume that the number of processors which can be assigned to a task is a continuous variable, with a view to exploiting continuous mathematics. The optimal scheduling problem is to determine the number of processors assigned to each task, and task sequencing, to minimize the finishing time.These assumptions allow us to recast the optimal scheduling problem in a form which can be addressed by optimal control theory. Various theorems can be proven which characterize the optimal scheduling solution. Most importantly, for the special case where the speedup function of each task isp , wherep is the amount of processing power applied to the task, we can directly solve our equations for the optimal solution. In this case, for task graphs formed from parallel and series connections, the solution can be derived by inspection. The solution can also be shown to be shortest path from the initial to the final state, as measured by anl _1/ distance metric, subject to obstacle constraints imposed by the precedence constraints.This research has been funded in part by the Advanced Research Project Agency monitored by ONR under Grant No. N00014-89-J-1489, in part by Draper Laboratory, in part by DARPA Contract No. N00014-87-K-0825, and in part by NSF Grant No. MIP-9012773. The first author is now with AT&T Bell Laboratories and the second author is with BBN Incorporated.     

Integrating intelligent job-scheduling into a real-world production-scheduling system

The paper addresses the problem of scheduling production orders (jobs). First, an approach based on simulated annealing and Hopfield nets is described. Since performance was unsatisfactory for real-world applications, we changed the problem representation and tuned the scheduling method, dropping features of the Hopfield net and retaining simulated annealing. Both computing time and solution quality were significantly improved. The scheduling method was then integrated into a software system for short-term production planning and control (electronic leitstand). The paper describes how real-world requirements are met, and how the scheduling method interacts with the leitstand's database and graphical representation of schedules.     

基于中间件的航电系统接口仿真通用软件设计

提出了一种基于”仿真软件＋中间件”的接15／仿真系统通用软件架构。开发了Interface_RTI中间件,使用XML文件作为系统配置文件,无需重新编译Interface_RTI中间件程序就可以支持在不同系统上的仿真运行,降低了软件维护成本。对仿真软件进行了合理的任务划分和优先级设置,减少了任务调度开销,保证了软件实时性。该软件能满足某型UAV航电系统的接口仿真功能、性能、通用性、可靠性及灵活性要求。     

A job grouping approach for planning container transfers at automated seaport container terminals

This paper proposes a practical job grouping approach, which aims to enhance the time related performance metrics of container transfers in the Patrick AutoStrad container terminal, located in Brisbane, Australia. It first formulates a mathematical model of the automated container transfers in a relatively complex environment. Apart from the consideration on collision avoidance of a fleet of large vehicles in a confined area, it also deals with many other difficult practical challenges such as the presence of multiple levels of container stacking and sequencing, variable container orientations, and vehicular dynamics that require finite acceleration and deceleration times. The proposed job grouping approach aims to improve the makespan of the schedule for yard jobs, while reducing straddle carrier waiting time by grouping jobs using a guiding function. The performance of the current sequential job allocation method and the proposed job grouping approach are evaluated and compared statistically using a pooled t-test for 30 randomly generated yard configurations. The experimental results show that the job grouping approach can effectively improve the schedule makespan and reduce the total straddle carrier waiting time.     

分布式系统多星故障诊断任务调度结构研究

多星故障诊断任务调度模型是构建多星任务调度系统的基础,提出分布式的多星故障诊断调度模型,将调度功能分为三个模块——监控模块、任务调度模块和服务器模块。将这些模块结合起来,便于实现多星的故障诊断,便于系统扩展、维护。以多星故障诊断任务调度的禁忌搜索算法为例,分析各模块之间的关系,为未来多星故障诊断任务划分提供了有力支撑。     

基于内容的网络集群负载平衡算法模型

在论述网络集群负载平衡算法的基础上,基于内容分类的方法,给出基于内容的网络集群负载平衡算法三元组模型。请求分类有利于提高缓存命中率,调度机制说明如何适当地转发请求,动态反馈避免将请求分配到重载的服务器,进而分析了调度机制的八种调度策略和六种基于内容的调度转发技术。该模型利用缓存内容来提高集群的吞吐量和响应时间,可部署多种服务类型。     

Algorithms for a realistic variant of flowshop scheduling

This paper deals with a realistic variant of flowshop scheduling, namely the hybrid flexible flowshop. A hybrid flowshop mixes the characteristics of regular flowshops and parallel machine problems by considering stages with parallel machines instead of having one single machine per stage. We also investigate the flexible version where stage skipping might occur, i.e., not all stages must be visited by all jobs. Lastly, we also consider job sequence dependent setup times per stage. The optimization criterion considered is makespan minimization. While many approaches for hybrid flowshops have been proposed, hybrid flexible flowshops have been rarely studied. The situation is even worse with the addition of sequence dependent setups. In this study, we propose two advanced algorithms that specifically deal with the flexible and setup characteristics of this problem. The first algorithm is a dynamic dispatching rule heuristic, and the second is an iterated local search metaheuristic. The proposed algorithms are evaluated by comparison against seven other high performing existing algorithms. The statistically sound results support the idea that the proposed algorithms are very competitive for the studied problem.     

Dispatching rule for non-identical parallel machines with sequence-dependent setups and quality restrictions

This paper proposes a dispatching rule that guarantees a predetermined minimum quality level for non-identical parallel machines with multiple product types. Manufacturers are focusing on improving the overall quality of their products, as the demand for top quality products is increasing. Such changes increase the possibility of neglecting another crucial factor in manufacturing schedules, namely due date. Traditionally, jobs are dispatched with the focus on meeting due dates. That is, jobs are assigned to machines without consideration of product quality. This approach opens the possibility of manufacturing poor quality products. Realizing the shortcomings of the existing dispatching rules, manufacturers are tempted to dispatch jobs with the objective of maximizing product quality. With such an attempt, jobs are likely to be assigned to high performance machines only. In turn, waiting times will increase and job delays are inevitable. This research proposes a dispatching rule that satisfies both criteria, reducing due date delays, while ensuring a predefined product quality level. A quality index is introduced to standardize various product qualities. The index is used to ensure a predetermined quality level, whilst minimizing product delays. Simulations compare various dispatch methods, evaluating them based on mean tardiness and product quality.