摘要：在一批新工件突然到達、單轉(zhuǎn)包商可加工任意工件的條件下,研究最大時間偏離量與總外包費用不超過給定上限、使總完工時間與總外包費用加權(quán)和最小化的單機重調(diào)度問題.在構(gòu)建0-1規(guī)劃模型、分析NP困難性、提出若干優(yōu)化性質(zhì)的基礎(chǔ)上,利用動態(tài)規(guī)劃技術(shù)和兩種不同的外包工件集決策方式,分別設(shè)計出工件添加型啟發(fā)式算法和工件排除型啟發(fā)式算法.在仿真實驗中,通過系統(tǒng)生成大量測試算例,對比分析了兩種啟發(fā)式算法在求解質(zhì)量、計算時間上的表現(xiàn).實驗結(jié)果表明,工件排除型啟發(fā)式算法在優(yōu)化質(zhì)量與效率上均優(yōu)于工件添加型啟發(fā)式算法.