A new heuristic algorithm solving the linear ordering problem

The linear ordering problem is an NP-hard combinatorial problem with a large number of applications. Contrary to another very popular problem from the same category, the traveling salesman problem, relatively little space in the literature has been devoted to the linear ordering problem so far. This is particularly true for the question of developing good heuristic algorithms solving this problem.In the paper we propose a new heuristic algorithm solving the linear ordering problem. In this algorithm we made use of the sorting through insertion pattern as well as of the operation of permutation reversal. The surprisingly positive effect of the reversal operation, justified in part theoretically and confirmed in computational examples, seems to be the result of a unique property of the problem, called in the paper the symmetry of the linear ordering problem. This property consists in the fact that if a given permutation is an optimal solution of the problem with the criterion function being maximized, then the reversed permutation is a solution of the problem with the same criterion function being minimized.     

Multivariate approximation in the worst case setting over reproducing kernel Hilbert spaces

We study the worst case setting for approximation of d variate functions from a general reproducing kernel Hilbert space with the error measured in the L_∞ norm. We mainly consider algorithms that use n arbitrary continuous linear functionals. We look for algorithms with the minimal worst case errors and for their rates of convergence as n goes to infinity. Algorithms using n function values will be analyzed in a forthcoming paper.We show that the L_∞ approximation problem in the worst case setting is related to the weighted L₂ approximation problem in the average case setting with respect to a zero-mean Gaussian stochastic process whose covariance function is the same as the reproducing kernel of the Hilbert space. This relation enables us to find optimal algorithms and their rates of convergence for the weighted Korobov space with an arbitrary smoothness parameter α>1, and for the weighted Sobolev space whose reproducing kernel corresponds to the Wiener sheet measure. The optimal convergence rates are n^-(α-1)/2 and n^-1/2, respectively.We also study tractability of L_∞ approximation for the absolute and normalized error criteria, i.e., how the minimal worst case errors depend on the number of variables, d, especially when d is arbitrarily large. We provide necessary and sufficient conditions on tractability of L_∞ approximation in terms of tractability conditions of the weighted L₂ approximation in the average case setting. In particular, tractability holds in weighted Korobov and Sobolev spaces only for weights tending sufficiently fast to zero and does not hold for the classical unweighted spaces.     

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.     

Uniform machine scheduling with machine available constraints

1.IntroductionIntheclassicalparallelmachineschedulingareaweassumethatmachinesarealwaysavailable.However,aspointedin[1],inrealindustrysettingsthisassumptionmaynotbetrue.Forexample,machinesmaynotalwaysbeavailablebecauseoftheirpreventivemaintenanceduringtheschedulingperiod.Thatistosay,eachmachineiisunavailablefromsibuntilrib(05sib5rib),where0SkSm,withmbeingthenumberofunavailabilityperiodsformachineiduringtheplanninghorizon.Inotherwords,somepapersstatethatmachinesareavailableintimewindows,whichi…     

Q2‖Cmax的对偶近似算法

本文讨论两台同类平行机排序问题,首先给出Ｍｕｌｔｉｆｉｔ算法在不同迭代初值下的紧界,然后利用一个新设计的对偶贪婪子过程构造出线性时间６／５－复合近似算法。     

On the worst scenario method: A modified convergence theorem and its application to an uncertain differential equation

We propose a theoretical framework for solving a class of worst scenario problems. The existence of the worst scenario is proved through the convergence of a sequence of approximate worst scenarios. The main convergence theorem modifies and corrects the relevant results already published in literature. The theoretical framework is applied to a particular problem with an uncertain boundary value problem for a nonlinear ordinary differential equation with an uncertain coefficient. This research was supported in part by the project MSM4781305904 from the Ministry of Education, Youth and Sports of the Czech Republic.     

A hybrid heuristic for the maximum clique problem

In this paper we present a heuristic based steady-state genetic algorithm for the maximum clique problem. The steady-state genetic algorithm generates cliques, which are then extended into maximal cliques by the heuristic. We compare our algorithm with three best evolutionary approaches and the overall best approach, which is non-evolutionary, for the maximum clique problem and find that our algorithm outperforms all the three evolutionary approaches in terms of best and average clique sizes found on majority of DIMACS benchmark instances. However, the obtained results are much inferior to those obtained with the best approach for the maximum clique problem.     

堆取料机调度问题的一个近似算法

研究源自煤炭港口料场管理的堆取料机调度问题.该问题中,堆取料机从长为L的料场作业区最左端开始空机或载料运行,两者的速度之比为s：1（s ≥ 1）.决策者需确定储料堆在作业区的分布以及堆取料机处理它们的先后次序,目的是极小化一批煤料运输船的在港服务时间.考虑堆取料机处理完毕需要回到料场终端的作业模型,证明了存在最坏情况界不超过1+1/4s的近似算法.     

可转包两台流水作业机排序的近似算法

研究可转包的两台流水作业机排序问题, 目标是极小化最大完工时间和总外包费用之和. 首先给出最坏情况界为2的近似算法, 接着对工件满足有序化约束的情形给出最坏情况界为frac{3}{2}的改进算法, 以上算法界均为紧界.     

