本文關(guān)鍵詞：具有多個(gè)受限制可用時(shí)間段的單機(jī)供應(yīng)鏈排序問(wèn)題

  更多相關(guān)文章： 可用時(shí)間段 供應(yīng)鏈排序 強(qiáng)NP-難 近似算法

【摘要】：在文中所研究的單機(jī)供應(yīng)鏈排序問(wèn)題中,機(jī)器可用時(shí)間段的長(zhǎng)度不大于給定常數(shù),且每個(gè)不可用時(shí)間段長(zhǎng)度確定。工件僅可以在機(jī)器的可用時(shí)間段內(nèi)被加工,完工后可與其他完工工件組成一批,由一個(gè)容量無(wú)限制的運(yùn)輸工具發(fā)送給客戶(hù)。運(yùn)輸工具在機(jī)器的每個(gè)可用時(shí)間段結(jié)束時(shí)間進(jìn)行發(fā)送,且每次發(fā)送的費(fèi)用固定。問(wèn)題的目標(biāo)是安排工件的加工、發(fā)送,以及機(jī)器的不可用時(shí)間段,以使總發(fā)送時(shí)間與總發(fā)送費(fèi)用之和達(dá)到最小。對(duì)于工件允許中斷的情況,可在多項(xiàng)式時(shí)間O(n log n)內(nèi)得到最優(yōu)序(n為工件的個(gè)數(shù))。對(duì)于工件不允許中斷的情況,證明了問(wèn)題是強(qiáng)NP-難的,并提出了2-近似算法。
【作者單位】： 上海第二工業(yè)大學(xué)理學(xué)院;
【關(guān)鍵詞】： 可用時(shí)間段 供應(yīng)鏈排序 強(qiáng)NP-難 近似算法
【基金】：上海第二工業(yè)大學(xué)青年教師培養(yǎng)科研項(xiàng)目(No.201513)資助
【分類(lèi)號(hào)】：O223
【正文快照】： 0引言供應(yīng)鏈排序是把生產(chǎn)、分批和發(fā)送三者集成在一起,研究集成優(yōu)化的模型及其算法[1]。實(shí)際上,供應(yīng)鏈排序就是在排序決策范疇內(nèi)研究供應(yīng)鏈管理,是排序論在供應(yīng)鏈管理中的應(yīng)用。供應(yīng)鏈排序的第一篇論文是由Potts[2]于1980年發(fā)表的。2003年Hall和Potts[3]在論文中系統(tǒng)地提出了

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前2條

1 馬晨;;未來(lái)的人類(lèi)能源[J];科學(xué)之友;2007年03期

2 ;[J];;年期

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 劉燕子;基于認(rèn)知行為分析的人誤因素辨識(shí)技術(shù)研究[D];南華大學(xué);2006年

，

本文編號(hào)：836403