非平衡指派模型及其在航空机务维修中的应用

非平衡指派问题是最优平衡指派问题的推广与深化,在航空机务维修工作中,维修任务的合理配置对及时完成维修任务,保障训练作战计划非常重要.本文从装备完好率和人力资源的优化配置角度出发,按照不考虑维修任务等待时间和考虑维修任务等待时间两种情况分别建立了非平衡指派优化模型,并给出了这两种情况下效益矩阵的构造方法,进而将优化模型转化为最优平衡指派模型进行求解,从而为航空机务维修工作中维修人员的优化配置提供了一种科学、合理的决策方法.     

项目多技能人力资源指派与调度混合算法

研究多技能人力资源在项目活动上的指派与调度问题.首先,从问题特点出发,把原始问题分解为指派问题子模型和调度问题子模型.然后,对项目活动间的重叠关系进行识别,将其转化为对指派问题的有效约束,构建数学规划与约束规划相结合的混合算法对问题求解,并采用CPLEX编程实现.研究表明,算法可有效缩减指派问题的可行域,快速地找到问题的近优解,从而提高多技能人力资源的使用效率,是求解项目多技能人力资源指派与调度问题的一个有效方法.     

关于有能力限制的指派问题的一点注记

首先讨论了有能力限制的不平衡指派问题的转化和最优性,并提出了采用最小费用最大流的方法求解该问题.     

广义指派问题及其在军事装备运输中的推广应用

军事装备中的运输问题复杂多样,如何建立数学模型是寻求优化方案的关键.本文首先将最优线性指派模型推广到广义指派模型并给出其两种算法,其次对带有时间约束的运输问题进行建模,并设法将其转化为广义指派问题来处理,从而为这类运输问题提供了一种有效可行的算法.     

一类齐次多项式优化问题的一个全局优化算法

对图像与信号处理中遇到的一类齐次多项式优化问题,本文首先借助平移技术将目标函数转化为凸函数,然后结合初始点技术提出了求解该类问题的一个全局优化算法.与求解该类问题的幂方法相比,本文给出的方法不但能在一般情形下保证算法的全局收敛性,而且数值结果表明在多数情况下可以得到问题的一个全局最优值解.     

多因素指派模型全局优化问题研究

基于多因素资源优化分配问题的不确定性,建立基于区间数型下的不确定多因素指派模型,给出模型建立的理论依据与全局优化算法,拓展区间数型多因素指派模型,解决了不确定条件下多因素资源优化分配问题.考虑多因素影响,基于任务完成效率,以5类任务多因素分配问题为例,获得了指派模型全局优化的解.为不确定条件下资源优化分配问题的研究拓宽了决策途径.     

线性互补约束规划问题的一种Filter算法

本文研究了求解线性互补约束规划问题的算法问题.首先基于广义互补函数和摄动技术将问题转化为带参数的非线性优化问题,利用SlQP-Filter算法方法,求解线性互补约束规划问题的一种Filter算法.在适当条件下,证明了该算法的全局收敛性.     

二次规划逆问题的牛顿方法

针对二次规划逆问题,将其表达为带有互补约束的锥约束优化问题.借助于对偶理论,将问题转化为变量更少的线性互补约束非光滑优化问题.通过扰动的方法求解转化后的问题并证明了收敛性.采用非精确牛顿法求解扰动问题,给出了算法的全局收敛性与局部二阶收敛速度.最后通过数值实验验证了该算法的可行性.     

求解障碍问题自由边界的一种非精确光滑方法

利用差分原理将一类数学物理障碍问题转化为线性互补问题.给出了求解大规模线性互补问题的一种非精确光滑算法,证明了该算法的适定性和全局收敛性.数值试验表明该方法能很好地求解此类障碍问题.     

一种具有区间数信息的多目标指派方法

针对具有区间数信息的多目标指派问题,给出了一种指派方法。首先,将不同类型目标的区间数损益矩阵规范化为区间数成本矩阵,并应用区间数运算法则构建区间数多目标指派问题的总成本矩阵。然后,通过事先定义的任意两个区间数的序关系,将区间数指派问题优化模型转化为一个双目标优化模型,并采用线性加权法将其转化为单目标优化模型来进行求解,同时还考虑了如何处理人员数量与任务数量不相等的情形的指派问题;最后,通过一个实例分析说明了本文给出方法的可行性和有效性。本文的方法丰富了已有的求解方法,具有实际应用价值。     

Clustering of search trajectory and its application to parameter tuning

This paper is concerned with automated classification of Combinatorial Optimization Problem instances for instance-specific parameter tuning purpose. We propose the CluPaTra Framework, a generic approach to CLUster instances based on similar PAtterns according to search TRAjectories and apply it on parameter tuning. The key idea is to use the search trajectory as a generic feature for clustering problem instances. The advantage of using search trajectory is that it can be obtained from any local-search based algorithm with small additional computation time. We explore and compare two different search trajectory representations, two sequence alignment techniques (to calculate similarities) as well as two well-known clustering methods. We report experiment results on two classical problems: Travelling Salesman Problem and Quadratic Assignment Problem and industrial case study.     

