分派问题的灵敏度分析及其应用

讨论分派问题的效率矩阵的元素发生变化时,对最优解的影响;在保持分派问题最优解不变的情况下,效率矩阵的元素的变化范围;及当分派问题的最优解发生变化后,如何用简单的方法求得新的最优解等.     

分派问题保持最优解不变的充分必要条件

进一步讨论了在保持分派问题最优解不变的情况下,效率矩阵元素的变化范围.这些变化范围是保持分派问题最优解不变的充要条件.     

分派问题的一个简单算法

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

超图中的着色问题

本文是近三十年来有关超图中涉及的着色问题的综述。它包含了有关超图着色中的基本结果,临界可着色性,２－可着色性,非２－可着色性以及在超图中与顶点着色、边着色和其它着色相关的极值问题。     

灰色分派问题及其应用

在分派问题中，总假设被分派工作的人（或机器等）做各项工作的效率（或所费时间）都是确定的值．但实际上．对于以往未做过的工作，或做过但情况变化较大的工作都难以定下确切的工作效率，而只能估计出一个大概的范围．这也就是说有些工作效率是有理灰数．我们把这一类分派问题称为灰色分派问题．木文给出了灰色分派问题有关定理的证明以及一个应用实例．     

工作分派问题的一种模糊决策模型

针对一类流水线式的工作分派问题,建立了在赋模糊权的二部图中求解模糊最大最小匹配的数学模型,给出了该模型的一个有效算法,并利用模糊决策思想得到了优化此类工作分派问题的一种决策方法     

着色李超代数与左着色对称结构

本文研究了着色李超代数上的左着色对称结构问题.利用着色李超代数的两种仿射表示和1-上同调群,得出左着色对称结构存在的几个充分或必要条件,推广了文[2]的结论.     

多重分派问题

系统分析了多重分派问题的线性规划模型的性质和特点，得到一个直接求解多重分派问题的算法，利用该算法来求解古典题，无需要求完全二部图，特别是求解过程不会受到已化解的影响。     

泊松着色代数

首先,给出了泊松着色代数的定义及构造泊松着色代数的一种方法,其次,证明了在张量积的运算下泊松着色代数是封闭的,最后,通过容许泊松着色代数及其上的非结合二元运算等价定义了泊松着色代数.     

关于图的全着色—一个综述

本文简要地综述了图的全着色的进展,给出了一些尚未解决的问题。     

A simple dual algorithm for the generalised assignment problem

A new algorithm for the generalised assignment problem is described in this paper. The dual-type algorithm uses a simple heuristic derived from a relaxation of the problem. The algorithm has been tested on generalised assignment problems of substantial size and compared to an exact integer programming approach and a well-established heuristic approach. Computational results look promising in terms of speed and solution quality.     

An Algorithm for the Generalized Assignment Problem with Special Ordered Sets

The generalized assignment problem (GAP), the 0–1 integer programming (IP) problem of assigning a set of n items to a set of m knapsacks, where each item must be assigned to exactly one knapsack and there are constraints on the availability of resources for item assignment, has been further generalized recently to include cases where items may be shared by a pair of adjacent knapsacks. This problem is termed the generalized assignment problem with special ordered sets of type 2 (GAPS2). For reasonably large values of m and n the NP-hard combinatorial problem GAPS2 becomes intractable for standard IP software, hence there is a need for the development of heuristic algorithms to solve such problems. It will be shown how a heuristic algorithm developed previously for the GAP problem can be modified and extended to solve GAPS2. Encouraging results, in terms of speed and accuracy, have been achieved.     

Probabilistic analysis of the generalised assignment problem

We analyse thegeneralised assignment problem under the assumption that all coefficients are drawn uniformly and independently from [0, 1]. We show that such problems can be solved exactly with high probability, in a well-defined sense. The results are closely related to earlier work of Lueker, Goldberg and Marchetti-Spaccamela and ourselves.Supported by NATO grant RG0088/89.Supported by NSF grant CCR-8900112 and NATO grant RG0088/89.     

The Robust Design with the Pole Assignment

ＴｈｅＲｏｂｕｓｔＤｅｓｉｇｎｗｉｔｈｔｈｅＰｏｌｅＡｓｓｉｇｎｍｅｎｔＺｈｏｕＱｉｎｇｑｕａｎ（周清泉）；ＷａｎｇＰｉｎｇ；（王平）；ＬｉｕＸｉａｎｘｉｎｇ（刘先省）Ａｂｓｔｒａｃｔ：Ｔｈｅｐｅｐｅｒｐｒｅｓｅｎｔｓｔｈｅｒｏｂｕｓｔｄｅｓｉｇｎｍ...     

A note on a polynomial time solvable case of the quadratic assignment problem

We identify a class of instances of the Koopmans–Beckmann form of the Quadratic Assignment Problem that are solvable in polynomial time. This class is characterized by a path structure in the flow data and a grid structure in the distance data. Chr18b, one of the test problems in the QAPLIB, is in this class even though this feature of it has not been noticed until now.     

On A Special Case of the Quadratic Assignment Problem with an Application to Storage-and-Retrieval Devices

In a storage-and-retrieval device, items are retrieved on demand from a storage bank by a picking mechanism. Many varieties of these robotic devices are in use in manufacturing, logistics and computer peripherals. In printed circuit board manufacturing, storage-and-retrieval is intertwined with component placement and product clustering. Under certain circumstances, the problem of assigning items by type to storage slots to minimize the expected retrieval time is a quadratic assignment problem. Although such models are very difficult to solve to optimality, an important special case considered here admits an easy solution, namely, the well known “organ pipe” arrangement of items.     

N×2N瓶颈指派问题及其阀门(threshold)算法

讨论把2N项任务(或工件)指派(安排)给N个人(或机器)的问题.已知人i处理(或加工)任务j的时间花费是cij,i=1,2,…,N,j=1,2,…,2N,要求每人恰承担2项任务,每项任务恰由1个人承担.怎样分派任务,使完成任务最慢的人所花的时间最少.     

A note on the inclusion of the kernel in the core of the bilateral assignment game

In this note we prove that the kernel of a bilateral assignment game is always included in the core. This solves an outstanding open problem for bilateral assignment games. Received January 1997/Final version June 1997     

A note on the nucleolus and the kernel of the assignment game

There exist coalitional games with transferable utility which have the same core but different nucleoli. We show that this cannot happen in the case of assignment games. Whenever two assignment games have the same core, their nucleoli also coincide. To show this, we prove that the nucleolus of an assignment game coincides with that of its buyer–seller exact representative.I am grateful to C. Rafels and to the referees for their comments. Institutional support from research grants BEC 2002-00642 and SGR2001–0029 is also acknowledged.     

Random assignment problems

Analysis of random instances of optimization problems provides valuable insights into the behavior and properties of problem’s solutions, feasible region, and optimal values, especially in large-scale cases. A class of problems that have been studied extensively in the literature using the methods of probabilistic analysis is represented by the assignment problems, and many important problems in operations research and computer science can be formulated as assignment problems. This paper presents an overview of the recent results and developments in the area of probabilistic assignment problems, including the linear and multidimensional assignment problems, quadratic assignment problem, etc.