工件集合上的某种全序及其应用

对于由工时与工期所确定的工件的全体,本文定义了一种全序,该全序是SPT序(短工时序)与EDD序(早工期序)的结合,且结合方式依赖于某个时间参数。本文分析了该全序与有关延误的相邻交换条件之联系,从而给出总延误问题的一个近似算法,并证明它可以在多项式时间内得到后移邻域所相应的局部解。

批处理机上具有两类释放时间的工件集竞争调度问题

研究了两个工件集合竞争在一台批处理机上加工的调度问题,其中每个集合的工件具有一个共同的释放时间.批处理机可以同时加工多个工件作为一批,每批的加工时间为该批工件中加工时间的最大值.基于两类释放时间的大小,针对无界批处理机上最小化一个集合工件的最大完工时间、最大延迟以及总完工时间,使得另一个集合工件的最大完工时间不超过给定上界问题,分别给出了最优求解方法.针对有界批处理机上最小化一个集合工件的最大完工时间,使得另一个集合工件的最大完工时间不超过给定上界问题,证明为一般意义NP-难问题,并给出伪多项式时间最优求解方法.