基于像素链的直线绘制算法

针对直线生成算法在直线斜率大于0.5时的低效率问题,提出一种基于像素链的直线绘制算法。将直线看做是由许多条平行像素链或对角像素链拼接而成,提出并利用逆向生成直线的类Bresenham算法,将斜率在0.5~1的直线绘制转换为斜率在0~0.5的直线绘制,一次判断生成一条像素链。仿真实验表明,基于像素链的算法生成的直线与Bresenham算法生成直线一致,且计算量显著减少。该算法只有加法和乘法两种整数运算,适合硬件实现,其绘制速度是Bresenham算法的4倍。     

对C++中继承的二义性之探讨

讨论了Ｃ＋＋中的继承关系,阐述了类型的重要性,着重探讨继承所产的二义性问题。     

热轧实施计划中最优倒垛问题的整数规划模型及遗传算法

对钢铁企业板坯库中的最优倒垛问题建立了0和1整数规划模型.这一模型是一个 二次规划模型,且目标函数的系数与变量的取值相关联,属于NP-难问题,获得较大规模的最 优解是不可能或非常困难.为了求解此问题,本文构造了改进遗传算法:(1)提出了适合于最 优倒垛问题的遗传编码,运用此编码,不但能够产生可行的初始染色体,而且能够保证在交叉 和变异操作后的染色体仍然可行;(2)改进了遗传算法结构,在新的结构中,增加了一个培育 操作,改进了交叉操作.通过精选随机产生的问题例子的实验显示出,提出的算法的性能明显 好于原系统的启发式算法,最好的改进率达到7.04％.     

求补舍入并行和位长自适应整数转浮点数电路设计

提出了一种实现整数转浮点数的新的设计方法 ,并且对方法的正确性给予了证明 .采用这种设计方法 ,实现了求补和舍入的合并并行 ,使关键路径的延时比常规的电路设计方案减少了 15级门 ,同时降低了电路规模 .关键路径延时的减小 ,使这一转换可以在单周期内完成 .另外 ,该方法实现了位长自适应 ,只需花费很少的电路规模和延时实现控制 ,就可以适应长整型、整型到单、双精度浮点数的转换 ,增强了电路功能 .这一设计方法同样适用于其逆转换 .该转换模块采用 Fujitsu CE71库设计 ,在 10 0 MHz主频下经仿真验证 ,结果正确 ,已经应用到实际工程中 .     

基于H.264/AVC的帧内4×4预测模式快速选择算法

在H.264/AVC视频编解码标准中,帧内预测利用周围像素预测当前块来降低空间冗余,能极大地提高H.264/AVC的编码效率。然而,帧内预测的4×4预测有9种模式,为选出最佳模式,全搜索算法需要花费极大的计算量。为了降低帧内预测的复杂度,文章结合9种预测模式的各自特点和整数变换的线性性质,提出一种适用于H.264/AVC帧内4×4模式选择的快速变换和量化算法来减少对应模式变换和量化操作步骤的计算量。实验结果表明,优化算法可以有效地减少整数变换和量化操作的计算量。     

基于多品种生产的预制梁厂设计优化模型的研究

针对我国现阶段基于多品种生产的预制梁厂设计和排产传统方法的缺陷,通过对预制梁厂设计和生产影响因素的调查与分析,结合优化理论与方法,建立了基于多品种生产的预制梁台设计和预制梁厂排产优化模型,并进行了实例验证,将优化方法同传统算法相比较,证明优化模型具有明显的优势,能够较好地辅助施工单位进行预制梁厂设计和生产决策。     

A computational study on the quadratic knapsack problem with multiple constraints

