【摘要】：排序問(wèn)題在管理科學(xué)、計(jì)算科學(xué)和控制科學(xué)等領(lǐng)域有廣泛的應(yīng)用,代理排序問(wèn)題則是近十年興起的。代理排序可以利用博弈論的基本方法來(lái)對(duì)各個(gè)代理的目標(biāo)進(jìn)行權(quán)衡；也可以利用組合優(yōu)化方法,將多目標(biāo)問(wèn)題轉(zhuǎn)化為約束限制優(yōu)化問(wèn)題、Pareto最優(yōu)問(wèn)題或單目標(biāo)優(yōu)化問(wèn)題。本文主要基于兩代理排序的約束限制優(yōu)化模型,研究單機(jī)和平行機(jī)環(huán)境下的兩代理排序問(wèn)題。 對(duì)于單機(jī)環(huán)境,我們研究了工件具有達(dá)到時(shí)間、目標(biāo)函數(shù)均為最大完工時(shí)間的兩代理排序問(wèn)題。我們利用劃分問(wèn)題證明了該問(wèn)題是NP-hard的,然后為其設(shè)計(jì)了限制情形的PTAS。對(duì)于平行機(jī)環(huán)境,我們首先研究了m臺(tái)平行機(jī)兩個(gè)代理目標(biāo)函數(shù)均為完工時(shí)間和的問(wèn)題,設(shè)計(jì)了該問(wèn)題的擬多項(xiàng)式時(shí)間算法,并由此說(shuō)明了該問(wèn)題是普通意義下NP-hard的,而且基于擬多項(xiàng)式時(shí)間算法,給出了該問(wèn)題限制情形下的FPTAS。最后我們考慮了平行機(jī)臺(tái)數(shù)m不作為輸入?yún)?shù)、兩個(gè)代理目標(biāo)函數(shù)均為最大完工時(shí)間的兩代理排序問(wèn)題�；谖矬w尺寸為有限個(gè)的裝箱問(wèn)題的動(dòng)態(tài)規(guī)劃算法,我們給出了限制情形下兩代理排序問(wèn)題的PTAS。
[Abstract]:Scheduling problems are widely used in the fields of management science, computational science and control science. Agent ranking can make use of the basic method of game theory to tradeoff the objectives of each agent, and can also use the combinatorial optimization method to transform the multi-objective problem into a constrained optimization problem or a Pareto optimization problem or a single-objective optimization problem. In this paper, based on the constrained optimization model of two-agent scheduling, we study the two-agent scheduling problem in single machine and parallel machine environment. For a single machine environment, we study the two-agent scheduling problem in which the workpiece has the time to reach and the objective function is the maximum completion time. We prove that the problem is NP-hard by using partitioning problem, and then we design the PTAs for the restricted case. For parallel machine environment, we first study the problem that the two agent objective functions of m parallel machines are the sum of completion time, and design the quasi-polynomial time algorithm for this problem, and show that the problem is NP-hard in the common sense. Furthermore, based on the quasi-polynomial time algorithm, the FPTASs for the restricted case are given. Finally, we consider that the number of parallel machines m is not the input parameter, and the two agent objective functions are the two agent ordering problems with the maximum completion time. Based on the dynamic programming algorithm for the packing problem with finite size, we give the PTASs for the two-agent scheduling problem under restricted conditions.
【學(xué)位授予單位】：華東理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：O223

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 顧燕紅;唐國(guó)春;;排序博弈:合作博弈的新發(fā)展[J];重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年02期

2 何程;林詒勛;付乳燕;;具有雙工期的最小化最大延遲的雙目標(biāo)排序(英文)[J];工程數(shù)學(xué)學(xué)報(bào);2009年01期

3 慕運(yùn)動(dòng);皮軍德;郭曉;;序列錯(cuò)位限制下最小化完工時(shí)間和的繼列分批重新排序[J];大學(xué)數(shù)學(xué);2012年04期

4 李小襯;;單機(jī)不相容雙目標(biāo)最優(yōu)批排序研究[J];長(zhǎng)江大學(xué)學(xué)報(bào)(自科版);2013年13期

5 唐國(guó)春;樊保強(qiáng);劉麗麗;;排序博弈的分類(lèi)、進(jìn)展和展望[J];重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年01期

6 戴秦;鄭興山;張新功;嚴(yán)廣樂(lè);;總遲后相關(guān)的兩個(gè)工況代理的單機(jī)排序問(wèn)題[J];工業(yè)工程與管理;2014年06期

