多专业批量维修任务调度方法研究

通过对不同专业设置方式下的维修任务调度问题进行分析,以最小化批量维修任务的维修时间为目标,将考虑专业维修顺序的批量维修任务调度问题分成两步进行求解,首先,建立了批量维修任务在专业领域内的调度及优化模型;其次,提出了基于NEH的批量维修任务排序方法．最后,通过实例对模型和方法的正确性和可行性进行了说明和验证,实例结果表明,该方法更贴近于实际,实现了快速、有效地解决维修任务调度问题,     

An efficient metaheuristic for integrated scheduling and staffing IT projects based on a generalized minimum cost flow network

Scheduling IT projects and assigning the project work to human resources are an important and common tasks in almost any IT service company. It is particularly complex because human resources usually have multiple skills. Up to now only little work has considered IT‐specific properties of the project structure and human resources. In this article, we present an optimization model that simultaneously schedules the activities of multiple IT projects with serial network structures and assigns the project work to multiskilled internal and external human resources with different efficiencies. The goal is to minimize costs. We introduce a metaheuristic that decomposes the problem into a binary scheduling problem and a continuous staffing problem where the latter is solved efficiently by exploiting its underlying network structure. For comparison, we solve the mixed–binary linear program with a state–of–the–art commercial solver. The impacts of problem parameters on computation time and solution gaps between the metaheuristic and the solver are assessed in an experimental study. Our results show that the metaheuristic provides very favorable results in considerable less time than the solver for midsize problems. For larger problems, it shows a similar performance while the solver fails to return feasible solutions. © 2012 Wiley Periodicals, Inc. Naval Research Logistics 59: 111–127, 2012     

面向能耗有效高性能嵌入式微处理器的VLIW调度

为了降低功耗,目前能耗有效的嵌入式微处理器一般都采用分布式与层次化的寄存器文件结构。第一层的超小寄存器文件(TORF)的极小容量使得很多数据必须存放到第二层的通用寄存器文件(GRF)中,这给编译器带来了新的挑战。通过分析程序特征,提出了新的VLIW调度算法,通过在编译时对变量进行检测,在恰当的时机插入虚拟的copy操作并进行指令与通信调度,为对寄存器需求较大的全局变量与软流水变量构建了新的包含GRF的数据传输路由,将对TORF的压力转移到GRF中。实验结果表明,新的VLIW调度算法符合处理器的设计初衷。与不使用GRF相比,在程序性能只降低约8%的情况下,降低了约51%的寄存器访问能耗,43%的处理器能耗。最关键的是避免了程序员手工分配优化的难题。     

航天测控调度问题的拉格朗日启发式算法

通过分析航天测控调度问题的测控需求,建立了航天测控调度0-1整数规划模型,运用拉格朗日松弛方法对模型中的任务约束和设备约束进行了松弛,运用次梯度优化算法求得了航天测控调度问题上界,同时得到了决策变量对应的拉格朗日权重,可以作为决策变量在最优解中是否被调度的启发式信息,对拉格朗日权重进行分析,提出了求解问题可行解的拉格朗日启发式算法。最后,通过对两个场景的试验分析验证了拉格朗日启发式算法所求可行解的优越性。     

基于时间窗的宽带阵列多目标干扰资源调度

随着宽带数字阵列技术和有源干扰技术的不断发展和成熟,舰载有源干扰设备的未来发展方向将是宽带数字阵列有源干扰系统。针对多目标干扰问题,提出了目标干扰时间窗概念和两种时间窗的处理方法,并建立干扰资源调度模型,通过仿真计算和对比分析,得出基于模糊时间窗的资源调度模型性能优于基于硬时间窗的资源调度模型,能够对干扰资源进行合理的调度,提高宽带阵列多目标干扰能力。     

一种用于区分服务路由器的crossbar调度算法

宽带路由器一般采用crossbar交换开关。Crossbar交换开关对QoS (QualityofService)的支持十分重要。提出一种支持IETF区分服务 (DifferentiatedService)服务模型的crossbar调度算法———OSP (OutputSerialPolling) ,该算法带宽利用率高 ,支持报文优先级。与目前存在的同类算法相比 ,具有硬件实现简单的优点     

导航卫星上行注入任务调度模型及启发式算法

合理安排导航卫星与地面上注站星地链路构建与导航电文上注,对保证星上导航电文的准确性和精确性有着重要意义。对卫星导航系统上行注入过程进行了分析,构建了上行注入任务调度问题的多目标混合整数规划模型,设计了基于规则的启发式求解算法。基于北斗二代和美国的GPS卫星导航系统构建仿真场景,仿真结果验证了模型和算法的正确性、可行性;通过分析仿真结果,得到影响卫星导航系统上行注入任务完成的关键因素。     

舰艇防空火力规划与调度方法研究

根据舰艇防空武器拦截过程的时间连续性和拦截效果的不确定性特点,提出了智能规划和优化调度相结合的舰艇防空计划生成方法。在规划阶段,先用智能规划描述语言PDDL对舰艇防空问题进行建模;针对新的来袭目标或观察的拦截结果,利用智能规划的高效行动推理能力,快速生成可能的备选行动方案;在优化调度阶段,对已生成的备选方案的行动系列进行时间、资源冲突处理,并计算选择出当前最佳拦截方案。与现有的采用离散化处理的武器-目标分配方法相比,该规划与调度过程充分体现了拦截过程的连续性,拦截效果的不确定性,拦截过程中的武器协同,以及最佳拦截时机的选择等,更好地描述了舰艇防空的实际过程。最后,通过蒙特卡罗仿真试验,验证了算法的有效性,为舰艇的自动化防空提供了一种新的解决办法。     

基于信息损失最小的预警卫星传感器调度模型

科学合理地调度预警卫星传感器资源是提高弹道导弹预警作战效能的重要手段.在预警卫星传感器资源(主要是凝视探测器)有限而进攻弹道导弹目标数量较多时,利用最小信息损失准则,将传感器调度问题转化为最优访问路径问题进行建模研究,满足了导弹预警资源调度的需要,仿真结果验证了模型的可靠性和可用性.     

Integrated scheduling of loading and transportation with tractors and semitrailers separated

Motivated by some practical applications, we study a new integrated loading and transportation scheduling problem. Given a set of jobs, a single crane is available to load jobs, one by one, onto semitrailers with a given capacity. Loaded semitrailers are assigned to tractors for transportation tasks. Subject to limited resources (crane, semitrailers, and tractors), the problem is to determine (1) an assignment of jobs to semitrailers for loading tasks, (2) a sequence for the crane to load jobs onto semitrailers, (3) an assignment of loaded semitrailers to tractors for transportation tasks, and (4) a transportation schedule of assigned tractors such that the completion time of the last transportation task is minimized. We first formulate the problem as a mixed integer linear programming model (MILPM) and prove that the problem is strongly NP‐hard. Then, optimality properties are provided which are useful in establishing an improved MILPM and designing solution algorithms. We develop a constructive heuristic, two LP‐based heuristics, and a recovering beam search heuristic to solve this problem. An improved procedure for solutions by heuristics is also presented. Furthermore, two branch‐and‐bound (B&B) algorithms with two different lower bounds are developed to solve the problem to optimality. Finally, computational experiments using both real data and randomly generated data demonstrate that our heuristics are highly efficient and effective. In terms of computational time and the number of instances solved to optimality in a time limit, the B&B algorithms are better than solving the MILPM. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 416–433, 2015