<i>LPT</i>Algorithm for Jobs with Similar Sizes on Three Machines

In this paper, LPT (largest processing time) algorithm is considered for scheduling jobs with similar sizes on three machines. The objective function is to minimize the maximum completion time of all machines. The worst case performance ratio of the LPT algorithm is given as a piecewise linear function of r if job sizes fall in [1, r]. Our result is better than the existing result. Furthermore, the ratio given here is the best. That means our result cannot be improved any more.

LPT算法在3层客户/服务计算中的应用

运用LPT算法 ,在保证网络访问速度的前提下 ,求得在 3层C/S模型中所需数据库服务器以及中间应用服务器的数目 ,从而使整个网络硬件资源得到充分利用 ,以获得高性价比的网络 .此外 ,运用LPT算法 。

带准备时间的平行机排序的LPT算法

本文考虑带准备时间的平行机排序问题，讨论在使最早机器完工时间达到最大目标下的优化问题．这是ＮＰ－ｈａｒｄ问题，本文证明ＬＰＴ排序解至少是最优解的倍．

时间表理论中LPT算法在装箱问题中的应用

本文利用二分搜索法和时间表理论中LPT算法求解装箱问题的近似最优解;给出了一个直观性算法,并研究这个算法的最坏情形,最后说明此算法在某些方面优于著名的FFD算法。

处理机具有准备时间的恒速机排序问题

讨论任务的加工是不可中断 ,处理机是恒速机且处理机具有准备时间的排序问题 ,对一般情况的 L PT排序的界做了改进 ,同时对 m =2的情况给出了一个与处理机加工速度有关的 L

矩形非均匀采样算法和对数级坐标变换算法的比较分析

针对对数极坐标变换引起的图像周边模糊和图像细节丢失等现象,提出了矩形非均匀采样方法。图像中心采样区的大小可根据实际需要进行选取,对其进行均匀采样,对周边区进行分层均匀采样,随距采样中心距离的增大,采样率逐渐降低。对矩形非均匀采样、经典LPT和变参数LPT三者的运算量进行了比较,总体上说,矩形方法具有最少的运算量,而且可以克服对数极坐标变换图像的扭曲,并便于硬件实现。

一种独立任务的同型机调度快速算法

如何将n个独立任务调度到m台同型机上加工,使总完成时间最短,是一个复杂问题.通过分析Bound Fit预备算法的性质,结合MULTIFIT和Bound Fit提出QUICKFIT算法;对相同机器数和任务数,QUICKFIT能用比MULTIFIT和Bound Fit都少的迭代次数得到相同的总完成时间.实验结果表明,任务机器比越大,QUICKFIT算法的性能就越优于MULTIFIT和Bound Fit.绝大多数情况下,总完成时间等于MULTIFIT和Bound Fit中的最小者.该算法适用于大规模同型机调度.

带约束的平行机排序问题

讨论了带资源约束和机器准备时间的平行机排序问题 ,资源约束是指每个机器最多加工k个工件 .首先对一般情况下的同型机的PLPT排序进行了讨论 ;并首次对同类机排序进行了研究 ,给出了一个FLPT近似算法 ,同时对m =2时证明了PLPT排序的最坏情况紧界是 2 .

具有周期维护最小化时间表长的两台平行机调度问题(英文)

本文讨论了具有周期维护的两台平行机调度问题,目标函数为最小化时间表长.设T为维护周期,t为每次对机器维护需要的时间,当t≤T/3时,本文证明了对于该问题由LPT算法得到的最坏误差界为2.

一类P/S_(ij)/C_(max)问题的LS算法分析

提出一类有准备时间的排序问题；分析了ＬＳ算法解此问题的最坏情况；修改了ＬＰＴ算法，使最差性能指标由４－２ｍ改进到８３－２３ｍ．

同速度的具有m台通用机的n组工件的排序问题

改进了经典的LPT(Longest Processing Time)算法,利用"首先空闲"准则安排机器,而对于工件的安排则按照"长时间任务优先"的原则,讨论了将n组工件安排在n台速度相同的专用机,m台同速度的通用机上的优化排序问题,得到了利用该近似算法所得的解T与最优解T*的一个估计:T/T*≤(2m+1)/(m+1)。

惯性组合导航系统的实时多级景象匹配算法

针对景象匹配辅助惯性组合导航系统需要快速准确获取飞行器位置、航向偏差的要求,提出一种实时多级景象匹配算法。算法分为两级,第一级粗匹配中提出了中心点4-邻域的抗变形算法,能抗旋转和小尺度变化的影响,使定位精度达到像素级;第二级精匹配中提出了基于分支特征点,应用最小二乘法原理精确匹配定位出两幅图像间的最优相似变换参数,即飞行器的精确位置和航向偏差的算法。仿真分析表明,提出的实时多级算法能满足景象匹配辅助惯性组合导航系统实时性、精确性和鲁棒性的要求。

机器在一段时间不可用条件下的单机调度问题

