帶有學習與惡化效應的機器受限的排序問題.pdf

1、在某些實際生產(chǎn)過程中，工件加工時間的變化既受生產(chǎn)設備長時間使用，導致惡化現(xiàn)象的影響，也受生產(chǎn)設備或工人加工效率提高的影響。因此，在這種模型中，工件的實際加工時間不僅與它的所排位置有關，而且還與工件的開始加工時間有關。此外，由于機器發(fā)生故障或進行維護與保養(yǎng)等原因，導致其在某一時間段內(nèi)無法加工工件。我們把受生產(chǎn)因素等影響，排在后面加工的工件，其加工時間縮短的現(xiàn)象稱之為學習效應；把機器設備等由于長時間使用導致生產(chǎn)能力下降，排在后面加工的工件，

2、其加工時間增加的現(xiàn)象稱之為惡化效應；把機器在工作過程中出現(xiàn)定期維修或保養(yǎng)等情況，從而導致機器在某段時間內(nèi)不能加工工件的現(xiàn)象稱之為機器具有可用性限制。本文將這三方面結(jié)合在一起進行了研究，具體內(nèi)容概括如下：
　　1、對于單機問題，即考慮一臺機器在任意時間段不可用的情況，本文主要討論了以下兩個問題：
　　(1)當工件的加工時間受學習與惡化效應影響時，極小化總完工時間的排序問題；
　　(2)當工件的加工時間受學習與惡化效應影響

3、、且工件的基本加工時間與權(quán)值逆序時，極小化加權(quán)總完工時間的排序問題。
　　對上面的NP-難問題，分別分析了最優(yōu)解性質(zhì)，給出了此問題的擬多項式時間的動態(tài)規(guī)劃算法及相應算法的計算復雜性，并用數(shù)值例子說明了算法的有效性。
　　2、對于平行機問題，即考慮其中一臺（如第一臺）機器在任意時間段不可用時的情況，本文針對以上兩個問題分別進行了討論，分析了問題的最優(yōu)解性質(zhì)，給出了擬多項式時間的動態(tài)規(guī)劃算法及算法的計算復雜性。
　　3、對