7 FENG Qi;LI Shi-sheng;SHANG Wei-ping;;Two-agent single machine scheduling with forbidden intervals[J];Applied Mathematics:A Journal of Chinese Universities(Series B);2015年01期

8 慕運(yùn)動(dòng);田曉正;;重新排序中目標(biāo)函數(shù)與錯(cuò)位量的Pareto最優(yōu)解[J];河南大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年05期

9 周艷平;顧幸生;;一類(lèi)流水車(chē)間調(diào)度問(wèn)題的合作博弈[J];化工學(xué)報(bào);2010年08期

10 慕運(yùn)動(dòng);許小艷;;重新排序問(wèn)題的Pareto最優(yōu)解[J];河南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年06期

相關(guān)會(huì)議論文 前4條

1 ;A Note on Two-agent Single-machine Scheduling Problem with Deteriorating Jobs[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

2 ;A Single-machine Scheduling Problem with Two Agents and Decreasing Linear Deteriorating Jobs[A];Proceedings of the 2011 Chinese Control and Decision Conference（CCDC）[C];2011年

3 ;Two Scheduling Problems of Two Agents' Jobs with Unit Processing Time and Different Release Dates[A];第六屆中國(guó)不確定系統(tǒng)年會(huì)論文集[C];2008年

4 劉曉惠;;一類(lèi)帶安裝時(shí)間的多客戶競(jìng)爭(zhēng)排序問(wèn)題[A];第十一屆中國(guó)青年信息與管理學(xué)者大會(huì)論文集[C];2009年

相關(guān)博士學(xué)位論文 前10條

1 丁國(guó)生;多代理競(jìng)爭(zhēng)排序問(wèn)題的研究[D];上海大學(xué);2009年

2 李士生;工件具有不相容性質(zhì)的機(jī)器排序問(wèn)題[D];鄭州大學(xué);2012年

3 慕運(yùn)動(dòng);關(guān)于重新排序問(wèn)題的研究[D];鄭州大學(xué);2007年

4 王林平;應(yīng)用齊套概念的離散制造業(yè)生產(chǎn)調(diào)度問(wèn)題研究[D];大連理工大學(xué);2009年

5 何程;多目標(biāo)分批排序及其相關(guān)課題[D];鄭州大學(xué);2009年

6 譚琦;多目標(biāo)優(yōu)化算法在多客戶批處理機(jī)環(huán)境下的應(yīng)用研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2012年

7 周艷平;基于博弈理論的多目標(biāo)生產(chǎn)調(diào)度問(wèn)題研究[D];華東理工大學(xué);2013年

8 常天田;裝配型供應(yīng)鏈調(diào)度與協(xié)調(diào)研究[D];青島大學(xué);2013年

9 馮琪;多個(gè)代理的機(jī)器排序問(wèn)題研究[D];鄭州大學(xué);2013年

10 王磊;OKP企業(yè)分散式項(xiàng)目計(jì)劃與調(diào)度優(yōu)化方法研究[D];哈爾濱工業(yè)大學(xué);2013年

相關(guān)碩士學(xué)位論文 前10條

1 李小襯;與雙目標(biāo)分批排序相關(guān)的排序問(wèn)題[D];蘭州大學(xué);2011年

2 王潔明;有關(guān)代理競(jìng)爭(zhēng)排序問(wèn)題的研究[D];華東理工大學(xué);2011年

3 宋鵬;面向承運(yùn)人與發(fā)貨人的調(diào)度博弈問(wèn)題研究[D];上海交通大學(xué);2011年

4 孫彬;基于無(wú)線傳輸?shù)墓卉?chē)載媒體節(jié)目管理系統(tǒng)研究與開(kāi)發(fā)[D];浙江工業(yè)大學(xué);2011年

5 馮琪;多目標(biāo)排序中的幾個(gè)結(jié)果[D];鄭州大學(xué);2005年

6 葛榮榮;基于非合作博弈的異構(gòu)目標(biāo)生產(chǎn)調(diào)度研究[D];上海交通大學(xué);2007年

7 關(guān)樹(shù)明;一類(lèi)與交貨期相關(guān)的多目標(biāo)排序問(wèn)題研究[D];武漢科技大學(xué);2007年

8 孫培;工件有到達(dá)時(shí)間的多代理排序問(wèn)題[D];鄭州大學(xué);2008年

9 張麗;一些分組工件排序問(wèn)題研究[D];鄭州大學(xué);2012年

10 王曉博;電爐生產(chǎn)過(guò)程能耗監(jiān)測(cè)與電耗智能分析方法的研究[D];長(zhǎng)春工業(yè)大學(xué);2012年

，

本文編號(hào)：2199096