機(jī)器帶激活費(fèi)用的有限資源博弈排序.pdf

1、本文主要研究有限資源的博弈排序問題,以工件排序為例就是指機(jī)器臺數(shù)有限,并且機(jī)器有一定的激活費(fèi)用。初始狀態(tài)沒有機(jī)器被激活,但機(jī)器一旦被激活,就需要支付一定的激活費(fèi)用,工件相當(dāng)于局中人,它們選擇機(jī)器進(jìn)行加工使它們的個體費(fèi)用最小,工件的個體費(fèi)用函數(shù)為其所選擇進(jìn)行加工的機(jī)器的完工時間與其所要承擔(dān)的激活費(fèi)用之和,研究的整體目標(biāo)函數(shù)為激活機(jī)器的最長完工時間與總的激活費(fèi)用之和。用PoA(price of anarchy)來衡量NE時的整體目標(biāo)函數(shù)值與

2、最優(yōu)值之間的差異。本文的結(jié)構(gòu)安排如下:
　　第一章首先介紹了研究問題的背景、有關(guān)概念及相關(guān)的研究進(jìn)展,并簡要說明了本文研究的主要成果及創(chuàng)新點(diǎn)。
　　第二章主要研究了m臺同型機(jī)情形下的資源分配問題,這時可不妨假設(shè)機(jī)器的激活費(fèi)用都為1.首先,證得此種情形下的PoA＜m,然后,分別在m=2和m=3兩種情形下證明,當(dāng)W＞l時,PoA分別小于3/2和2。此外,分別給出例子證明以上所求PoA的界均為緊界。
　　第三章研究了兩臺同類