 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 6 | 1/1 | 返回列表 |
| 查看: 1417 | 回復: 5 | |||
lichengjun金蟲 (初入文壇)
|
[求助]
[求助] 一個非典型的排序問題
|
|
小弟非數(shù)學專業(yè)，遇到一個非典型的排序問題，之前也沒有接觸過太多排序論的知識，故希望各位蟲友能幫忙解答。 首先有2個機器，N個工件，每個工件都要在這兩個機器上加工。給定每個工件在兩個機器上的加工時間P_{in} ，n表示工件個數(shù)，i表示機器個數(shù)。 和一般的工件加工不一樣，這里兩個機器可以同時加工一個工件，而我希望找到一個排序（這個順序在兩個機器上是相同的），使得在最短的完工時間內，每個工件在兩個機器上的加工時間之和最短。 T_{in}^{1}是任務P_{in} 在i機器上的開始時間，T_{in}^{2} 是任務P_{in} 在i機器上的結束時間。 這個問題的數(shù)學表示如下，其中max(T_{1n}^{2},T_{2n}^{2})-min(T_{1n}^{1},T_{2n}^{1}) 表示的就是每個工件的在線加工時間。 求一個排序σ，使得min\sum_{n=1}^{N}[max(T_{1n}^{2},T_{2n}^{2})-min(T_{1n}^{1},T_{2n}^{1})] ， 其中： T_{in}^{2} - T_{in}^{1} = P_{in} \underset{1\leq n\leq N}{MAX}(T_{in}^{2})=\sum_{n=1}^{N}P_{in} 其中i=1，2； \forall k (1\leq k\leq N-1),T_{i\sigma (k)}^{2}= T_{i\sigma (k+1)}^{1} 而我的疑惑是，如何證明這個問題是否是一個NP問題（我個人直觀認為是NP問題），如果是，最好能給出證明方法；如果不是，則最好能給出最優(yōu)方法。 您的任何一個建議都不甚感激！ |
回復此樓» 猜你喜歡
281求調劑（0805）
已經(jīng)有8人回復
-
環(huán)境領域全國重點實驗室招收博士1-2名
已經(jīng)有3人回復
-
材料專碩306英一數(shù)二
已經(jīng)有10人回復
-
301求調劑
已經(jīng)有6人回復
-
一志愿天津大學化學工藝專業(yè)（081702）315分求調劑
已經(jīng)有7人回復
-
302求調劑
已經(jīng)有6人回復
-
26博士申請
已經(jīng)有3人回復
-
268求調劑
已經(jīng)有3人回復
-
311求調劑
已經(jīng)有10人回復
-
被我言中：新模板不強調格式了，假專家開始管格式了
已經(jīng)有4人回復
» 本主題相關價值貼推薦，對您同樣有幫助:
- 發(fā)表SCI，作者排序問題
已經(jīng)有53人回復
- 關于參考文獻中第一作者和通訊作者的排序問題
已經(jīng)有3人回復
- 關于評審意見的排序問題
已經(jīng)有3人回復
- 關于工作基礎的作者排序問題
已經(jīng)有28人回復
- 青基人員排序問題
已經(jīng)有16人回復
- 【原創(chuàng)】求助博士期間文章發(fā)表作者排序問題
已經(jīng)有32人回復
- endnote排序混亂問題
已經(jīng)有9人回復
- 關于正交表的某一因素的水平排序問題
已經(jīng)有3人回復
- 轉帖 數(shù)量關系中排列組合問題的七大解題策略
已經(jīng)有6人回復
lichengjun
金蟲 (初入文壇)
- 應助: 0 (幼兒園)
- 金幣: 830.5
- 帖子: 17
- 在線: 32小時
- 蟲號: 1423137
- 注冊: 2011-09-30
- 專業(yè): 通信理論與系統(tǒng)
| 公式看不太清楚，我傳附件里。。。 |
» 本帖附件資源列表
-
歡迎監(jiān)督和反饋：小木蟲僅提供交流平臺，不對該內容負責。
本內容由用戶自主發(fā)布，如果其內容涉及到知識產(chǎn)權問題，其責任在于用戶本人，如對版權有異議，請聯(lián)系郵箱：xiaomuchong@tal.com - 附件 1 : 一個非典型的排序問題.docx
2012-05-01 22:58:45, 27.99 K
2樓2012-05-01 22:58:47
3樓2012-05-02 10:56:09
lichengjun
金蟲 (初入文壇)
- 應助: 0 (幼兒園)
- 金幣: 830.5
- 帖子: 17
- 在線: 32小時
- 蟲號: 1423137
- 注冊: 2011-09-30
- 專業(yè): 通信理論與系統(tǒng)
4樓2012-05-02 12:46:28
liuhl2012
木蟲 (職業(yè)作家)
- 應助: 31 (小學生)
- 金幣: 2604.5
- 散金: 10
- 紅花: 3
- 沙發(fā): 1
- 帖子: 3090
- 在線: 70.1小時
- 蟲號: 1795435
- 注冊: 2012-05-04
- 專業(yè): 通信理論與系統(tǒng)
5樓2012-05-05 10:45:24
lichengjun
金蟲 (初入文壇)
- 應助: 0 (幼兒園)
- 金幣: 830.5
- 帖子: 17
- 在線: 32小時
- 蟲號: 1423137
- 注冊: 2011-09-30
- 專業(yè): 通信理論與系統(tǒng)
6樓2012-05-06 15:54:33
相關版塊跳轉
我要訂閱樓主 lichengjun 的主題更新
| 6 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 301求調劑 +6 | yy要上岸呀 2026-03-17 | 6/300 |
|
|---|---|---|---|---|
|
|
[考研] 326求調劑 +5 | 上岸的小葡 2026-03-15 | 6/300 |
|
|
|
[考研] 化學工程321分求調劑 +11 | 大米飯！ 2026-03-15 | 14/700 |
|
|
[考研] 085600材料與化工求調劑 +5 | 緒幸與子 2026-03-17 | 5/250 |
|
|
|
[考研] 工科材料085601 279求調劑 +3 | 困于星晨 2026-03-17 | 3/150 |
|
|
|
[考研] 267一志愿南京工業(yè)大學0817化工求調劑 +6 | SUICHILD 2026-03-12 | 6/300 |
|
|
|
[考研]
 11408 一志愿西電，277分求調劑
