A Review of On-Line Machine Scheduling:Algorithms and Competitiveness

在过去的十年里，在线算法的研究吸引了广泛的兴趣．本文对在排序和时间表问题中的各种有效的在线算法以及它们的竞争度作一综述．

Line-feature-based SLAM Algorithm

A line-feature based SLAM algorithm is presented in this paper to resolve the conflict between the requirements of computational complexity and information-richness within the point-feature based SLAM algorithm, All operations required for building and maintaining the map, such as model-setting, data association, and state-updating, are described and formulated. This approach has been programmed and successfully tested in the simulation work, and results are shown at the end of this paper.

Extraction of Laser Stripe Center Line Based on Genetic Algorithm and NURBS Interpolation

To improve the measurement accuracy of structured laser for inner surface dimensions of a deep hole, a new method to extract the laser stripe center line is proposed. An improved adaptive genetic algorithm that can converge rapidly and search the global optimum is used to determine the threshold for the laser stripe segmentation. And then NURBS interpolation which has a good local control capability is adopted to extract the laser stripe center line. Experiments show that the extracted laser stripe center line is stable and the diameter of the deep hole can be measured accurately.

The Line Clipping Algorithm Basing on Affine Transformation

A new algorithm for clipping line segments by a rectangular window on rectangular coordinate system is presented in this paper. The algorithm is very different to the other line clipping algorithms. For the line segments that cannot be identified as completely inside or outside the window by simple testings, this algorithm applies affine transformations (the shearing transformations) to the line segments and the window, and changes the slopes of the line segments and the shape of the window. Thus, it is clear for the line segment to be outside or inside of the window. If the line segments intersect the window, the algorithm immediately (no solving equations) gets the intersection points. Having applied the inverse transformations to the intersection points, the algorithm has the final results. The algorithm is successful to avoid the complex classifications and computations. Besides, the algorithm is effective to simplify the processes of finding the intersection points. Comparing to some classical algorithms, the algorithm of this paper is faster for clipping line segments and more efficient for calculations.

RECONFIGURABLE PRODUCTION LINE MODELING AND SCHEDULING USING PETRI NETS AND GENETIC ALGORITHM

In response to the production capacity and functionality variations, a genetic algorithm （GA） embedded with deterministic timed Petri nets（DTPN） for reconfigurable production line（RPL） is proposed to solve its scheduling problem. The basic DTPN modules are presented to model the corresponding variable structures in RPL, and then the scheduling model of the whole RPL is constructed. And in the scheduling algorithm, firing sequences of the Petri nets model are used as chromosomes, thus the selection, crossover, and mutation operator do not deal with the elements in the problem space, but the elements of Petri nets model. Accordingly, all the algorithms for GA operations embedded with Petri nets model are proposed. Moreover, the new weighted single-objective optimization based on reconfiguration cost and E/T is used. The results of a DC motor RPL scheduling suggest that the presented DTPN-GA scheduling algorithm has a significant impact on RPL scheduling, and provide obvious improvements over the conventional scheduling method in practice that meets duedate, minimizes reconfiguration cost, and enhances cost effectivity.

Self-adaptive PID controller of microwave drying rotary device tuning on-line by genetic algorithms

The control design, based on self-adaptive PID with genetic algorithms(GA) tuning on-line was investigated, for the temperature control of industrial microwave drying rotary device with the multi-layer(IMDRDWM) and with multivariable nonlinear interaction of microwave and materials. The conventional PID control strategy incorporated with optimization GA was put forward to maintain the optimum drying temperature in order to keep the moisture content below 1%, whose adaptation ability included the cost function of optimization GA according to the output change. Simulations on five different industrial process models and practical temperature process control system for selenium-enriched slag drying intensively by using IMDRDWM were carried out systematically, indicating the reliability and effectiveness of control design. The parameters of proposed control design are all on-line implemented without iterative predictive calculations, and the closed-loop system stability is guaranteed, which makes the developed scheme simpler in its synthesis and application, providing the practical guidelines for the control implementation and the parameter design.

Genetic Algorithm for Concurrent Balancing of Mixed-Model Assembly Lines with Original Task Times of Models

The growing global competition compels manufacturing organizations to engage themselves in all productivity improvement activities. In this direction, the consideration of mixed-model assembly line balancing problem and implementing in industries plays a major role in improving organizational productivity. In this paper, the mixed model assembly line balancing problem with deterministic task times is considered. The authors made an attempt to develop a genetic algorithm for realistic design of the mixed-model assembly line balancing problem. The design is made using the originnal task times of the models, which is a realistic approach. Then, it is compared with the generally perceived design of the mixed-model assembly line balancing problem.

Sequencing of Mixed Model Assembly Lines Based on Improved Shuffled Frog Leaping Algorithm

Shuffled frog leaping algorithm( SFLA) was used to solve multi-objective sequencing problem of mixed model assembly line( MMAL). Local convergence can be avoided and optimal solution can be obtained to a certain extent. However,the multi-objective sequencing problem of MMAL is an non-deterministic polynomial hard( NP-hard) problem and the shortcomings are slow convergence rate and low precision. To solve the shortcomings for optimization objectives of minimizing total utility time and keeping average consumption rate of parts, a chaos differential evolution SFLA( CDESFLA) is proposed in this study. Because SFLA is easy to fall into local optimum,the evolution operator of differential evolution algorithms is introduced in SFLA as a local search strategy,and differential mutation operator is introduced in chaotic sequence to prevent premature convergence. The examples show that the proposed CDESFLA is better for convergence accuracy than SFLA,genetic algorithm( GA) and particle swarm optimization( PSO)

基于Hessian矩阵的改进EDlines输电线识别算法

随着电力网络的飞速发展,采用无人机搭载高清摄像头来进行输电线巡检已成常态。为提高巡检的实时性和准确性,本研究提出了一种基于Hessian矩阵的改进EDlines输电线识别算法。首先,通过伽马变换对输电线图像进行预处理,利用Hessian矩阵特征值和特征向量以求取像素点主方向和主曲率,并获得输电线主体轮廓,从而摒弃了传统方法中梯度计算锚点和像素方向的繁琐步骤。接着,在主体轮廓基础上连接锚点以得到潜在直线线段像素链,并运用随机抽样一致性(RANSAC)算法来进行线段拟合。最后,根据直线间的距离和角度,迭代拟合以得到最终的输电线。实验结果表明,该方法能应对多种复杂环境下的输电线识别任务,抗干扰能力强,误检率显著降低,为高空输电线巡检提供了可靠的技术支持,具有重要的工程应用价值。

An Improved Line Search and Trust Region Algorithm

In this paper, we present a new line search and trust region algorithm for unconstrained optimization problems. The trust region center locates at somewhere in the negative gradient direction with the current best iterative point being on the boundary. By doing these, the trust region subproblems are constructed at a new way different with the traditional ones. Then, we test the efficiency of the new line search and trust region algorithm on some standard benchmarking. The computational results reveal that, for most test problems, the number of function and gradient calculations are reduced significantly.

Assembly Line Balancing Based on Double Chromosome Genetic Algorithm

Aiming at assembly line balancing problem,a double chromosome genetic algorithm(DCGA)is proposed to avoid trapping in local optimum,which is a disadvantage of standard genetic algorithm(SGA).In this algorithm,there are two chromosomes of each individual,and the better one,regarded as dominant chromosome,determines the fitness.Dominant chromosome keeps excellent gene segments to speed up the convergence,and recessive chromosome maintains population diversity to get better global search ability to avoid local optimal solution.When the amounts of chromosomes are equal,the population size of DCGA is half that of SGA,which significantly reduces evolutionary time.Finally,the effectiveness is verified by experiments.

Effective Hybrid Teaching-learning-based Optimization Algorithm for Balancing Two-sided Assembly Lines with Multiple Constraints

Due to the NP-hardness of the two-sided assembly line balancing （TALB） problem, multiple constraints existing in real applications are less studied, especially when one task is involved with several constraints. In this paper, an effective hybrid algorithm is proposed to address the TALB problem with multiple constraints （TALB-MC）. Considering the discrete attribute of TALB-MC and the continuous attribute of the standard teaching-learning-based optimization （TLBO） algorithm, the random-keys method is hired in task permutation representation, for the purpose of bridging the gap between them. Subsequently, a special mechanism for handling multiple constraints is developed. In the mechanism, the directions constraint of each task is ensured by the direction check and adjustment. The zoning constraints and the synchronism constraints are satisfied by teasing out the hidden correlations among constraints. The positional constraint is allowed to be violated to some extent in decoding and punished in cost fimction. Finally, with the TLBO seeking for the global optimum, the variable neighborhood search （VNS） is further hybridized to extend the local search space. The experimental results show that the proposed hybrid algorithm outperforms the late acceptance hill-climbing algorithm （LAHC） for TALB-MC in most cases, especially for large-size problems with multiple constraints, and demonstrates well balance between the exploration and the exploitation. This research proposes an effective and efficient algorithm for solving TALB-MC problem by hybridizing the TLBO and VNS.

Ethics Lines and Machine Learning: A Design and Simulation of an Association Rules Algorithm for Exploiting the Data

