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

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

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