有資源限制的分批排序問題的算法研究.pdf

1、排序問題是組合優(yōu)化領域的一個重要分支，它有著重要的應用背景和深刻的理論意義．而分批排序是繼經典排序之后的較新排序模型之一．本文就這一模型的有資源限制的問題做了一些工作． 第一章簡單介紹了排序問題的相關定義、記號及相關預備知識． 第二章考慮了單機分批排序問題中目標是極小化加權總完工時間的問題．將FBLW算法進行推廣，就工件到達時間均為正整數、加工時間恒為1的情形，設計出了一個時間復雜性為(O)(n<'2>log n)的最優(yōu)

2、算法；對工件有常數m個到達時間、加工時間恒等的情形給出一個最優(yōu)算法，并給出其算法復雜性為O(2<'m-1>n log n)． 第三章研究了分批排序中機器有使用限制的兩個問題．這是首次將機器有使用限制的條件在分批排序問題中進行考慮．對于目標是極小化最大完工時間、工件不可中斷的單機分批排序問題，我們對批容量無限的情形找到了多項式時間的最優(yōu)算法，對批容量有限的情形提出了一個最差性能比為4/3的近似算法，并且界是緊的． 第四章總