工件可自由下线最小化总完工时间的有界平行分批排序

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题.在该问题中,一台平行批机器可以同时处理b个工件作为一个平行批,这里b是批容量,一个批的加工时间等于分配给这个批的工件的最大加工时间.关于可自由下线工件,每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和.也就是,如果一个批■有一个开工时间S,那么包含在批■中的每一个工件乃的开工时间定义为S,而它的完工时间定义为S+p_j,这里p_j是工件J_j的加工时间.对此问题,首先研究最优排序的一些性质.然后,基于这些性质,给出一个运行时间为O(n^(b(b-1))的动态规划算法.