Scheduling with variable time slot costs

In this article, we study a class of new scheduling models where time slot costs have to be taken into consideration. In such models, processing a job will incur certain cost which is determined by the time slots occupied by the job in a schedule. The models apply when operational costs vary over time. The objective of the scheduling models is to minimize the total time slot costs plus a traditional scheduling performance measure. We consider the following performance measures: total completion time, maximum lateness/tardiness, total weighted number of tardy jobs, and total tardiness. We prove the intractability of the models under general parameters and provide polynomial‐time algorithms for special cases with non‐increasing time slot costs.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

等效载噪比评估全球导航卫星系统接收机误码率的适应性分析

等效载噪比是全球导航卫星系统接收机捕获、数据解调和跟踪性能的重要指标。近年来,研究人员取得大量以等效载噪比为指标的干扰影响分析研究成果,但鲜有等效载噪比适应性分析。为此,展开等效载噪比适应性研究。在推导单频干扰下接收机等效载噪比和误码率模型基础上,得出特定条件下等效载噪比评估数据解调性能失效的结论。同时,深入分析等效载噪比失效的机理,给出等效载噪比指标的适用条件。仿真实验验证了理论分析的正确性。     

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     

Determining optimal sizes of bounded batches with rejection via quadratic min‐cost flow

In this article, we consider a single machine scheduling problem, in which identical jobs are split into batches of bounded sizes. For each batch, it is allowed to produce less jobs than a given upper bound, that is, some jobs in a batch can be rejected, in which case a penalty is paid for each rejected job. The objective function is the sum of several components, including the sum of the completion times, total delivery cost, and total rejection cost. We reduce this problem to a min‐cost flow problem with a convex quadratic function and adapt Tamir's algorithm for its solution. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 217–224, 2017     

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

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

基于Pareto排序法的战时装备维修任务多目标调度方法

针对战时武器装备维修保障问题,建立了包括最大完工时间、延迟时间和维修单元负荷在内的多目标优化调度模型。为提高解的多样性和收敛性,构建了一种基于Pareto排序法和小生境技术相结合的遗传算法用于模型求解,引入Pareto排序和拥挤距离进行适应度计算,通过混沌系统随机生成权重系数,并使用小生境技术改进选择方式。通过实例验证表明,该方法能够有效地解决装备维修多目标调度问题。     

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

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

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

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

Linking a throughput simulation to a systems dynamics simulation to assess the utility of a US Navy foreign humanitarian aid mission

The success of any humanitarian aid mission is generally measured by the timeliness of critical supplies that are delivered to the affected area. However, a more interesting analysis may be to determine the effect of the aid on the overall satisfaction of the local population. The authors' research focused on the delivery of humanitarian aid to a notional region that was decimated by flooding with ships, landing craft and security personnel provided by the US Navy and Marines. While the research effort addressed naval force structure, the focus of the research was: (1) to assess different delivery methods for the aid; and (2) to determine how the aid delivery impacted the overall satisfaction of the local population. To examine both concerns, two simulation models were developed, with one examining the throughput of aid delivered during the operation, and the other the satisfaction of the population based on the humanitarian aid effort.