Intelligent scheduling with tabu search: An application to jobs with linear delay penalties and sequence-dependent setup costs and times

In this article we study thetabu search (TS) method in an application for solving an important class of scheduling problems. Tabu search is characterized by integrating artificial intelligence and optimization principles, with particular emphasis on exploiting flexible memory structures, to yield a highly effective solution procedure. We first discuss the problem of minimizing the sum of the setup costs and linear delay penalties when N jobs, arriving at time zero, are to be scheduled for sequential processing on a continuously available machine. A prototype TS method is developed for this problem using the common approach of exchanging the position of two jobs to transform one schedule into another. A more powerful method is then developed that employs insert moves in combination with swap moves to search the solution space. This method and the best parameters found for it during the preliminary experimentation with the prototype procedure are used to obtain solutions to a more complex problem that considers setup times in addition to setup costs. In this case, our procedure succeeded in finding optimal solutions to all problems for which these solutions are known and a better solution to a larger problem for which optimizing procedures exceeded a specified time limit (branch and bound) or reached a memory overflow (branch and bound/dynamic programming) before normal termination. These experiments confirm not only the effectiveness but also the robustness of the TS method, in terms of the solution quality obtained with a common set of parameter choices for two related but different problems.     

Optimal search for signals in a multichannel system: Arbitrary initial distribution in state space merging scheme

Markovian and semi-Markovian random processes are used to analyze the problem of optimal search for signals in a multichannel communication system with arbitrarily distributed random outputs. The search efficiency factor is found in explicit form based on state space merging, and a mathematical programming problem is set up to find a numerical suboptimal solution. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 144–150, May–June 2007.     

Cubic Bézier approximation of a digitized curve

In this paper we present an efficient technique for piecewise cubic Bézier approximation of digitized curve. An adaptive breakpoint detection method divides a digital curve into a number of segments and each segment is approximated by a cubic Bézier curve so that the approximation error is minimized. Initial approximated Bézier control points for each of the segments are obtained by interpolation technique i.e. by the reverse recursion of De Castaljau's algorithm. Two methods, two-dimensional logarithmic search algorithm (TDLSA) and an evolutionary search algorithm (ESA), are introduced to find the best-fit Bézier control points from the approximate interpolated control points. ESA based refinement is proved to be better experimentally. Experimental results show that Bézier approximation of a digitized curve is much more accurate and uses less number of points compared to other approximation techniques.     

Metaheuristic downhill simplex method in combinatorial optimization

The concept of combinatorial objects is formalized. It allows strict definition of a combinatorial optimization problem (COP). An efficient metaheuristic method to solve COPs (H-method) is considered. It includes stochastic local search algorithms as a built-in procedure. A parallel implementation of the H-method is set forth and analyzed. The results from a numerical experiment and solution of some well-known COPs on personal computers and on the SKIT cluster supercomputer are presented. The study was supported by INTAS (Project 06-1000017-8909). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 70–79, November–December 2007.     

关于随机集值映象的不动点定理

我们得到几个随机集值映象的不动点定理，它推广了Ｍ．Ｓ．Ｋｈａｍ的结果［５］，文中所使用的方法与其它作者不同     

钻削中产生迷切现象的机理研究

随着科学技术的发展．对孔加工精度的要求越来越高．钻削过程中的速切现象对孔加工的形状精度、位置精度有很大的影响．本文用试验、观察、解析的方法分析了钻头迷切现象与各种因素的关系，对提高孔加工精度有了新的揭示．     

以数字搜索树表示的二值图象的几何变换

本文介绍以数字搜索树表示的二值图象的一种几何变换算法，文中讨论了四分区与正四边区的基本关系，输出ＤＳＴ结点成立的充分条件，给出了完整的几何变换算法并对算法的复杂性作了分析。     

基于Matlab的线性规划问题求解

线性规划是运筹学中研究较早、发展较快、应用广泛、方法成熟的一个重要分支,它是辅助人们进行科学管理的一种重要的数学方法.文章首先介绍了线性规划的基本概念及标准形式,着重讨论了线性规划问题的三种常用解法:单纯形法、直接搜索法以及遗传算法,最后在Matlab R2009a环境下进行了仿真.通过结果可以看出,用Matlab求解线性规划问题,可以避免手工的烦琐计算,大大地提高工作效率和结果的准确性.     

Intranet搜索引擎设计与实现

随着企业内部网络应用的深入,Intranet内部的信息资源越来越庞大,怎样为这些数据信息构建索引是我们面If缶的主要任务,而全文检索的产生解决了这一问题。目前越来越多的中小企业采用Linux系统作为Web平台,并且利用检索系统来管理内部繁多的文本和HTML文件。文章对www搜索引擎的全文检索及其相关技术进行了分析和讨论,实现了一个基于Linux环境的Intranet搜索引擎LISE（Linux Intranet Search Engine）。LISE利用了基于词表的索引方法,为用户提供了更加准确的信息,能满足多种中小企业用户的需求。