機器具有準備時間的排序問題.pdf

1、排序問題是一類重要的組合最優(yōu)化問題，現(xiàn)在已經(jīng)成為運籌學研究的一個非?；钴S的分支，是運籌學中相當具有生命力的一部分。排序問題的一大特點是：模型繁多，適用于某一模型的算法，只要將模型的條件稍加變化，該算法即可能不適用。經(jīng)典的排序問題通常是假設(shè)所有的機器都是可以同時開始加工工件的，但在實際生產(chǎn)中機器不一定可以同時開工。機器具有準備時間的排序問題是經(jīng)典排序問題的推廣，越來越引起研究者的興趣。本文首先介紹了排序問題的定義、表示方法和分類，以及對于

2、機器具有準備時間的排序問題的研究現(xiàn)狀，然后對機器具有準備時間的排序問題進行了進一步的討論。 首先介紹了有關(guān)機器具有準備時間的排序問題的一些研究成果，然后分別對機器具有準備時間的同速機排序問題和機器具有準備時間的恒速機排序問題這兩大類問題進行了介紹和研究。在本文的第二章中，對第一類問題進行了討論，并且從兩方面分別進行了研究。第一方面研究了任務(wù)具有鏈約束的排序問題，主要討論了任務(wù)的加工不允許中斷，任務(wù)間具有鏈約束，機器具有準備時間的

3、同速機排序問題，目標函數(shù)是極小化最大完工時間，并將LPT算法應(yīng)用到了該問題中得出了最優(yōu)值的一個下界，利用具體例子對算法的應(yīng)用做出解釋，并且用實例說明了該界是緊界。第二方面研究了關(guān)于A<,kk>算法和它的界，主要討論了任務(wù)的加工不可中斷，機器具有準備時間的同速機排序問題，目標函數(shù)是極小化最大完工時間，將A<,kk>算法應(yīng)用到本問題中得出了一個界，并用數(shù)值例子做了說明，但此界不是緊的，因此，有待于進一步研究。在本文的第三章中，對第二類問題進