工件有到達(dá)時(shí)間的多代理排序問(wèn)題.pdf

1、授予單位代碼:學(xué)號(hào)或申請(qǐng)?zhí)?密級(jí):045905311146鄭州大學(xué)碩士學(xué)位論文論文題目:_!二件有到達(dá)時(shí)間的多代理排序問(wèn)題作者姓名:孫培學(xué)科門(mén)類(lèi):理學(xué)專(zhuān)業(yè)名稱(chēng):運(yùn)籌學(xué)與控制論研究方向:圖論與組合鼓優(yōu)化瀏巾姓名、職稱(chēng):原晉江教授二零零八年五月摘要所謂排序，就是在一定的約束條件下分配時(shí)間資源去完成一些任務(wù)，使一個(gè)或多個(gè)目標(biāo)達(dá)到最優(yōu).近年來(lái)，多代理排序間題越來(lái)越引起國(guó)際同行的重視，這是排序論研究中發(fā)展比較迅速的一個(gè)排序模型.在多代理排序模型中

2、，多個(gè)代理商互相競(jìng)爭(zhēng)使用一個(gè)公共的加工資源，代理商之間在加工各自的工件時(shí)互相影響，在關(guān)于公共資源的使用上互相協(xié)商.本文主要研究了有兩個(gè)代理的排序問(wèn)題:有兩個(gè)代理，每個(gè)都有一個(gè)工件集合.兩個(gè)代理商都想在一個(gè)公共資源上加工自己的工件，并希望最小化各自的目標(biāo)函數(shù)，這個(gè)目標(biāo)函數(shù)只和各自工件的完工時(shí)間有關(guān).因此，問(wèn)題是，如何安排工件的加工順序，使得在支持兩個(gè)代理商之間的協(xié)商的基礎(chǔ)上，使各自的目標(biāo)函數(shù)盡可能小.本文中，我們考慮一種特殊的兩個(gè)代理排序

3、模型.要求在對(duì)一個(gè)代理商的目標(biāo)函數(shù)值可以接受的條件下使得另一個(gè)代理商的目標(biāo)函數(shù)達(dá)到最小.我們將兩個(gè)代理商記為A和B，代理商A的工件集記為尸，代理商B的工件集記為JB.設(shè)尸=沖，對(duì)，…，孺，尸二護(hù)，昭，…，硫.我們稱(chēng)這兩個(gè)工件集中的工件分別為A一工件和B一工件.進(jìn)一步假設(shè)B一工件有非負(fù)的到達(dá)時(shí)間，記為哆，而A一工件的到達(dá)時(shí)間為0.兩個(gè)代理的目標(biāo)函數(shù)均是最大完工時(shí)間.于是，我們考慮的模型可記為:11昭嘿ax:嗽公，其中，嘿ax和嗽故分別對(duì)應(yīng)

4、A和B的目標(biāo)函數(shù)，也就是說(shuō)，我們的目標(biāo)是要找一個(gè)可行排序a使得在保證B一工件的最大完工時(shí)間不超過(guò)一個(gè)固定值(代理商B的可接受條件)的前提下A工件的最大完工時(shí)間最小.在A，etis等人(2004)(s山時(shí)ulingProtrlemswithTwoeompetingAgents)的文章中，并沒(méi)有考慮工件的到達(dá)時(shí)間.因此，本文的研究是對(duì)已有文獻(xiàn)的進(jìn)一步發(fā)展.本文的主要結(jié)論如下:(l)證明了問(wèn)題llrf嗽ax:嗽公在一般意義下是N尸一困難的.(