A branch‐and‐price algorithm for parallel machine scheduling with time windows and job priorities

This paper presents a branch‐and‐price algorithm for scheduling n jobs on m nonhomogeneous parallel machines with multiple time windows. An additional feature of the problem is that each job falls into one of ρ priority classes and may require two operations. The objective is to maximize the weighted number of jobs scheduled, where a job in a higher priority class has “infinitely” more weight or value than a job in a lower priority class. The methodology makes use of a greedy randomized adaptive search procedure (GRASP) to find feasible solutions during implicit enumeration and a two‐cycle elimination heuristic when solving the pricing subproblems. Extensive computational results are presented based on data from an application involving the use of communications relay satellites. Many 100‐job instances that were believed to be beyond the capability of exact methods, were solved within minutes. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

联合作战规划中资源调度算法研究

以联合作战为例建立任务和作战平台资源模型,通过多维动态列表规划算法(Multidimensional Dynamic List Scheduling,MDLS)进行任务-平台分配,对平台选择提出了两种不同的优先权计算方法,通过对案例求解比较了不同方法的结果.     

Opportunistic retooling of a flexible machine subject to failure

A set of jobs can be processed without interruption by a flexible machine only if the set of tools required by all jobs can be loaded in the tool magazine. However, in practice the total number of tools required by a job set would exceed the tool magazine capacity. In such situations, the job set has to be carefully partitioned at the start of the production run such that each partition can be processed without interruption. During the production run, if there are unscheduled machine downtimes due to machine failure, this provides an additional opportunity to optimally retool the magazine for a smaller job set consisting of just the unprocessed jobs. In this paper, we study job sequencing rules that allow us to minimize the total expected cost of machine down time due to machine failures and magazine retooling, assuming a dynamic re‐sequencing of the unprocessed jobs after each machine failure. Using these rules, we develop a branch‐and‐bound heuristic that allows us to solve problems of reasonable size. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 79–97, 2001     

基于SWE的空天资源对地观测协同任务规划服务模型

空天协同对地观测是对地观测领域的新趋势。为解决现有空天资源规划调度系统相对独立、协同困难的问题,分析总结了SWE(Sensor Web Enablement)标准,并在此基础上提出了空天资源对地观测协同任务规划服务模型。在此模型中,为实现观测资源共享,建立了空天观测资源传感器描述模型,能够描述典型空天资源的载荷平台、观测机理、定位信息、使用约束和工作特性等信息;为简化观测请求交互流程,基于SOA技术对SWE标准操作进行封装及简化,用户可以在不了解观测平台细节信息的情况下提交观测数据请求。为验证模型有效性,构建了空天资源对地观测协同任务规划实验平台,结果表明该模型具有较强的可实现性和适应性。     

Case‐based reasoning and improved adaptive search for project scheduling

Most scheduling problems are notoriously intractable, so the majority of algorithms for them are heuristic in nature. Priority rule‐based methods still constitute the most important class of these heuristics. Of these, in turn, parametrized biased random sampling methods have attracted particular interest, due to the fact that they outperform all other priority rule‐based methods known. Yet, even the “best” such algorithms are unable to relate to the full range of instances of a problem: Usually there will exist instances on which other algorithms do better. We maintain that asking for the one best algorithm for a problem may be asking too much. The recently proposed concept of control schemes, which refers to algorithmic schemes allowing to steer parametrized algorithms, opens up ways to refine existing algorithms in this regard and improve their effectiveness considerably. We extend this approach by integrating heuristics and case‐based reasoning (CBR), an approach that has been successfully used in artificial intelligence applications. Using the resource‐constrained project scheduling problem as a vehicle, we describe how to devise such a CBR system, systematically analyzing the effect of several criteria on algorithmic performance. Extensive computational results validate the efficacy of our approach and reveal a performance similar or close to state‐of‐the‐art heuristics. In addition, the analysis undertaken provides new insight into the behaviour of a wide class of scheduling heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 201–222, 2000     

CON/SLK due date assignment and scheduling on a single machine with two agents