Data mining techniques offer great opportunities for developing ethics lines whose main aim is to ensure improvements and compliance with the values, conduct and commitments making up the code of ethics. The aim of this study is to suggest a process for exploiting the data generated by the data generated and collected from an ethics line by extracting rules of association and applying the Apriori algorithm. This makes it possible to identify anomalies and behaviour patterns requiring action to review, correct, promote or expand them, as appropriate.

Transmission Lines Distance Protection Using Differential Equation Algorithm and Hilbert-Huang Transform

This paper proposed the scheme of transmission lines distance protection based on differential equation algorithms (DEA) and Hilbert-Huang transform (HHT). The measured impedance based on EDA is affected by various factors, such as the distributed capacitance, the transient response characteristics of current transformer and voltage transformer, etc. In order to overcome this problem, the proposed scheme applies HHT to improve the apparent impedance estimated by DEA. Empirical mode decomposition (EMD) is used to decompose the data set from DEA into the intrinsic mode functions (IMF) and the residue. This residue has monotonic trend and is used to evaluate the impedance of faulty line. Simulation results show that the proposed scheme improves significantly the accuracy of the estimated impedance.

A NEW ALGORITHM FOR ADAPTIVE LATTICE FILTERAND ITS APPLICATION IN THE SPEECH LINEARPREDICTIVE SYNTHESIS

In this paper, an adaptive line spectral pair filter is derived from an adaptive lattice filter. A least-mean-square(LMS) type adaptive algorithm used to calculate directly the line spectral pair(LSP) coefficients on a stage-by-stage basis is presented. Experimental results show that the algorithm has higher convergence rate and lower misadjustment as compared with the other algorithms. The LSP coefficients calculated by the algorithm have been used to carry out speech linear predictive synthesis, resulting in better results than PARCOR coefficients.

P|rj,on-line|∑C_j的一类在线算法与竞争比分析

本文研究平等机上的在线排序问题,优化目标是使总完工时间最小,算法SSPT是此问题的一类在线算法,论文引入一个拟时间表,此时间表具有SRPT时间表的部分性质,论文通过此辅助时间表证明了SSPT算法是(3-1/m)-competitive的。

平行机的实时到达on-line算法下界的改进

本文考虑了平行机实时到达的在线问题．模型中，工件是陆续到达的，工件的个数、到达时间是事先未知的，而且只有当工件到达，才知其加工时间，目标是使所有工件都加工完的时间达到最小．Ｃｈｅｎ与Ｖｅｓｔｊｅｎｓ（１９９６年）证明了该在线问题不存在性能比小于１．３４７３的ｏｎ－ｌｉｎｅ算法．本文将此界改进为（５－５）／２．

非平衡大气辐射强度与透过率的Line-By-Line计算模式

导出了非局域热力学平衡（ＮＬＴＥ）大气辐射强度与透过率的基本公式，以及ＮＬＴ和ＬＴＥ的线强、光学厚度和透过率的关系。假设转动能级是热力学平衡（ＬＴＥ）的，建立了一个精确的ＬｉｎｅｂｙＬｉｎｅＮＬＴＥ辐射强度与透过率的有效算法来计算较高层行星大气红外活跃样品的辐射强度。计算了地球大气１６Ｏ３９６μｍ带在白天、夜晚和ＮＬＴＥ、ＬＴＥ条件下的临边光谱辐射强度、线积分辐射强度、带积分辐射强度和合成光谱辐射强度，揭示了ＮＬＴＥ辐射强度对ＬＴＥ辐射强度有显著而重要的偏离。

两台机器超载实时系统的On-line算法

对超载实时系统的On-line算法中的SR算法作了修改,提出了NSR算法,并证明NSR算法的竞争比至少为2/5,因而它比SR算法更为优异.

基于改进多目标粒子群算法的可重构装配线调度

针对可重构装配线调度问题,构建了最小化重构成本、最小化生产负荷平衡和最小化物流平准化的多目标调度模型,设计了改进多目标粒子群算法。该算法采取了自适应调整策略和重启机制以保证种群多样性,帮助算法跳出局部最优。为了测试两种改进策略的有效性,所提出算法与两种多目标粒子群算法进行对比实验,实验结果表明自适应调整策略和重启机制有效提升了多目标粒子群算法的性能。同时,将改进多目标粒子群算法与原始多目标粒子群算法、多目标模拟退火算法、多目标人工蜂群算法、多目标差分进化算法、基于分解的多目标进化算法、快速非支配遗传算法进行对比。对100个测试案例进行求解,在世代距离、指标和超体积率上均表明改进多目标粒子群算法优于对比算法,可实现多目标可重构装配线调度问题的高效求解。