+3
|
zhouzhen654 2026-03-16 | 3/150 |
|
|
|
[考研] 環(huán)境工程調劑 +6 | 大可digkids 2026-03-16 | 6/300 |
|
|
|
[考研] 318求調劑 +3 | Yanyali 2026-03-15 | 3/150 |
|
|
|
[考研] 327求調劑 +6 | 拾光任染 2026-03-15 | 11/550 |
|
|
|
[考研] 255求調劑 +3 | 李嘉慧， 2026-03-12 | 4/200 |
|
|
|
[考研] 招收0805（材料）調劑 +3 | 18595523086 2026-03-13 | 3/150 |
|
|
|
[考研] 一志愿211化學學碩310分求調劑 +8 | 努力奮斗112 2026-03-12 | 9/450 |
|
|
|
[考研] 314求調劑 +7 | 無懈可擊的巨人 2026-03-12 | 7/350 |
|
|
|
[考研] 工科調劑 +4 | Jiang191123！ 2026-03-11 | 4/200 |
|
|
|
[考研] 土木第一志愿276求調劑，科研和技能十分豐富，求新興方向的導師收留 +3 | 土木小天才 2026-03-12 | 3/150 |
|
|
|
[考研] 308求調劑 +3 | 是Lupa啊 2026-03-12 | 3/150 |
|
|
|
[考研] 070303一志愿西北大學學碩310找調劑 +3 | d如愿上岸 2026-03-13 | 3/150 |
|
|
|
[考研] 290求調劑 +3 | ADT 2026-03-13 | 3/150 |
|
|
|
[考博] 26讀博 +4 | Rui135246 2026-03-12 | 10/500 |
|