An Efficient Algorithm for the Knapsack Sharing Problem

The Knapsack Sharing Problem (KSP) is an NP-Hard combinatorial optimization problem, admitted in numerous real world applications. In the KSP, we have a knapsack of capacity c and a set of n objects, namely N, where each object j, j = 1,...,n, is associated with a profit p _j and a weight w _j. The set of objects N is composed of m different classes of objects J _i, i = 1,...,m, and N = ^m _i=1 J _i. The aim is to determine a subset of objects to be included in the knapsack that realizes a max-min value over all classes.In this article, we solve the KSP using an approximate solution method based upon tabu search. First, we describe a simple local search in which a depthparameter and a tabu list are used. Next, we enhance the algorithm by introducing some intensifying and diversifying strategies. The two versions of the algorithm yield satisfactory results within reasonable computational time. Extensive computational testing on problem instances taken from the literature shows the effectiveness of the proposed approach.     

Parallel machine covering with limited number of preemptions简

In this paper,we investigate the i-preemptive scheduling on parallel machines to maximize the minimum machine completion time,i.e.,machine covering problem with limited number of preemptions. It is aimed to obtain the worst case ratio of the objective value of the optimal schedule with unlimited preemptions and that of the schedule allowed to be preempted at most i times. For the m identical machines case,we show the worst case ratio is 2m.i.1 m,and we present a polynomial time algorithm which can guarantee the ratio for any 0 ≤ i ≤ m. 1. For the i-preemptive scheduling on two uniform machines case,we only need to consider the cases of i = 0 and i = 1. For both cases,we present two linear time algorithms and obtain the worst case ratios with respect to s,i.e.,the ratio of the speeds of two machines.     

一种新的两道工序柔性流水车间排序问题

本文针对F_2(p),h11.1|m_1=1,m_2=μ≥2|C_(max)这一问题给出了几种近似算法,并对每种近似算法进行了最坏情形分析,给出了最坏情形界.     

A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting

In this paper, a dynamic programming-based recursive method is proposed for solving an unconstrained 2D rectangular cutting problem. The algorithm is an incomplete method, in which some intricate cutting patterns may not be obtained. The worst case performance of the algorithm is evaluated and some theoretical analyses for the algorithm are performed. Compared to traditional dynamic programming, this algorithm gives a high percentage of optimal solutions (94.84%, 86.67% and 77.83% for small, medium and large sized unweighted instances, 99.67%, 99.50% and 97.00% for small, medium and large sized weighted instances) but features a far lower computational complexity. Computational results are also presented for some known benchmarks.     

Improving port performance in developing countries—A case study

Exchange algorithms are an important class of heuristics for hard combinatorial optimization problems as, e.g., salesman problems or quadratic assignment problems. In Kirkpatrick's and Cerny's exchange algorithms for the travelling salesman problem and placement problem they propose to perform an exchange not only if the objective function value decreases by this exchange, but also in certain cases if the objective function value increases. An exchange increasing the objective function value is performed stochastically depending on the size of the increment.Computational tests with quadratic assignment problems revealed an excellent behaviour in such an approach. Suboptimal solutions differing 1–2% from the best known solutions are obtained by a simple program in short time. By starting this program several times with different starting values all known minimal objective function values were reached. Thus this approach is well suited also for smaller computers and leads in short time to acceptable solutions.     

Upper bounds for the homogeneous case of a two-dimensional packing problem

A method for determining an upper bound for the homogeneous case of a two-dimensional packing problem is presented in this paper. It is based on an analysis of the problem's structure and can be evaluated as the optimal solution of a non-convex minimization problem which can be transformed to a piecewise linear problem by using its special properties. Finally a comparative analysis of solution quality and time complexity is presented.

---

Zusammenfassung In dieser Arbeit wird ein Verfahren zur Bestimmung oberer Schranken für ein homogenes zweidimensionales Packproblem vorgestellt. Auf der Grundlage von Analysen der Problemstruktur kann man eine obere Schranke als optimale Lösung eines nichtkonvexen Minimierungsproblems ermitteln, das unter Ausnutzung spezieller Eigenschaften in ein stückweise lineares Problem transformiert werden kann. Den Abschluß dieser Arbeit bildet eine vergleichende Analyse von Lösungsqualität und Rechenzeitbedarf.

     

Convergence of a stochastic approximation algorithm for the GI/G/1 queue using infinitesimal perturbation analysis

Discrete-event systems to which the technique of infinitesimal perturbation analysis (IPA) is applicable are natural candidates for optimization via a Robbins-Monro type stochastic approximation algorithm. We establish a simple framework for single-run optimization of systems with regenerative structure. The main idea is to convert the original problem into one in which unbiased estimators can be derived from strongly consistent IPA gradient estimators. Standard stochastic approximation results can then be applied. In particular, we consider the GI/G/1 queue, for which IPA gives strongly consistent estimators for the derivative of the mean system time. Convergence (w.p.1) proofs for the problem of minimizing the mean system time with respect to a scalar service time parameter are presented.