Resource assignment with preference conditions

This paper deals with a modification of the standard assignment problem, where subsets of resources express preferences in being, or not being, assigned together to the same activity. The problem arises in several real settings, among which the job assignment of the crew personnel of an airline company. We provide an integer programming formulation for both the Split Preference Problem, where couples of assignees do not want to work together, and for the Join Preference Problem, where, oppositely, couples of assignees want to work together. The mathematical nature of the two problems is indeed different, as for the first one it is possible to determine a minimum cost flow formulation on a suitable graph, and thus a polynomial time algorithm, while for the second one we face a NP-hard problem and device some heuristic solution approaches. Experimental tests conducted on instances of variable size confirm the effectiveness of the models and of the algorithms proposed.     

A new pivot selection rule for the network simplex algorithm

We present a new network simplex pivot selection rule, which we call theminimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks withn nodes,m arcs, integral arc capacities and integral supplies/demands of nodes. We define a {0, 1}-valued penalty for each arc of the network. The minimum ratio pivot rule is to select that eligible arc as the entering arc whose addition to the basis creates a cycle with the minimum cost-to-penalty ratio. We show that the so-defined primal network simplex algorithm solves minimum cost flow problem within O(nΔ) pivots and in O(Δ(m + n logn)) time, whereΔ is any upper bound on the sum of all arc flows in every feasible flow. For assignment and shortest path problems, our algorithm runs in O(n ²) pivots and O(nm +n ² logn) time.     

任务数多于人数的指派问题

本文给出任务数多于人数指派问题的两种解决方法。     

Optimal single machine scheduling of products with components and changeover cost

We consider the problem of scheduling products with components on a single machine, where changeovers incur fixed costs. The objective is to minimize the weighted sum of total flow time and changeover cost. We provide properties of optimal solutions and develop an explicit characterization of optimal sequences, while showing that this characterization has recurrent properties. Our structural results have interesting implications for practitioners, primarily that the structure of optimal sequences is robust to changes in demand.     

Random linear programs with many variables and few constraints

We extend and simplify Smale's work on the expected number of pivots for a linear program with many variables and few constraints. Our analysis applies to new versions of the simplex algorithm and to new random distributions.     

分派问题的一个简单算法

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

Persistency in the assignment and transportation problems

LetG = (U,V,E) be a bipartite graph with weights of its edgesc _ij . For the assignment and transportation problem given by such a graph we propose efficient procedures for partitioning the edge setE into three classes:E _o is the set of edgesij withx _ij = 0 for each optimum solution (0-persistent edges);E ₁ is the set of edges withx _ij > 0 and constant for each optimum (1-persistent edges) andE _w is the set of edges such that there are two optimum solutions x, x withx _ij x _ij ¹ (weakly persistent edges).     

一类最优指派问题的动态规划模型

考虑一类指派问题：欲指派m个人去做n项工作(m≥n)，要求每个人只做一项工作，第j项工作可以由b_j个人共同去做，其中，b_j(b_j≥1)是待求的未知数，j=1,2,…,n,满足．假定已知第i人做第j项工作的效益为c_ij≥0,i=1,2,…m;j=1,2,…,n.本文建立了求解上述问题最优指派（即使总的效益最大)的动态规划模型．     

单机排序问题的数学规划表示

本文把单机排序问题1||∑wjCj表述成一个二次规划,并把不带权的问题1||∑Cj进一步转化成指派问题,从而用指派问题的匈牙利算法证明SPT序是问题1||∑Cj的最优解,这个结论似乎很平凡,但对于用数学规划来研究排序问题是一个很有意义的进展,这为我们用二次规划和半定规划来研究NP困难的排序问题的近似算法打下基础。     

How ∗ not ∗ to solve a Sudoku

We prove the NP-hardness of a consistency checking problem that arises in certain elimination strategies for solving Sudoku-type problems.     

多车场多车型车辆调度问题及其遗传算法

研究多车场多车型车辆调度问题,建立了一种基于最小配送费用的数学模型,模型的配送费用在考虑基本运输费的基础上又引入了司机的工资支出,包括基本工资和加班费.在多车场多车型车辆调度模型中,一辆车可以为多个客户服务,但一个客户只能由一辆车提供服务.根据模型的这些特点,提出了一种新的染色体混合编码方案和遗传操作策略,从而借助遗传算法成功实现了模型的求解.数值仿真结果验证了算法的可行性.     

Group automorphisms with few and with many periodic points

For each a compact group automorphism is constructed with the property that

This may be interpreted as a combinatorial analogue of the (still open) problem of whether compact group automorphisms with any given topological entropy exist.

     

Elitist genetic algorithm for assignment problem with imprecise goal

