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

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

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

【相似文獻(xiàn)】

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

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

2 ;[J];;年期

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

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

，

本文編號：836403