The quadratic knapsack problem (QKP) has been the subject of considerable research in recent years. Despite notable advances in special purpose solution methodologies for QKP, this problem class remains very difficult to solve. With the exception of special cases, the state-of-the-art is limited to addressing problems of a few hundred variables and a single knapsack constraint.In this paper we provide a comparison of quadratic and linear representations of QKP based on test problems with multiple knapsack constraints and up to eight hundred variables. For the linear representations, three standard linearizations are investigated. Both the quadratic and linear models are solved by standard branch-and-cut optimizers available via CPLEX. Our results show that the linear models perform well on small problem instances but for larger problems the quadratic model outperforms the linear models tested both in terms of solution quality and solution time by a wide margin. Moreover, our results demonstrate that QKP instances larger than those previously addressed in the literature as well as instances with multiple constraints can be successfully and efficiently solved by branch and cut methodologies.     

Optimal cyclic single crane scheduling for two parallel train oilcan repairing lines

Crane is widely used to move a heavy object from one place to another not only in manufacturing industry but also service industry. As an important resource in the train oilcan repairing, crane scheduling affects directly the productivity of the systems. In this paper, we study cyclic single crane scheduling problem with two parallel train oilcan repairing lines, where jobs are loaded into the line at one end and unloaded at the other end. The processing time at each workstation must be within a given range. There is no buffer between these stations. A crane is used to move jobs between the workstations in two parallel lines. The objective is to schedule the moves to minimize the production cycle. We proposed a time way diagram for two parallel lines and developed a mixed integer linear programming model. Then we extended the model to the scheduling problem with multi-station to eliminate the bottleneck in lines. Examples are given to demonstrate the effectiveness of the model.     

Alternative mixed integer linear programming models for identifying the most efficient decision making unit in data envelopment analysis

A mixed integer linear model for selecting the best decision making unit (DMU) in data envelopment analysis (DEA) has recently been proposed by Foroughi [Foroughi, A. A. (2011a). A new mixed integer linear model for selecting the best decision making units in data envelopment analysis. Computers and Industrial Engineering, 60(4), 550–554], which involves many unnecessary constraints and requires specifying an assurance region (AR) for input weights and output weights, respectively. Its selection of the best DMU is easy to be affected by outliers and may sometimes be incorrect. To avoid these drawbacks, this paper proposes three alternative mixed integer linear programming (MILP) models for identifying the most efficient DMU under different returns to scales, which contain only essential constraints and decision variables and are much simpler and more succinct than Foroughi’s. The proposed alternative MILP models can make full use of input and output information without the need of specifying any assurance regions for input and output weights to avoid zero weights, can make correct selections without being affected by outliers, and are of significant importance to the decision makers whose concerns are not DMU ranking, but the correct selection of the most efficient DMU. The potential applications of the proposed alternative MILP models and their effectiveness are illustrated with four numerical examples.     

Efficient solution of the 3G network planning problem

The 3G universal mobile telecommunications system (UMTS) planning problem is combinatorially explosive and difficult to solve optimally, though solution methods exist for its three main subproblems (cell, access network, and core network planning). We previously formulated the entire problem as a single integrated mixed-integer linear program (MIP) and showed that only small instances of this global planning problem can be solved to optimality by a commercial MIP solver within a reasonable amount of time ( St-Hilaire, Chamberland, & Pierre, 2006). Heuristic methods are needed for larger instances. This paper provides the first complete formulation for the heuristic sequential method ( St-Hilaire, Chamberland, & Pierre, 2005) that re-partitions the global formulation into the three conventional subproblems and solves them in sequence using a MIP solver. This greatly improves the solution time, but at the expense of solution quality. We also develop a new hybrid heuristic that uses the results of the sequential method to generate constraints that provide tighter bounds for the global planning problem with the goal of reaching the provable optimum solution much more quickly. We empirically evaluate the speed and solution accuracy of four solution methods: (i) the direct MIP solution of the global planning problem, (ii) a local search heuristic applied to the global planning problem, (iii) the sequential method and (iv) the new hybrid method. The results show that the sequential method provides very good results in a fraction of the time needed for the direct MIP solution of the global problem, and that optimum results can be provided by the hybrid heuristic in greatly reduced time.