機(jī)器具有準(zhǔn)備時(shí)間的排序問題.pdf

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

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

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