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

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

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

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

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

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

基于禁忌搜索的點狀注記研究04-26

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

次可加測度壓的一個注記04-26

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

模型昆蟲翼作非定常i運動時的氣動力特性04-27

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

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

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