摘要：多处理机工件是在同一时刻由多台处理机并行加工的工件。面向以最小化最大完工时间为目标的多处理机工件调度,分析了机器数量增加对最大完工时间的影响,证明了最优调度方案和所提近似调度方案的最好情形影响比,揭示了最大完工时间随着机器数量增加而减少并趋于稳定的规律。分析了机器数量增加的影响,一方面改善了调度目标,另一方面增加了机器投入成本。权衡最大完工时间减少和机器成本增加两方面影响,以最小化最大完工时间与机器成本加权和为目标决策机器数量。基于降序首次适应算法设计了近似算法,给出了调度优化方案,并证明了所提算法的最差性能比不超过2。通过仿真实验,验证了所提算法的最好情形影响比及算法的有效性。

摘要：对工件有不同到达时间、不同加工时间和尺寸的同型机分批排序问题寻找近似算法。对于大工件(工件的体积严格大于机器容量的1/2)的加工时间不小于小工件(工件的体积小于或等于机器容量的1/2)的加工时间的特定情形,利用动态规划的方法和拆分的技巧,我们设计了近似算法并分析了其最差性能比。

摘要：首次研究了机器带准备时间的平行机上的分批排序问题,这里的目标函数为极小化工件的最大完工时间,这类问题是NP-难的.我们根据FBLPT算法、Multifit算法和LPT算法,分别对机器是同型机和同类机的两种情形设计出两个近似算法,并证明它们的最差性能比分别不超过(2-1B)[97+(12)k]和53(2-1B).

摘要：主要讨论了工件有到达时间、加工时间和尺寸的目标函数是极小化最大延误时间的单机分批排序问题1|B,rj,sj|Lmax.在机器容量B为常数时,即使在B=2和工件的到达时间与尺寸都相同时,问题也是强NP—难的.基于问题1|B,rj|Lmax目前最好的多项式时间近似算法——PTAS算法(从算法的最差性能比来说是最好的),我们采用任意工件可以按尺寸拆分的技巧,针对问题1|B,rj,sj|Lmax设计了一个多项式时间的近似算法,并分析出这个算法的最差性能比为2+ε(其中ε是任意小的正数).