本文關(guān)鍵詞：一些單機(jī)和平行機(jī)排序情形的研究

  更多相關(guān)文章： 排序情形 特征函數(shù) 代價(jià)分配 夏普里值 EWCS規(guī)則

【摘要】：本文主要研究了一些單機(jī)排序情形和平行機(jī)排序情形。在一個(gè)排序情形中,一些工件需要在若干臺(tái)機(jī)器上加工,工件分別屬于不同的客戶�？蛻粼谒墓ぜ旯ぶ皶�(huì)產(chǎn)生代價(jià),在本文中代價(jià)是時(shí)間的線性函數(shù),即單位時(shí)間的代價(jià)保持一致,稱為客戶的權(quán)重。不同加工順序下客戶的代價(jià)不同。這個(gè)問題可以看成是多個(gè)參與人在做決策,選擇眾多可能工序中的一個(gè)作為最后執(zhí)行的工序,在達(dá)成協(xié)議的過程中還需協(xié)調(diào)利益沖突。在已有的文獻(xiàn)中,應(yīng)用合作博弈的理論去解排序情形產(chǎn)生的博弈被稱為排序博弈。通常采用收益博弈理論來討論排序情形,因此需要給出一個(gè)初始工序,在此基礎(chǔ)上客戶之間產(chǎn)生合作,并且盡量兼顧個(gè)人利益。然而初始工序強(qiáng)烈影響著客戶的最終支付,在初始工序中占據(jù)一個(gè)好的位置意味著較少的代價(jià)支付。本文主要討論無初始工序排序情形。我們主要研究一些排序情形對(duì)應(yīng)的排序博弈的特征、設(shè)計(jì)分配規(guī)則并分析最終支付的公平性。全文主要分為六部分內(nèi)容。第一章主要介紹了合作博弈論的基本思想和一些解的內(nèi)容,排序問題的三參數(shù)表示法以及算法相關(guān)的一些概念,并介紹了合作博弈在排序理論中的應(yīng)用這一課題的研究現(xiàn)狀。第二章采用成本博弈的方法研究了單機(jī)無約束排序情形,客戶的代價(jià)為工件的加權(quán)完工時(shí)間。與收益博弈不一樣,不需要給出初始工序。我們給出了一個(gè)基于任意加工順序的EWCS分配規(guī)則,并論證了這個(gè)規(guī)則的公平性,即這個(gè)規(guī)則會(huì)促使客戶選擇排序問題的最優(yōu)工序。此外,我們把這個(gè)規(guī)則推廣到單機(jī)帶鏈?zhǔn)絻?yōu)先約束的排序情形,并根據(jù)解的性質(zhì)做出一定的調(diào)整。第三章討論了單機(jī)工件有學(xué)習(xí)效應(yīng)的最大完工時(shí)間排序情形,這時(shí)每個(gè)客戶的代價(jià)為客戶的實(shí)際加工時(shí)間。假設(shè)初始工序?yàn)楹愕扰帕?該問題最終可歸納為排列博弈,或者是特殊的指派博弈,本文給出一個(gè)單值解。若沒有初始工序,則可引入指派博弈理論并給出一個(gè)基于指派博弈的核元素得到的解。第四章討論了兩臺(tái)機(jī)器上的排序情形,一個(gè)客戶恰好擁有兩個(gè)個(gè)工件且它們分別要在機(jī)器1和2上加工,客戶的代價(jià)為他對(duì)應(yīng)的工件的加權(quán)最大完工時(shí)間。對(duì)于客戶的兩個(gè)工件加工時(shí)間完全一致的特殊情形,其分配規(guī)則可沿用單機(jī)排序情形的EWCS規(guī)則。對(duì)一般情況,可采用啟發(fā)式算法編程求解最終加工順序,我們制定了依賴于工序的代價(jià)分配方法。第五章對(duì)m臺(tái)平行機(jī)的排序情形進(jìn)行了探討,由于對(duì)應(yīng)的排序問題是NP-難的,主要對(duì)兩種特殊情形的夏普里值計(jì)算進(jìn)行了推導(dǎo)：當(dāng)工件的加工時(shí)問一致時(shí)以及當(dāng)工件的權(quán)重完全一致時(shí),夏普里值的計(jì)算可在多項(xiàng)式時(shí)間內(nèi)完成。第六章對(duì)未來的研究方向做了一些展望,并對(duì)本文做了一個(gè)總結(jié)。
【學(xué)位授予單位】：華東理工大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：O223

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 張智聰;鄭力;翁小華;;基于增強(qiáng)學(xué)習(xí)的平行機(jī)調(diào)度研究[J];計(jì)算機(jī)集成制造系統(tǒng);2007年01期

