Two-agent scheduling with linear resource-dependent processing times

This paper considers a two-agent scheduling problem with linear resource-dependent processing times, in which each agent has a set of jobs that compete with that of the other agent for the use of a common processing machine, and each agent aims to minimize the weighted number of its tardy jobs. To meet the due date requirements of the jobs of the two agents, additional amounts of a common resource, which may be in discrete or continuous quantities, can be allocated to the processing of the jobs to compress their processing durations. The actual processing time of a job is a linear function of the amount of the resource allocated to it. The objective is to determine the optimal job sequence and resource allocation strategy so as to minimize the weighted number of tardy jobs of one agent, while keeping the weighted number of tardy jobs of the other agent, and the total resource consumption cost within their respective predetermined limits. It is shown that the problem is -hard in the ordinary sense, and there does not exist a polynomial-time approximation algorithm with performance ratio unless ; however it admits a relaxed fully polynomial time approximation scheme. A proximal bundle algorithm based on Lagrangian relaxation is also presented to solve the problem approximately. To speed up convergence and produce sharp bounds, enhancement strategies including the design of a Tabu search algorithm and integration of a Lagrangian recovery heuristic into the algorithm are devised. Extensive numerical studies are conducted to assess the effectiveness and efficiency of the proposed algorithms.     

RCS特性辅助的CMIMO雷达功率资源分配方法

针对集中式多输入多输出(collocated multiple-input multiple-output, CMIMO)雷达在实际探测过程中,未有效结合目标雷达散射截面(radar cross section, RCS)高动态变化特性导致雷达跟踪精度不高甚至失跟的问题,提出一种基于目标RCS高动态特性的CMIMO雷达功率资源自适应分配方法。考虑到目标RCS特征的角度敏感性,利用目标运动状态的可预测性动态获取实际观测角度,从而完成跟踪帧的极化方式优选;在此基础上构建包含功率与RCS的多目标跟踪误差后验克拉美罗下界,将其作为目标函数进行优化,利用内点惩罚法求解该凸优化问题即可实现RCS高动态情况下的功率优化分配。实验结果表明:该方法可结合目标不同方向RCS动态分集特性实现功率的有效分配,相比于传统RCS模型分配方案,有效解决了分配方案与实际跟踪场景之间的失配问题,从而提升了CMIMO雷达的多目标跟踪性能。     

A bicriterion approach to common flow allowances due window assignment and scheduling with controllable processing times

We investigate a single‐machine scheduling problem for which both the job processing times and due windows are decision variables to be determined by the decision maker. The job processing times are controllable as a linear or convex function of the amount of a common continuously divisible resource allocated to the jobs, where the resource allocated to the jobs can be used in discrete or continuous quantities. We use the common flow allowances due window assignment method to assign due windows to the jobs. We consider two performance criteria: (i) the total weighted number of early and tardy jobs plus the weighted due window assignment cost, and (ii) the resource consumption cost. For each resource consumption function, the objective is to minimize the first criterion, while keeping the value of the second criterion no greater than a given limit. We analyze the computational complexity, devise pseudo‐polynomial dynamic programming solution algorithms, and provide fully polynomial‐time approximation schemes and an enhanced volume algorithm to find high‐quality solutions quickly for the considered problems. We conduct extensive numerical studies to assess the performance of the algorithms. The computational results show that the proposed algorithms are very efficient in finding optimal or near‐optimal solutions. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 41–63, 2017     

测试性增长中资源优化配置模型及求解

良好的测试性设计对系统维修性具有重要意义,测试性增长试验通过一系列测试性设计缺陷发现和纠正措施,可保证系统测试性指标达到设计要求。针对基于延缓纠正的测试性增长过程中的资源配置问题进行研究,基于增长试验目标是否明确和试验资源是否受限制问题构建资源优化配置模型,并提出一种基于拉格朗日松弛和本地搜索的快速优化算法。仿真结果表明:该模型能够有效指导测试性增长中的资源优化配置问题,所提混合优化方法能够高效、准确地求解整数规划问题。     

