On competitive analysis for polling systems

Polling systems have been widely studied, however most of these studies focus on polling systems with renewal processes for arrivals and random variables for service times. There is a need driven by practical applications to study polling systems with arbitrary arrivals (not restricted to time-varying or in batches) and revealed service time upon a job's arrival. To address that need, our work considers a polling system with generic setting and for the first time provides the worst-case analysis for online scheduling policies in this system. We provide conditions for the existence of constant competitive ratios, and competitive lower bounds for general scheduling policies in polling systems. Our work also bridges the queueing and scheduling communities by proving the competitive ratios for several well-studied policies in the queueing literature, such as cyclic policies with exhaustive, gated or l-limited service disciplines for polling systems.     

Scheduling parallel dedicated machines with the speeding‐up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two‐machine problem is NP‐hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst‐case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple‐choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Scheduling and due‐date quotation in a make‐to‐order supply chain

We consider a manufacturer, served by a single supplier, who has to quote due dates to arriving customers in a make‐to‐order production environment. The manufacturer is penalized for long lead times and for missing due dates. To meet due dates, the manufacturer has to obtain components from a supplier. We model this manufacturer and supplier as a two‐machine flow shop, consider several variations of this problem, and design effective due‐date quotation and scheduling algorithms for centralized and decentralized versions of the model. We perform extensive computational testing to assess the effectiveness of our algorithms and to compare the centralized and decentralized models to quantify the value of centralized control in a make‐to‐order supply chain. Since complete information exchange and centralized control is not always practical or cost‐effective, we explore the value of partial information exchange for this system. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

基于目标威胁度的相控阵雷达自适应调度方法

对时间资源的合理安排是相控阵雷达发挥自身优势的关键。将目标威胁度引入调度算法中,与工作方式和任务截止期共同进行综合优先级规划。通过构建目标威胁度的量化模型,使雷达在调度跟踪任务时依目标威胁度大小分配时间。提出了修正价值率和执行威胁率的概念,完善了性能评估指标。通过仿真,全面评价了新算法性能,验证了引入目标威胁度的合理性。结果表明,新算法可以有效提升相控阵雷达对高威胁度目标的处理能力。     

机务保障要求到保障方案转换

首先以装备可靠性为依据,以任务要求中任务时间、出动飞机数量、任务可靠度等参数为约束,建立了保障资源的配置模型;在确定保障资源配置基础上再以保障任务时间为优化目标,建立保障任务调度模型和调度算法,按照保障专业调度优化,为保障方案制定奠定了重要基础,对实行精确化保障有重要现实意义,对基层级的保障工作有很强的指导作用。     

基于变结构的应急航材调度策略

针对应急航材需求的随机性提出了变结构应急航材配送网络的概念,立足于物流运输车辆的优化调度,将现代优化算法引入应急航材的调度中,通过仿真算例的验证可以得出调运路径长度及应急航材需求量与调运时间成正比。     

基于预定作业周期的航母作战部署调度研究

为科学筹划航母作战部署调度,优化航母作战兵力的运用,对航母作战部署调度问题进行建模研究。介绍航母预定作业周期,重点阐述航母综合训练期、维修保障期和人员/作战节奏等相关内容;在此基础上,分析航母作战部署调度的约束条件,在满足对作战区域有效时间覆盖条件下,以最小化航母作战兵力数量为目标函数,构建航母作战部署调度优化模型,并通过实例进行验证。结果表明,该模型是有效、实用的,可为科学决策航母作战部署调度提供依据和方法。     

带时间窗的相控阵雷达实时任务调度方法

为了解决传统相控阵雷达任务调度中采用基于工作方式优先级的方法而存在忽略任务时间紧迫性和重要性的问题,提出了一种基于任务自身工作方式优先级、截止期和空闲时间3个特征参数的相控阵雷达任务调度方法,通过调整参数的权重来适应调度器不同的负载情况,并采用时间窗处理发生冲突的任务请求,确保更多的高优先级任务在调度间隔内被调度。仿真结果表明,所提出的方法能够有效提高任务的调度成功率,明显改善调度器性能。     

基于改进型粒子群算法的航空多项目调度方法

多项目并举状况下的资源有限-工期最短问题求解,是提高航空企业资源利用率、缩短项目周期的关键。在项目网络计划的基础上,提出了一种改进型粒子群算法对多项目实施并行资源调度,求解多项目最优资源调度方案。该方法通过改进的交叉和变异操作,提高了解的多样性,保证了算法的全局搜索能力。最后,通过对某型飞机的2个并行装配计划进行实例计算,验证了方法的有效性。     

匈牙利算法在多目标分配中的应用

在多目标攻击决策中 ,根据 Harold提出的目标优势函数 ,分析了使所有目标机的总优势函数为指派问题 ,运用匈牙利算法对 n对 n的最优目标分配指派问题进行求解 ,并把它推广至 n对 m的多目标分配中。仿真结果表明匈牙利算法对于此类多目标分配指派问题的求解是十分有效的。