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     

天地测控资源调度的两阶段递进遗传算法

为对天地测控资源调度进行高效求解,设计了两阶段递进遗传算法对其进行优化调度。鉴于问题的目标具有一定的可分性,以时间为依据将被调度弧段划分成两个部分,在对第一部分形成种群并作进化求解的基础上,将其最优解与第二部分弧段组合,并作进一步的进化求解。为了缓解两阶段优化的局部搜索特性,在第一阶段个体适应度计算中,以一定概率设定虚拟弧段,保留具有潜在全局优势的个体。仿真表明该方法能在确保求解质量的前提下明显减少运算时间。     

大型工程项目集成化管理环境下的知识协同与任务调度

将各个项目单元抽象为不同的知识源,详细分析了集成化管理环境下的知识协同问题,提出了基于权威性加权原则的知识协同处理策略,并就策略修正、协同求解等问题作了分析说明。在此基础上,采取前向调度算法和逆向调度算法相结合的迭代算法,建立了协同工作中的任务调度模型,算例证明,模型能够有效满足各约束条件下任务的增删需求。     

Transporting jobs through a two‐machine open shop

We consider the two‐machine open shop scheduling problem in which the jobs are brought to the system by a single transporter and moved between the processing machines by the same transporter. The purpose is to split the jobs into batches and to find the sequence of moves of the transporter so that the time by which the completed jobs are collected together on board the transporter is minimal. We present a ‐approximation algorithm. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

基于LMI的不确定性无尾飞行器鲁棒变增益控制器设计

无尾式飞行器是飞行器发展的方向,研究无尾式控制具有重要意义.研究了线性变参数系统的增益调度控制器的设计方法,采用多胞形进行增益调度,提出了一种简单实用的变参数顶点凸分解方法,该方法在保证系统稳定的情况下,确保系统达到最优性能指标.同时还充分考虑了系统的不确定性因素,利用线性矩阵不等式(LMI)对系统进行鲁棒控制器设计,大大减少了计算量以及对系统的约束,设计出了基于LMI的增益调度控制器,通过非线性仿真结果可以看出,该控制器在调节变量变化很大的情况下,使得系统在0.5s内收敛,而且超调量很小,论证了该方法在无尾式飞控系统中应用的可行性.     

考虑随机回放的卫星数传调度问题的一种求解方法

针对考虑随机回放的卫星数传调度问题,从置换空间到调度解空间的映射方法和置换空间的搜索算法两方面进行了研究.提出了一种时间窗优先的置换序列映射算法,并证明该映射算法可以将置换序列映射到调度解空间上的最优解.提出了一种遗传随机搜索算法,基于有记忆功能的随机邻域搜索,在置换空间上搜索产生优化调度的置换序列.仿真计算表明,遗传随机搜索算法可以增强遗传算法的局部搜索能力,在搜索结果上平均获得了2.72%的改进.     

Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work

We consider the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. We first discuss the approximability of the problem. We then develop two pseudo‐polynomial dynamic programming algorithms and a fully polynomial‐time approximation scheme for the problem. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 172–183, 2016     

A note on efficient sequences with respect to total flow time and number of tardy jobs

For the single‐machine scheduling problem with the objective of simultaneously minimizing total flow time and number of tardy jobs, a lower bound on the number of efficient sequences is known. However, the proof thereof, which makes use of a modified version of Smith's algorithm, is unduly lengthy and sophisticated. Adopting a totally new point of view, we present in this short article a much simpler proof based on the naive idea of pairwise interchange. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 346–348, 2016     

带数据传输的光学卫星成像调度系统关键技术研究

针对光学小卫星成像调度系统设计需求,考虑侧视、存储容量、能量和数据传输等复杂约束,面向小规模问题应用,设计了问题求解流程.建立了顶点和边都带权的成像约束图模型,并提出了基于标记更新最短路算法的复杂约束成像卫星调度算法解决成像方案生成过程;对数传方案生成过程,给出背包模型并采用带回看策略的贪婪启发式方法进行问题求解.实验结果表明,该方法是可行和适用的.