A multi-level bottleneck assignment approach to the bus drivers' rostering problem

The problem of finding a work assignment for drivers in a given time horizon, in such a way as to have an even distribution of the workload, is considered. This problem is formulated as a Multi-level Bottleneck Assignment Problem (MBA). The MBA problem is studied: it is shown that it is NP-complete and an asymptotically optimal algorithm is presented. Some computational results are illustrated which prove the efficiency of the algorithm.     

An Approach to the Subproblem of the Cutting Angle Method of Global Optimization

The solution of the Subproblem of the Cutting Angle Method of Global Optimization for problems of minimizing increasing positively homogeneous of degree one functions is proved to be NP-Complete. For the proof of this fact we formulate another problem which we call “Dominating Subset with Minimal Weight”. This problem is also NP-Complete. An O(n²)-time algorithm is presented for approximate solution of Dominant Subset with Minimal Weight Problem. This problem can be expressed as a kind of Assignment Problem in which it is allowed to assign multiple tasks to a single processor. Experimental analysis of the algorithm is performed using the program implemented in ANSI-C. The results of the analysis show the efficiency of the proposed algorithm.Mathematics Subject Classification (2000): 65K05, 90C27, 68Q25     

The Multi-Story Space Assignment Problem

The Multi-Story Space Assignment Problem (MSAP) is an innovative formulation of the multi-story facility assignment problem that allows one to model the location of departments of unequal size within multi-story facilities as a Generalized Quadratic 3-dimensional Assignment Problem (GQ3AP). Not only can the MSAP generate the design of the location of the departments in the facility, the MSAP also includes the evacuation planning for the facility. The formulation, background mathematical development, and computational experience with a branch and bound algorithm for the MSAP are also presented.     

Generalized Assignment Type Goal Programming Problem: Application to Nurse Scheduling

The notion of the Generalized Assignment Type Goal Programming Problem is introduced to consider the additional side constraints of an Assignment Type problem as goal functions. A short term Tabu Search method together with diversification strategies are used to deal with this model. The methods are tested on real-world Nurse Scheduling Problems.     

Solution of the Cumulative Assignment Problem With a Well-Structured Tabu Search Method

The Cumulative Assignment Problem is an NP-complete problem obtained by substituting the linear objective function of the classic Linear Assignment Problem, with a non-linear cumulative function. In this paper we present a first attempt to solve the Cumulative Assignment Problem with metaheuristic techniques. In particular we consider two standard techniques, namely the Simulated Annealing and the Multi-Start methods, and we describe the eXploring Tabu Search: a new structured Tabu Search algorithm which uses an iterative multi-level approach to improve the search. The new method is analyzed through extensive computational experiments and proves to be more effective than the standard methods.     

The continuous grey pattern problem

A new location problem is formulated and solved. It is the continuous version of the grey pattern problem which is a special case of the Quadratic Assignment Problem. The problem is a minimization of a convex function subject to non-convex constraints and has infinitely many optimal solutions. We propose several mathematical programming formulations that are suitable for a multi-start heuristic algorithm. In addition to solving these formulations by the Solver in Excel and Mathematica, a special Nelder–Mead algorithm is proposed. This special algorithm provided the best results. One suggested modification may improve the performance of the Nelder–Mead algorithm for other optimization problems as well.     

Minimizing the span of d-walks to compute optimum frequency assignments

In this paper we deal with the Minimum Span Frequency Assignment Problem (MSFAP), that is the problem of assigning a limited set of radio frequencies to the base stations of a radio network so as the bandwidth occupancy is minimized and the overall interference is not too large. We present a new integer linear formulation for MSFAP in the multidemand case, which is the basis of an exact algorithm to compute both lower and upper bounds for MSFAP. Frequency assignments are represented as walks (sequence of nodes) in a graph. We look for a walk of minimum span, where the span of a walk is defined as the cost of a maximum cost subwalk (subsequence). The new approach is able to find optimum solutions over a large set of classical benchmarks. Received: July 10, 2000 / Accepted: July 6, 2001?Published online October 26, 2001     

Tabu Search for Frequency Assignment in Mobile Radio Networks

The main goal of the Frequency Assignment Problem in mobile radio networks consists of assigning a limited number of frequencies to each radio cell in a cellular network while minimizing electromagnetic interference due to the reuse of frequencies. This problem, known to be NP-hard, is of great importance in practice since better solutions will allow a telecommunications operator to manage larger cellular networks. This paper presents a new Tabu Search algorithm for this application. The algorithm is tested on realistic and large problem instances and compared with other methods based on simulated annealing, constraint programming and graph coloring algorithms. Empirical evidence shows that the Tabu algorithm is very competitive by giving the best solutions to the tested instances.     

分派问题的一个简单算法

本文给出了分派问题的一个新算法，这个算法是初等的，且便于使用和编程上机操作，尤其适合于较低阶分派问题．