具有不可用區(qū)間的平行機(jī)排序問題的近似算法.pdf

1、近幾年來，排序問題由于其深刻的實際背景和廣泛的應(yīng)用前景而受到了極大關(guān)注。在經(jīng)典的排序模型中，機(jī)器是一直可用的。然而，在實際生活中機(jī)器也需要維修，工人也需要休息，這就導(dǎo)致了機(jī)器在使用過程中不可能是一直可用的。所以很多人研究了機(jī)器帶有不可用約束的排序問題。同時我們也考慮了工件帶有運輸時間的問題，這是因為在具有很多工件數(shù)的大型排序問題中，往往在工件加工完之后還需要在一定的時間內(nèi)將其運送到指定的生產(chǎn)地方。這就使得我們不僅要單純考慮工件的完工時間

2、也要把運輸時間計劃在內(nèi)，使其更符合實際意義。
　　本文主要討論在機(jī)器具有不可用約束的情形下的平行機(jī)排序問題。文章主要分為四個部分，第一章中介紹了排序問題的背景，描述及表示方法，并對機(jī)器的不可用區(qū)間和工件的運輸時間做了陳述。第二章中主要討論了機(jī)器具有不可用區(qū)間的平行機(jī)排序問題。其中第一臺機(jī)器上有一段不可用區(qū)間，第二臺機(jī)器是可以連續(xù)使用的，工件在加工過程中是不允許中斷的，目標(biāo)函數(shù)是極小化時間表長。首先介紹了與之相關(guān)問題的發(fā)展情況，然后