单台机以总完工时间为目标的批排序问题

研究单台机,工件加工时间相等,大小不同的批排序问题,给出了一个最坏情况界为9+3~(1/2)/6≈1.7817的多项式时间近似算法,并证明了即使工件总大小不超过2,该问题也不存在FPTAS,除非P=NP.     

带服务器的三台平行机排序问题的复杂性和近似算法

讨论带有两具服务器的三台机的平行机排序问题,在这个问题的实例中,每一个工件都有一个时间长度 安装操作必须要由服务器来完成,每一个服务器在同一时刻只能安装一个工件,用三段式描述表示此问题即为Ｐ３,Ｓ２／ｓｉ＝１／Ｃｍａｘ,证明了此问题为ＮＰ－Ｃ的,分别给出了在在线和离线条件下的近似算法,并且估计了算法的最坏情况界。     

组合优化若干经典问题新进展

组合优化是20世纪中后期发展起来的一个运筹学与计算机科学交叉学科分支, 研究具有离散结构的优化问题解的性质和求解方法. 由于不同离散问题的结构差异, 出现了各种各样的研究手段和技巧. 针对组合优化的若干经典问题, 简述了算法和复杂性理论的研究进展.     

两台可拒绝同类机在线排序问题近似算法的参数性能比

讨论两台可拒绝同类机在线排序问题的近似算法。设两台机器的速度之比为ｓ（≥１）。工件逐个到位,可以被加工,也可以被拒绝,但要付出相应的罚值ｐｊ。并且只有在安排完当前工件之后,下一个工件才到达。目标函数要求被加工工件集的最迟工件完工时间与被拒绝工件集的总罚值之和达到最小。文中设计出线性时间的ＲＬＳ（α）算法,并证明了其关于ｓ的参数紧界,这个界于ｓ＝１以及ｓ≥（５＋１）／２均是不可改进的。     

工件可拒绝排序问题综述

可拒绝排序问题是兴起于2000年前后的有代表性、应用背景极强的的排序问题,是经典排序问题的衍生和推广.经典排序问题总是要求每个工件必须被加工,然而在实际中由于某些特殊原因,决策者会选择拒绝加工某些工件.把允许工件被拒绝的这类问题称为工件可拒绝排序问题,有的文献称之为外包的排序问题.这些问题不仅具有很强的应用价值,在理论上也有重要的意义.近年来该领域受到越来越广泛的关注,新的研究成果不断涌现.现就离线、在线情况下的可拒绝排序问题的进展情况作了全面介绍,展示了已有的研究成果和新的问题,给出了此方面的比较重要的参考文献,旨在帮助感兴趣的读者迅速了解问题研究的进展并由此进入此研究领域的前沿.     

箱覆盖问题的半定松驰算法

箱覆盖问题是NP困难问题中的经典问题，得到了广泛地研究，九十年代以来，半定松驰策略被用来求解组合优化问题，取得了很好的结果[13]，本文首次给箱覆盖问题的半定松驰算法，算法的理论分析结果表明它适合于求解大规模的箱覆盖问题。     

多专用机的两组工件的P／／C_（max）问题

本文对具有多台专用机与通用机的两组工件的Ｐ     

带机器准备时间的平行机在线与半在线排序

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。     

一类广义分式规划问题的完全多项式时间近似算法

本文对一类广义分式规划问题,提出一种求其全局最优解的完全多项式时间近似算法,给出该算法的理论分析和计算复杂性,通过数值算例验证该算法是有效可行的.     

一类特殊的分式规划问题的ε-近似算法

本文针对一类特殊的分式规划问题基于网格搜索提出了一个求其全局最优解的算法,且从理论上证明了算法的收敛性与计算复杂性,通过算例验证了算法的可行性与有效性.     

An evolutionary algorithm for the vehicle routing problem with route balancing

In this paper, we address a bi-objective vehicle routing problem in which the total length of routes is minimized as well as the balance of routes, i.e. the difference between the maximal route length and the minimal route length. We propose a meta-heuristic method based on an evolutionary algorithm involving classical multi-objective operators. To improve its efficiency, two mechanisms, which favor the diversification of the search, have been added. First, an elitist diversification mechanism is used in cooperation with classical diversification methodologies. Second, a parallel model designed to take into account the elitist diversification is proposed. Our method is tested on standard benchmarks for the vehicle routing problem. The contribution of the introduced mechanisms is evaluated by different performance metrics. All the experimentations indicate a strict improvement of the generated Pareto set.     

A note on the precedence-constrained class sequencing problem

