模糊匈牙利算法在舰艇抢修人员指派问题中的研究

分析了舰艇在执行任务或作战等紧急情况下的抢修人员指派问题,并对此建立了多目标广义指派问题的数学模型。在任务数少于工作人数的情况下,采用虚拟“工作”和“人员”的方法,得到适合经典匈牙利算法的拓展效益矩阵,并对此矩阵采用匈牙利算法求得最优指派。     

基于匈牙利算法求解的火力分配问题

匈牙利算法是求解指派问题的一个很好的算法,但一般情况下,火力分配问题的数学模型不具备指派问题的模型形式.针对目标函数是线性或非线性的一类火力分配问题,提出了虚拟火力单位或目标的方法,将问题转化为能够用匈牙利算法求解的指派问题,该方法简单、易于计算,有很高的应用价值.     

指派问题的降阶优化算法

指派问题是运筹学中特殊线性规划中的一类问题。在现实生活中,指派问题非常普遍,常常可以见到各种各样的指派问题。通过对指派问题的数学模型进行分析,提出了与以往方法不同的求解指派问题的一种新的思路,通过对几个定理的研究,给出了一种新的求解方法——降阶优化算法。对求解指派问题提供了一种新的途径,在运筹学等领域有着较好的应用前景。     

智能化战机编队指派的战术匹配寻优算法

战机编队指派是空战指挥决策的重要一环,属于多属性决策优化问题。为提高空战指挥的自动化水平,设计了一种智能化战机编队指派的战术匹配寻优算法。首先分析了战机编队空战优势的估算方法;然后提出了战机编队指派的初步匹配方法,该方法通过战术匹配得到满足编队级最小空战优势要求的,能够覆盖最多目标编队的初步指派方案;最后设计了基于自扰动蚁群算法的战机编队指派寻优算法,该算法针对未分配战机寻找能够使己方战术价值总和最大化的战机编队指派方案。对战机编队指派的初步匹配结果和自扰动蚁群算法寻优结果进行合成得到最终的战机编队指派方案。示例验证了该方法能够得到与空战指挥员经验一致的战机编队指派结果,而且具有较好的实时性。     

基于排队系统的战时基本抢修单元指派模型

基本抢修单元的指派过程是战时维修保障工作中的重要环节,其指派的合理性将直接影响到维修保障工作的顺利进行。针对传统的基本抢修单元指派模糊、效率低下等问题,结合战时基本抢修单元可指派数量的有限性,建立了一种基于排队系统的战时基本抢修单元指派模型,为缩短保障时间、提高装备作战效能提供了一种参考方法。     

在轨服务航天器任务指派问题

一个在轨服务可有多种服务选择,必须进行合理的任务指派。首先求解服务航天器满足燃耗约束下的可达区域,筛选出满足可达范围要求的目标航天器。然后,以任务执行时间、燃料消耗和航天器服务优先级为优化目标,研究多目标的任务指派问题。通过设计决策变量,考虑时间、燃耗等约束,建立了基于0-1整数规划的任务模型,采用NSGA-Ⅱ算法,求得问题的Pareto最优集,得到多组可供任务设计者选择自己偏好的折中方案。文章给出了两个多目标优化的仿真算例,算例一给出了任务指派的一般研究结论,算例二对比了另外一种算法：分层-加权法。仿真结果表明利用文章给出的方法可以较好地解决多目标下在轨服务任务指派问题。     

防空反导装备抢修任务分配建模

分析了防空反导装备战场抢修任务的特点和类型,构建了防空反导装备战场抢修任务分配模型。分析了单人多事型抢修任务分配计算模型、多人一事型抢修任务分配流程和有规定顺序的抢修任务分配方案,采取不同方法求解了各自的最优解,并综合得到全局最优解。通过增加虚拟任务将非平衡指派模型改进为标准平衡指派模型,并运用匈牙利算法进行求解,有效降低了模型计算量。最后,通过算例验证了模型和方法的有效性,结果表明:该方法能有效缩短装备抢修时间,可为部队进行抢修任务分配优化提供参考。     

面向多平台多目标协同跟踪的指派问题

针对多平台多目标协同跟踪中要求多个无人地面平台尽可能均匀地协同跟踪多个目标的特点,提出了改进的离散粒子群优化算法。首先采用连续型粒子群优化算法中的速度和位置迭代公式,然后对粒子位置进行离散编码,使粒子编码对应于可行的指派方案;其次,在优化算法中引入局部搜索,提高算法寻优性能。最后将所提算法应用于多平台多目标协同跟踪中的指派问题,并与未加入局部搜索的粒子群优化算法比较,仿真结果表明,加入局部搜索后的离散粒子群优化算法具有较好的寻优性能。     

基于可变虚拟阻抗的感性逆变器下垂控制

为解决并联逆变器功率分配差异,首先从逆变器并联的功率传输特性出发分析了线路阻抗差异对感性逆变器无功功率分配的影响;然后,通过选取合适的逆变器双环控制参数,将逆变器等效输出阻抗设计成感性,并在传统下垂控制的基础上引入虚拟阻抗,通过实时无功与给定无功的偏差调节虚拟阻抗补偿线路阻抗差异。随后的仿真结果证明:该方法能实现线路阻抗差异下逆变器并联功率均分。     