2 陳榮軍;唐國春;;平行機(jī)的供應(yīng)鏈排序[J];系統(tǒng)科學(xué)與數(shù)學(xué);2010年02期

3 陳榮軍;張峰;唐國春;;平行機(jī)及自由作業(yè)的排序與轉(zhuǎn)包[J];系統(tǒng)工程學(xué)報(bào);2011年05期

4 陳榮軍;唐國春;;平行機(jī)的排序與轉(zhuǎn)包(英文)[J];數(shù)學(xué)季刊;2012年04期

5 蔣大奎;李波;;平行機(jī)作業(yè)環(huán)境下的訂單分配與排序[J];管理學(xué)報(bào);2013年06期

6 王成堯,汪定偉;有模機(jī)配合約束的平行機(jī)臺(tái)調(diào)度方法[J];東北大學(xué)學(xué)報(bào);1999年04期

7 曾歡歡,胡建華;可換速平行機(jī)工件帶起止值的搶先進(jìn)度表[J];數(shù)學(xué)理論與應(yīng)用;1999年02期

8 蔣大奎;李波;曹立思;;考慮轉(zhuǎn)包的平行機(jī)供應(yīng)鏈排序[J];控制與決策;2014年05期

9 陳仕平,張國川;兩臺(tái)平行機(jī)的實(shí)時(shí)到達(dá)在線排序[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2000年01期

10 周偉剛;高成修;黃凱;;加工時(shí)間可控和簡單線性增長的平行機(jī)排序[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2010年04期

中國重要會(huì)議論文全文數(shù)據(jù)庫 前1條

1 聞?wù)裥l(wèi);;一類平行機(jī)上的任務(wù)指派問題及其動(dòng)態(tài)規(guī)劃算法[A];中國運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前4條

1 劉珊珊;一些單機(jī)和平行機(jī)排序情形的研究[D];華東理工大學(xué);2015年

2 程貞敏;平行機(jī)調(diào)度問題研究的若干結(jié)果[D];北京師范大學(xué);2008年

3 蔡圣義;同類平行機(jī)在線半在線排序參數(shù)界的若干研究[D];浙江大學(xué);2010年

4 何龍敏;一類平行機(jī)和批處理機(jī)組成的二階段柔性流水作業(yè)問題[D];上海大學(xué);2006年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 郭平寧;工件帶權(quán)重的平行機(jī)博弈排序問題[D];曲阜師范大學(xué);2015年

2 李大偉;考慮延誤的平行機(jī)可拒絕排序[D];曲阜師范大學(xué);2015年

3 洪文益;與平行機(jī)排序相關(guān)的幾個(gè)組合問題研究[D];清華大學(xué);2013年

4 李松松;在平行機(jī)博弈排序中的近似強(qiáng)納什均衡問題[D];曲阜師范大學(xué);2013年

5 王君麗;有加工權(quán)限平行機(jī)在線問題研究[D];浙江大學(xué);2012年

6 財(cái)玉華;具有非交叉維修時(shí)間的平行機(jī)在線排序[D];鄭州大學(xué);2007年

7 莫禎貞;改進(jìn)粒子群算法在模糊環(huán)境下平行機(jī)批調(diào)度問題中的應(yīng)用研究[D];中國科學(xué)技術(shù)大學(xué);2010年

8 林琳;具有同時(shí)性約束的平行機(jī)排序問題[D];鄭州大學(xué);2006年

9 徐武來;具有完工期和工裝數(shù)量約束的平行機(jī)調(diào)度方法[D];廣東工業(yè)大學(xué);2012年

10 何曉瓊;一致平行機(jī)上在線排序[D];湖南師范大學(xué);2009年

，

本文編號(hào)：1202629