论文部分内容阅读
排序论是运筹学中非常重要的一个分支.在经典的排序问题中,人们对与时间限制有关的目标函数的研究是非常广泛的.在本学位论文中,我们主要研究目标函数是关于提前工作量指标的单机排序问题.工件的提前工作量是不同于工件的提前量的一个指标,它是工件在预开工时间之前加工部分的大小.因此,在任一可行排序中,一个工件的提前工作量不会大于它的加工时间.在大数据的信息处理中,预开工时间之前加工的工件(数据)会产生额外的存储费用,并且该费用通常是与工件的提前工作量是成正比的.因此,如何合理安排工件的加工使得工件的提前工作量产生的费用尽可能少就是一个具有理论研究价值和应用前瞻性的研究课题. 本学位论文分成两部分来研究关于提前工作量指标下的排序问题.第一部分研究的是单机上的最小化最大提前工作量的排序问题,第二部分研究的是单机上最小化加权提前工作量的排序问题. 我们用EWmax表示工件的最大提前工作量,用此处为公式表示工件的加权提前工作量总和.本文的主要结果如下: ?对于排序问题此处为公式,我们给出了一个运行时间为O(n2)的最优算法;我们进一步猜测,引入适当的数据结构,该算法的运行时间可以改进到0(nlogn). ?对于排序问题此处为公式,我们给出了一个运行时间为O(n2)的最优算法.并且指出了该算法对于在线的排序问题此处为公式也是最优的. ?对于NP-困难的排序问题此处为公式,我们给出了一个运行时间为此处为公式的动态规划算法.这就解决了Ben-Yehoshua和 Mosheiov(2016)在文献中提出的遗留问题. ?对于工件带有到达时间且允许中断抢先的排序问题此处为公式,我们给出了一个运行时间为O(n2)的最优算法.