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

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

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

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