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

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

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

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