1844.單臺機(jī)器下的幾類兩個代理排序問題研究

1、重慶師范大學(xué)碩士學(xué)位論文單臺機(jī)器下的幾類兩個代理排序問題研究碩士研究生指導(dǎo)教師學(xué)科專業(yè)所在學(xué)院馬露張新功副教授運籌學(xué)與控制論數(shù)學(xué)科學(xué)學(xué)院重慶師范大學(xué)二〇一七年五月重慶師范大學(xué)碩士學(xué)位論文中文摘要單臺機(jī)器下的幾類兩個代理排序問題研究摘要排序是為加工若干工件而對資源按時間進(jìn)行高效率分配.排序的好壞直接影響著費用的高低和利潤的大小.在經(jīng)典排序問題中，往往只有一個目標(biāo)函數(shù)并且工件僅屬于一個代理.本文研宄幾類兩個代理單機(jī)排序問題.每個代理都有各自

2、的工件集和與其對應(yīng)的目標(biāo)函數(shù)，它們共用一臺機(jī)器來完成各自工件.每個代理都想讓自己的目標(biāo)函數(shù)最小化并且這個目標(biāo)函數(shù)只與工件完工時間有關(guān).問題在于如何安排工件的加工次序以便滿足各個代理對其目標(biāo)函數(shù)的要求.本文主要研宄以下幾類問題：1)最小化總誤工損失問題第一個代理的目標(biāo)函數(shù)為總誤工損失，第二個代理的目標(biāo)函數(shù)為總完工時間或者總誤工工件數(shù).目的是找到一個排序，讓第一個代理的目標(biāo)函數(shù)值最小，并且保證另一個代理的目標(biāo)函數(shù)值不超出給定上界.對于這兩個

3、排序問題，提出相應(yīng)擬多項式時間算法.2)工件可拒絕的排序問題考慮第一個代理的目標(biāo)函數(shù)分別是最大完工時間與總拒絕懲罰之和，最大延遲與總拒絕懲罰之和，總誤工損失與總拒絕懲罰之和.第二個代理的目標(biāo)函數(shù)均為總權(quán)誤工工件數(shù).對于這三種排序問題，證明它們是一般意義下的難問題，并提出相應(yīng)的擬多項式時間算法.3)帶到達(dá)時間可中斷的排序問題第一個代理中的工件有不同到達(dá)時間且允許中斷，以總誤工損失為目標(biāo)函數(shù)第二個代理中的工件不允許中斷且被安排在固定時間窗口