文章对机器在一段给定时间内不可用情况下部分可恢复模式的单机调度问题进行了研究,当目标函数是最小化调度长度时,首先证明了LPT规则的误差上限是α/2,并举例说明该界限是紧的;同理可证该规则对不可恢复模式调度问题的误差上限是1/2,而不是有关文献所证明的1/3,同时上例也是1/3误差上限的反例;其次提出了一个启发式算法,该算法以LPT规则得到的解作为初始解,并结合基于成对交换技术的邻域搜索对解进行改进;当目标函数是最小化加权完成时间之和时,首先证明了最优调度的一个性质,并据此提出了动态规划算法。

具有通用机的多组工件的Q//C_(max)问题的近似算法

研究的目的在于解决实践中对多组任务的优化排序问题,即在最短的时间内完成所有给定的任务。由于这类问题往往都是NP完全问题,人们通常寻求其近似算法。提出了一种改进的LPT算法,利用"最大相对加工时间"准则和"首先空闲"准则,讨论了将n组工件安排在n台速度不同的专用机,一台速度小于专用机的通用机上的Cmax问题,得到了利用该近似算法所得的解T与最优解T*的一个估计:T/T*≤1+1/∑i∈Isi,其中I表示在最后完工的工件完工之前,在通用机上至少安排了一个工件的工件组的下标集合。由此得出采用该近似算法对工件排序,在最差情况下要比最优排序多出1/∑i∈Isi的时间。

速度相同的具有m-2台通用机的两组工件的LS算法分析

对于实践中存在的具有两组任务的优化排序问题进行了讨论,在经典的LS算法的基础上提出了一种改进的LS算法,利用"首先空闲"准则选择机器,按照工件的到达顺序安排工件,讨论了将两组工件安排在两台速度相同的专用机,m-2台同速度的通用机上的Cm ax问题,其中工件具有准备或到达时间,且工件的准备或到达时间均不超过其加工时间的α倍。目标是在最短的时间内完成所有给定的任务。得到了利用该近似算法所得的解TLS与最优解T*的一个估计(1+α)(2-1/m),并且证明了对任意的α此界是紧的。

基于Petri网的智能计划编排及优化模型的建立

根据某印染企业实际加工生产过程,建立了相应的分层赋时着色Petri网模型。根据各种实际约束条件为生产过程建立了优化模型,同时结合智能算法实现生产调度甘特图的自动生成和生产计划的自动预排,最后与手工编制的生产计划进行了比较,证明了该方法的有效性。

两台平行机完工时间平方和最小的排序问题

在两个竞争公司进行零和博弈过程中,最大化两个公司收益的乘积,在两台平行机的离线排序问题中相当于最小化两台机器完工时间的平方和.给出了该问题修改的延缓开始LPT算法：首先,将工件按照加工时间pj的LPT序重新标记;若加工时间最长的前2m个工件的总加工时间P（2m）〈（2m＋1）p2m＋1,最优的安排加工前2m＋1个工件,一旦有机器空闲,依次从第2m＋2个工件安排加工;否则,P（2m）≥（2m＋1）p2m＋1,最优的安排加工前2m个工件,一旦有机器空闲,依次从第2m＋1个工件安排加工.证明了该算法的最差性能比不超过1＋（1/（2m＋2））2,且界是紧的.

具有m台通用机和两台专用机的Q_(m+2)/r_j/C_(max)问题的改进LS算法

对于实践中存在的机器加工速度不同的,具有两组任务的优化排序问题进行了讨论,在经典的LS算法的基础上提出了一种改进的LS算法,利用"首先空闲"准则选择机器,按照工件的到达顺序安排工件,讨论了将两组工件安排在两台速度不同的专用机,m台速度相同的通用机上的C_(max)问题,其中工件具有调整时间或安装时间,且工件的调整时间或安装时间均不超过其加工时间的α倍.目标是在最短的时间内完成所有给定的任务.得到了利用该近似算法所得的解T^(LS)与最优解T~*在不同条件下的两个估计,并且证明了这两个估计是紧的。

关于模糊工期平行机调度问题的若干结果

研究工件工期是模糊数的平行机调度问题,给出最优调度目标函数值在不同分布下该问题的4个性质,证明了Pm｜^~di=^~d｜Fmin问题是NP-难的.特别地,分析了当所有工件的dj与ej都相同时,LPT算法所得到的最小满意度相对于最优调度所对应的最小满意度的界.

串行生产线中机器维修工人的任务分配问题研究

在串行生产线中,机器会发生故障而且故障间隔时间随机,因此需要维修工人及时维修,使得故障的机器恢复加工能力,否则就可能导致系统吞吐率降低.如何在满足系统吞吐率的前提下,使用尽可能少的维修工人来完成机器的维修任务,本文称这样一个全新的问题为串行生产线中机器维修工人的任务分配问题.针对该问题,本文首先建立了问题的优化模型,并将该优化问题转换为多个判定问题进行求解;然后,通过合理地定义机器的维修工作量,使得判定问题可以类比为并行机调度问题;最后,采用了一种基于最长处理时间优先算法(Longest processingtime,LPT)和回溯策略的启发式算法,搜索最优的维修工人任务分配方式.实验结果表明,该方法能有效求解维修工人的任务分配问题.