多传感器优化分配数学模型及其求解

当传感器资源有限而同时又有多个目标存在时,利用最大信息增益准则,在目标身份和目标优先级确定的基础上,将传感器的优化分配问题转化为指派问题进行求解,并对算法进行了仿真实验。     

Efficient algorithms for flexible job shop scheduling with parallel machines

Job shop scheduling with a bank of machines in parallel is important from both theoretical and practical points of view. Herein we focus on the scheduling problem of minimizing the makespan in a flexible two-center job shop. The first center consists of one machine and the second has k parallel machines. An easy-to-perform approximate algorithm for minimizing the makespan with one-unit-time operations in the first center and k-unit-time operations in the second center is proposed. The algorithm has the absolute worst-case error bound of k − 1 , and thus for k = 1 it is optimal. Importantly, it runs in linear time and its error bound is independent of the number of jobs to be processed. Moreover, the algorithm can be modified to give an optimal schedule for k = 2 .     

Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost

Motivated by the flow of products in the iron and steel industry, we study an identical and parallel machine scheduling problem with batch deliveries, where jobs finished on the parallel machines are delivered to customers in batches. Each delivery batch has a capacity and incurs a cost. The objective is to find a coordinated production and delivery schedule that minimizes the total flow time of jobs plus the total delivery cost. This problem is an extension of the problem considered by Hall and Potts, Ann Oper Res 135 (2005) 41–64, who studied a two‐machine problem with an unbounded number of transporters and unbounded delivery capacity. We first provide a dynamic programming algorithm to solve a special case with a given job assignment to the machines. A heuristic algorithm is then presented for the general problem, and its worst‐case performance ratio is analyzed. The computational results show that the heuristic algorithm can generate near‐optimal solutions. Finally, we offer a fully polynomial‐time approximation scheme for a fixed number of machines. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 492–502, 2016     

A parallel sequencing algorithm for minimizing total cost

The problem of sequencing jobs on parallel processors when jobs have different available times, due dates, penalty costs and waiting costs is considered. The processors are identical and are available when the earliest job becomes available and continuously thereafter. There is a processor cost during the period when the processor is available for processing jobs. The proposed algorithm finds the sequence (or sequences) with minimum total cost (sum of waiting, penalty and processor costs.). A proof of the algorithm and numerical results are given.     

Single- and multiple-processor models for minimizing completion time variance

This article concerns the scheduling of n jobs around a common due date, so as to minimize the average total earliness plus total lateness of the jobs. Optimality conditions for the problem are developed, based on its equivalence to an easy scheduling problem. It seems that this problem inherently has a huge number of optimal solutions and an algorithm is developed to find many of them. The model is extended to allow for the availability of multiple parallel processors and an efficient algorithm is developed for that problem. In this more general case also, the algorithm permits great flexibility in finding an optimal schedule.     

An exact branch‐and‐price algorithm for multitasking scheduling on unrelated parallel machines

We consider the multitasking scheduling problem on unrelated parallel machines to minimize the total weighted completion time. In this problem, each machine processes a set of jobs, while the processing of a selected job on a machine may be interrupted by other available jobs scheduled on the same machine but unfinished. To solve this problem, we propose an exact branch‐and‐price algorithm, where the master problem at each search node is solved by a novel column generation scheme, called in‐out column generation, to maintain the stability of the dual variables. We use a greedy heuristic to obtain a set of initial columns to start the in‐out column generation, and a hybrid strategy combining a genetic algorithm and an exact dynamic programming algorithm to solve the pricing subproblems approximately and exactly, respectively. Using randomly generated data, we conduct numerical studies to evaluate the performance of the proposed solution approach. We also examine the effects of multitasking on the scheduling outcomes, with which the decision maker can justify making investments to adopt or avoid multitasking.     

Due‐window assignment with unit processing‐time jobs

In due‐window assignment problems, jobs completed within a designated time interval are regarded as being on time, whereas early and tardy jobs are penalized. The objective is to determine the location and size of the due‐window, as well as the job schedule. We address a common due‐window assignment problem on parallel identical machines with unit processing time jobs. We show that the number of candidate values for the optimal due‐window starting time and for the optimal due‐window completion time are bounded by 2. We also prove that the starting time of the first job on each of the machines is either 0 or 1, thus introducing a fairly simple, constant‐time solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

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     

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.     

A hybrid algorithm for the one machine sequencing problem to minimize total tardiness

In a recent paper, Hamilton Emmons has established theorems relating to the order in which pairs of jobs are to be processed in an optimal schedule to minimize the total tardiness of performing n jobs on one machine. Using these theorems, the algorithm of this paper determines the precedence relationships among pairs of jobs (whenever possible) and eliminates the first and the last few jobs in an optimal sequence. The remaining jobs are then ordered by incorporating the precedence relationships in a dynamic programming framework. Propositions are proved which considerably reduce the total computation involved in the dynamic programming phase. Computational results indicate that the solution time goes up less than linearly with the size (n) of the problem. The median solution time for solving 50 job problems was 0.36 second on UNIVAC 1108 computer.     

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