限位排序的若干结果

In this paper,we first consider the position restriction scheduling problems on a single machine.The problems have been solved in certain special cases,especially for those obtained by restricting the processing time pj=1.We introduce the bipartite matching algorithm to provide some polynomial-time algorithms to solve them.Then we further consider a problem on unrelated processors.     

定名次快速排序方法

给出了一个全新的不用比较交换数据的排序法—定名次排序法。用于内排序其计算量为2N次加法;对于涉及M个文件的外排序,可不形成新文件,计算量为N次加法,调用文件次数为2M次。该算法也是一特殊的并行算法,其总计算量几乎和单机计算量相同。     

基于向量的多边形扫描转换方法

提出了一种基于向量的多边形扫描转换方法,给出了相关的转换算法,并与一般计算机图形学原理教材中的常用几种多边形的扫描转换算法进行了相关比较分析。结论是在凸多边形的扫描转换上文中所提算法明显优于其他算法;对凹多边形也只需在凸多边形计算的基础上增加对凹边的判断与处理,但效率仍然高过其他算法。     

加工时间和尺寸成正比单机排序和工件运输的最小化最大完工时间问题

在单机排序和工件运输的最小化最大完工时间问题中,工件首先在一台机器上加工,然后被一辆有容量限制的汽车运送到一个顾客．当工件的加工时间和尺寸无关时, Chang和Lee已经证明该问题是强NP困难的．他们也给出了一个启发式算法,它的最差执行比为5／3,并且这个界是紧的．本文考虑工件的加工时间和尺寸成正比的情形,证明了Chang和Lee的算法有更好的最差执行比53／35,并提供了一个新的启发式算法,它的最差执行比是3／2,并且这个界是最好的．