工件有體積的平行機(jī)加工及分批運(yùn)輸.pdf

1、排序是組合最優(yōu)化的一個(gè)重要分支,它廣泛地應(yīng)用于管理科學(xué)、計(jì)算機(jī)科學(xué)和工程技術(shù)等很多領(lǐng)域,也是運(yùn)籌學(xué)研究的重要分支。分批排序是排序中的重要部分,它起于上世紀(jì)末,來(lái)源于半導(dǎo)體生產(chǎn)中的芯片測(cè)試過(guò)程,是一類新型排序問(wèn)題,有著很重要的應(yīng)用價(jià)值,在理論上也有重要的意義.因此,分批排序問(wèn)題在近年來(lái)受到了國(guó)內(nèi)外學(xué)者、專家、及企業(yè)家的高度關(guān)注,新的研究成果也是不斷出現(xiàn).本文就分批排序問(wèn)題的新進(jìn)展作了一些介紹,指出了它獨(dú)有的魅力,并給出了豐富的參考文獻(xiàn)。<

2、br>　　我們這篇文章主要研究了n個(gè)工件,工件Jj,j=1,2,…,n的體積為Sj工時(shí)為pj,在兩臺(tái)平行機(jī)上加工,然后分批運(yùn)輸?shù)膯?wèn)題。工件有體積是指在被運(yùn)輸時(shí)所占的物理空間,而且此文中我們假設(shè)運(yùn)輸車輛容量為z且只有一輛。本文中把車看做箱子,先把工件按裝箱問(wèn)題分箱,同箱物體為一批,再分批加工、運(yùn)輸。我們的目標(biāo)函數(shù)是求完工時(shí)間(車把工件全部運(yùn)輸?shù)侥康牡睾蠡氐皆霭l(fā)點(diǎn)的時(shí)間)的最小值。由[1]知它是NP難的,本文分為兩章,具體內(nèi)容如下: