關(guān)于排序模型1-·-ri≥0-n∑i=1vi的注記

設(shè) J={J1,…,Jn}是n個(gè)工件的集合,M是一臺(tái)機(jī)器.每個(gè)工件Ji要在機(jī)器M上加工一次,而且是相繼只加工一次,即加工不能夠中斷.Ji的加工時(shí)間是pi,準(zhǔn)備時(shí)間是ri,即Ji不能在ri之前加工,要求完工的期限是di,即工件ji的加工應(yīng)該在di之前完成.否則,這個(gè)工件將被拒絕放在一旁.我們的目的是尋找排序算法A,當(dāng)使用到給定的J上時(shí),使被拒絕的工件個(gè)數(shù)為最少.1978年Kise,Ibaraki,Mine等在條件ri＜rj蘊(yùn)涵di≤dj(對(duì)于任何1≤i,j≤n)下,對(duì)于任何給定的J找到算法A.他們?cè)谡撐腫1]中"證明"算法A是最優(yōu)算法.最近,李杉林給出一個(gè)例子說明他們的證明中的一個(gè)關(guān)鍵引理是錯(cuò)誤的.本文作者在書[2]中也沿用了這個(gè)錯(cuò)誤的"證明".對(duì)于算法A的最優(yōu)性,本文給出一個(gè)新的簡(jiǎn)單的證明.

作 者： 越民義 Yue Minyi   作者單位： 中國(guó)科學(xué)院應(yīng)用數(shù)學(xué)研究所,北京,100080  刊 名： 運(yùn)籌學(xué)學(xué)報(bào)  ISTIC PKU 英文刊名： OPERATIONS RESEARCH TRANSACTIONS  年，卷(期)： 2007 11(4)  分類號(hào)： O22  關(guān)鍵詞： 運(yùn)籌學(xué)   算法   排序   Operations research   algorithm   scheduling  

【排序模型1-·-ri≥0-n∑i=1vi的注記】相關(guān)文章：

CCR模型中決策單元的區(qū)間效率值及其排序04-27

關(guān)于LCM方程的李-曹猜想的注記04-26

基于禁忌搜索的點(diǎn)狀注記研究04-26

關(guān)于Shannon采樣定理的一點(diǎn)注記04-26

次可加測(cè)度壓的一個(gè)注記04-26

1-羥基-2-(1-甲基咪唑-2-基)乙烷-1,1-雙膦酸的合成04-27

模型昆蟲翼作非定常i運(yùn)動(dòng)時(shí)的氣動(dòng)力特性04-27

實(shí)習(xí)1-厭惡教案！04-25

關(guān)于變截面桿自由振動(dòng)精確解的注記04-26

關(guān)于Locale Wallman緊化的一點(diǎn)注記04-26