We give a short proof of a result of Tovey [Non-approximability of precedence-constrained sequencing to minimize setups, Discrete Appl. Math. 134:351-360, 2004] on the inapproximability of a scheduling problem known as precedence-constrained class sequencing. In addition, we present an approximation algorithm with performance guarantee (c+1)/2, where c is the number of colors. This improves upon Tovey's c-approximation.     

Equilibria in load balancing games

A Nash equilibrium （NE） in a multi-agent game is a strategy profile that is resilient to unilateral deviations. A strong Nash equilibrium （SE） is one that is stable against coordinated deviations of any coalition. We show that, in the load balancing games, NEs approximate SEs in the sense that the benefit of each member of any coalition from coordinated deviations is well limited. Furthermore, we show that an easily recognizable special subset of NEs exhibit even better approximation of SEs.     

限制性多源点偏心距增广问题

给定一个赋权图$G=（V,E;w,c）$以及图$G$的一个支撑子图$G_{1}=（V,E_{1}）$,这里源点集合$S=\{s_{1},s_{2},\cdots,s_{k}\}\subseteq V$,权重函数$w：E\rightarrow\mathbb{R}^{+}$,费用函数$c：E\setminus E_{1}\rightarrow\mathbb{Z}^{+}$和一个正整数$B$,本文考虑两类限制性多源点偏心距增广问题,具体叙述如下：（1）限制性多源点最小偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最小值达到最小;（2）限制性多源点最大偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。     

限制性多源点偏心距增广问题

给定一个赋权图$G=（V,E;w,c）$以及图$G$的一个支撑子图$G_{1}=（V,E_{1}）$,这里源点集合$S=\{s_{1},s_{2},\cdots,s_{k}\}\subseteq V$,权重函数$w：E\rightarrow\mathbb{R}^{+}$,费用函数$c：E\setminus E_{1}\rightarrow\mathbb{Z}^{+}$和一个正整数$B$,本文考虑两类限制性多源点偏心距增广问题,具体叙述如下：（1）限制性多源点最小偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最小值达到最小;（2）限制性多源点最大偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。     

A new algorithm for the solution of the linear minimax approximation problem

This paper introduces an efficient approach to the solution of the linear mini-max approximation problem. The classical nonlinear minimax problem is cast into a linear formulation. The proposed optimization procedure consists of specifying first a feasible point belonging to the feasible boundary surface. Next, feasible directions of decreasing values of the objective function are determined. The algorithm proceeds iteratively and terminates when the absolute minimum value of the objective function is reached. The initial point May be selected arbitrarily or it May be optimally determined through a linear method to speed up algorithmic convergence. The algorithm was applied to a number of approximation problems and results were compared to those derived using the revised simplex method. The new algorithm is shown to speed up the problem solution by at least on order of magnitude.     

An iterative rounding 2-approximation algorithm for the k-partial vertex cover problem

We study a generalization of the vertex cover problem. For a given graph with weights on the vertices and an integer k, we aim to find a subset of the vertices with minimum total weight, so that at least k edges in the graph are covered. The problem is called the k-partial vertex cover problem. There are some 2-approximation algorithms for the problem. In the paper we do not improve on the approximation ratios of the previous algorithms, but we derive an iterative rounding algorithm. We present our technique in two algorithms. The first is an iterative rounding algorithm and gives a （2 ＋ Q/OPT ）-approximation for the k-partial vertex cover problem where Q is the largest finite weight in the problem definition and OPT is the optimal value for the instance. The second algorithm uses the first as a subroutine and achieves an approximation ratio of 2.     

考虑常数客户批运输的单机排序问题

本文考虑工件首先在单机上加工,完工的工件由一辆容量有限的车配送到指定客户的模型,目标是最小化makespan。对于工件物理大小相同的情况,我们考虑了常数个客户的情形,并且给出了一个多项式时间的动态规划算法。对于工件物理大小不同的情况,我们讨论了一类特殊的三个客户的情形,并给出了一个2-近似算法。     

Constraint Handling in Genetic Algorithms: The Set Partitioning Problem

In this paper we present a genetic algorithm-based heuristic for solving the set partitioning problem (SPP). The SPP is an important combinatorial optimisation problem used by many airlines as a mathematical model for flight crew scheduling.A key feature of the SPP is that it is a highly constrained problem, all constraints being equalities. New genetic algorithm (GA) components: separate fitness and unfitness scores, adaptive mutation, matching selection and ranking replacement, are introduced to enable a GA to effectively handle such constraints. These components are generalisable to any GA for constrained problems.We present a steady-state GA in conjunction with a specialised heuristic improvement operator for solving the SPP. The performance of our algorithm is evaluated on a large set of real-world problems. Computational results show that the genetic algorithm-based heuristic is capable of producing high-quality solutions.