We consider scheduling problems involving two agents (agents A and B), each having a set of jobs that compete for the use of a common machine to process their respective jobs. The due dates of the A‐jobs are decision variables, which are determined by using the common (CON) or slack (SLK) due date assignment methods. Each agent wants to minimize a certain performance criterion depending on the completion times of its jobs only. Under each due date assignment method, the criterion of agent A is always the same, namely an integrated criterion consisting of the due date assignment cost and the weighted number of tardy jobs. Several different criteria are considered for agent B, including the maxima of regular functions (associated with each job), the total (weighted) completion time, and the weighted number of tardy jobs. The overall objective is to minimize the performance criterion of agent A, while keeping the objective value of agent B no greater than a given limit. We analyze the computational complexity, and devise polynomial or pseudo‐polynomial dynamic programming algorithms for the considered problems. We also convert, if viable, any of the devised pseudopolynomial dynamic programming algorithms into a fully polynomial‐time approximation scheme. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 416–429, 2016     

Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints

In this article, we propose a branch‐and‐price‐and‐cut (BPC) algorithm to exactly solve the manpower routing problem with synchronization constraints (MRPSC). Compared with the classical vehicle routing problems (VRPs), the defining characteristic of the MRPSC is that multiple workers are required to work together and start at the same time to carry out a job, that is, the routes of the scheduling subjects are dependent. The incorporation of the synchronization constraints increases the difficulty of the MRPSC significantly and makes the existing VRP exact algorithm inapplicable. Although there are many types of valid inequalities for the VRP or its variants, so far we can only adapt the infeasible path elimination inequality and the weak clique inequality to handle the synchronization constraints in our BPC algorithm. The experimental results at the root node of the branch‐and‐bound tree show that the employed inequalities can effectively improve the lower bound of the problem. Compared with ILOG CPLEX, our BPC algorithm managed to find optimal solutions for more test instances within 1 hour. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 138–171, 2016     

Scheduling parallel machines with inclusive processing set restrictions and job rejection

In this article, we study a parallel machine scheduling problem with inclusive processing set restrictions and the option of job rejection. In the problem, each job is compatible to a subset of machines, and machines are linearly ordered such that a higher‐indexed machine can process all those jobs that a lower‐indexed machine can process (but not conversely). To achieve a tight production due date, some of the jobs might be rejected at certain penalty. We first study the problem of minimizing the makespan of all accepted jobs plus the total penalty cost of all rejected jobs, where we develop a ‐approximation algorithm with a time complexity of . We then study two bicriteria variants of the problem. For the variant problem of minimizing the makespan subject to a given bound on the total rejection cost, we develop a ‐approximation algorithm with a time complexity of . For the variant problem of maximizing the total rejection cost of the accepted jobs subject to a given bound on the makespan, we present a 0.5‐approximation algorithm with a time complexity of . © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 667–681, 2017     

一种基于目标的雷达对抗侦察策略

传统的电子战接收系统的搜索方式主要针对参数完全未知的敌方信号,通过在频域、空域等各维度进行大范围的逐段重复搜索可在较长时间内获得较好的侦察效果,但不适合短时间内对特定目标群的搜索和验证。针对电子战接收机存在的盲目侦察接收、与作战目标结合不紧密等问题,提出了一种基于作战目标的侦察策略,能够智能引导超外差接收机进行搜索截获,有效提升了超外差接收机对重点目标的实时截获与准确识别能力。     

改进柔性资源约束项目调度模型与粒子群算法

在资源受限项目调度问题中,将可再生资源进一步拓展为具有能力差异的柔性资源,建立考虑能力差异的柔性资源受限的多模式项目调度问题模型,该模型是对传统资源约束项目调度问题(RCPSP)更接近实际的拓展。提出了基于粒子群算法的求解算法,粒子群算法求解该模型的思路为,利用蒙特卡洛方法根据资源-能力矩阵与活动模式-能力矩阵得到活动模式-资源矩阵,将考虑能力差异的柔性资源受限的多模式项目调度问题转换为常规的多模式项目调度问题,然后利用基于任务序列与模式表示的粒子群算法对该多模式项目调度问题进行求解。用数值实例说明了模型的合理性与算法的有效性。