The objective of this research paper is to solve a generalized assignment problem with imprecise cost(s)/time(s) instead of precise one by elitist genetic algorithm (GA). Here, the impreciseness of cost(s)/time(s) has been represented by interval valued numbers, as interval valued numbers are the best representation than others like random variable representation with a known probability distribution and fuzzy representation. To solve these types of problems, an elitist GA has been developed with interval valued fitness function. In this developed GA, the existing ideas about the order relations of interval valued numbers have been modified from the point of view of two types of decision making viz., optimistic decision making and pessimistic decision making. This modified approach has been used in the selection process for selecting better chromosomes/individuals for the next generation and in finding the best as well as the worst chromosomes/individuals in each generation. Here two new crossover schemes and two new mutation schemes have been introduced. In order to maintain the feasibility with crossover operations, a repair algorithm has been suggested. Extensive comparative computational studies based on different parameters of our developed algorithm on one illustrative example have also been reported.     

Finding all essential terms of a characteristic maxpolynomial

Let us denote ab=max(a,b) and ab=a+b for and extend this pair of operations to matrices and vectors in the same way as in linear algebra. We present an O(n²(m+n log n)) algorithm for finding all essential terms of the max-algebraic characteristic polynomial of an n×n matrix over with m finite elements. In the cases when all terms are essential, this algorithm also solves the following problem: Given an n×n matrix A and k{1,…,n}, find a k×k principal submatrix of A whose assignment problem value is maximum.     

依赖机器的两台机自由作业排序问题

文章研究加工时间仅依赖于机器的两台机自由作业排序问题 O2 | pij = pi, p2 < p1 < 2p2, Non-Idle | ΣCj。项思明和唐国春(1998)证明了可将该问题转化成指派问题。俞文ci 和应刚(1998)给出了这一问题的显式解,并用较长的篇幅证明其显式解的正确性;他们还举例说明所给出的显式最优排序并不排除其他形式的最优解的存在;但他们未说明所给出的显式解何时才是唯一最优解。本文将给出问题 O2 | pij = pi, p2 < p1 < 2p2, Non-Idle | ΣCj的显式解的直观的最优性证明,并讨论问题显式解何时是唯一的最优解。     

Scheduling with step-improving processing times

We consider the scheduling problem of minimizing the makespan on a single machine with step-improving job processing times around a common critical date. For this problem we give an NP-hardness proof, a fast pseudo-polynomial time algorithm, an FPTAS, and an on-line algorithm with best possible competitive ratio.     

带学习效应和资源依赖的单机排序模型

在工业生产中,随着员工操作技能的熟练程度的增加,对于相同的任务越往后加工,所花的时间将会减少。 同时,为了尽早完工,管理者也会考虑给加工工件分配一定量的额外资源来缩短工件加工时间。 本文基于以上实例,讨论了工件的实际加工时间既具有学习效应又依赖所分配资源的单机排序问题。 在问题中,假设工件的学习效应是之前已加工工件正常加工时间和的指数函数。 同时随着分配给工件资源量的增加,工件的实际加工时间呈线性减少,所需费用呈线性增加。对这一排序模型,主要探讨以下五个目标函数:最小化最大完工时间与资源消耗量总费用的和;最小化总完工时间与资源消耗量总费用的和;最小化加权总完工时间与资源消耗量总费用的和;最小化总提前、总延误、总共同交货期与资源消耗量总费用的和以及最小化总提前、总延误、总松弛交货期与资源消耗量总费用的和。 本文对前三个目标函数相应的排序问题给出了多项式时间可求解的算法。 对后两个目标函数所涉及的排序问题借助于指派问题分别给出了时间复杂性为O(n³)的算法。     

On the robust assignment problem under a fixed number of cost scenarios

We investigate the complexity of the min-max assignment problem under a fixed number of scenarios. We prove that this problem is polynomial-time equivalent to the exact perfect matching problem in bipartite graphs, an infamous combinatorial optimization problem of unknown computational complexity.     

A comment on “An extended assignment problem considering multiple inputs and outputs”

This note shows that the data envelopment analysis (DEA) models formulated by Chen and Lu [L.H. Chen, H.W. Lu, An extended assignment problem considering multiple inputs and outputs, Appl. Math. Modell. 31 (2007) 2239–2248] are not correct. The enveloping form of the Chen and Lu formulation is studied and a simple example is presented to demonstrate the differences between the efficiency scores resulted of the Chen and Lu formulation, and the true ones.     

自由作业环境下的供应链排序问题

本文研究自由作业环境下的供应链排序问题,研究供应链的上游如何安排工件在自由作业机器上加工,把加工完毕的工件分批发送给下游,使得生产排序费用和发送费用总和最少.这里,生产排序费用是用工件送到时间的函数来表示;发送费用是由发送的固定费用和与运输路径有关的变化费用所组成.本文研究以工件最大送到时间为生产排序费用的自由作业供应链排序问题,在指出问题的NP困难性后,用动态规划算法构造多项式时间近似算法,并分析算法的性能比.本文最后还对特殊情形进行了讨论.