军事云环境下基于动态博弈的资源调度方法

针对军事云环境下联合指挥资源调度优化问题,综合考虑了多部队任务需求,多目标优化,多部队资源竞争等约束条件,运用动态博弈理论及方法,建立并提出了一种基于完全信息扩展博弈的资源调度模型及方法,提高了资源调度效率,兼顾了多部队利益,增加了联合作战效益。最后通过实验验证了其有效性及准确性。     

A self‐adapting genetic algorithm for project scheduling under resource constraints

This papers deals with the classical resource‐constrained project scheduling problem (RCPSP). There, the activities of a project have to be scheduled subject to precedence and resource constraints. The objective is to minimize the makespan of the project. We propose a new heuristic called self‐adapting genetic algorithm to solve the RCPSP. The heuristic employs the well‐known activity list representation and considers two different decoding procedures. An additional gene in the representation determines which of the two decoding procedures is actually used to compute a schedule for an individual. This allows the genetic algorithm to adapt itself to the problem instance actually solved. That is, the genetic algorithm learns which of the alternative decoding procedures is the more successful one for this instance. In other words, not only the solution for the problem, but also the algorithm itself is subject to genetic optimization. Computational experiments show that the mechanism of self‐adaptation is capable to exploit the benefits of both decoding procedures. Moreover, the tests show that the proposed heuristic is among the best ones currently available for the RCPSP. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 433–448, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10029     

装备维修资源优化中的模拟退火遗传算法

在对模拟退火遗传算法改进的基础上,结合建立的通信装备维修资源分配模型,给出了该算法的实现过程,并利用此算法对模型进行了最优化求解。实例的计算结果表明该算法对于模型的求解具有较好的收敛性。     

分层分布式分群监控体系下的网格资源发现机制

网格中资源发现机制是把资源提供者和资源请求者联系起来的重要环节.在分析分层分布式分群监控体系结构和现有资源发现机制的基础上,提出将集中式目录服务、资源路由表和移动代理三种机制相结合的网格资源发现机制.实验验证该机制在小范围内查找具有性能高效的特点,而在大范围内查找减少了资源发现代理的分发数量,降低了系统消息的负载,进而降低了网络资源的占用.     

A model to design recreational boat mooring fields

This article develops a mathematical model and heuristic algorithm to design recreational boating mooring fields. The boating industry is important to the Florida economy, and boat storage is becoming a concern among those in the industry. The mooring field design problem is formulated to maximize the total number of boat feet moored in the mooring field. In the model, we allow two adjacent moorings to overlap, which introduces a risk that under certain conditions the boats on these moorings could contact each other. We identify the conditions when contact is possible and quantify the probability of contact. The mooring field design problem is formulated as a nonlinear mixed‐integer programming problem. To solve the problem, we decompose it into two separate models, a mooring radii assignment model and a mooring layout model, which are solved sequentially. The first is solved via exhaustive enumeration and the second via a depth‐first search algorithm. Two actual mooring fields are evaluated, and in both cases our model leads to better layouts than ones experts developed manually. The mooring field design model rationalizes the mooring field design and shows that in one case by increasing the risk from 0 to 1%, the mooring efficiency increases from 74.8% to 96.2%. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

光互连网络中资源预留的多级光互连仲裁机制

基于资源预留策略提出一种多级光互连仲裁机制,通过将网络分级实现快速、高效的仲裁。多优先级数据缓存队列的传输节点设计,提供了不同类型流量的差异化传输;通过预约式两级仲裁机制,实现网络的完全公平与100%的高吞吐率。设计并对快速仲裁通道进行了合理布局,极大地缩短了仲裁延迟。仿真结果表明:采用基于资源预留的分级仲裁策略,在多种流量模式下所有节点均获得公平的服务。与Feather Weight相比,分级仲裁策略吞吐率提高17%;与2-pass相比,仲裁延迟减少15%,同时,功耗减少5%。