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

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

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

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