具有等長(zhǎng)工件平行批排序模型的一些結(jié)果.pdf

1、授予單位代碼： ! ! ! i !研究生學(xué)號(hào)：——密 級(jí)：鄭州大學(xué)碩士學(xué)位論文論文題 目： 具有等長(zhǎng)工件平行批排序模型的一些結(jié)果作者姓名：學(xué)科門(mén)類(lèi)：專(zhuān)業(yè)名稱(chēng)：研究方向：導(dǎo)師姓名、職稱(chēng)：孫曉梅理 學(xué)運(yùn)籌學(xué)與控制論圖論與組合最優(yōu)化原晉江教授二零零七年四月形是這樣的時(shí)間序列( r ( ”，r ( ”，?，r ( ”a ’) ( 1s T ／b s 后) ，其中r ( ‘’∈{ 7 ( 1 ) ，7 ㈣?，7 ( ^ ) ) ．其次，對(duì)于所有可

2、能的構(gòu)形進(jìn)行枚舉，并給出一個(gè)0 ( 2 ‘n l o g k n 2 ) 時(shí)間的算法求解L 。。最優(yōu)值．最后對(duì)于問(wèn)題1 I p r e c ；p - b a t c h ；P j = p ；7 ( { ) ，iE { 1 ，2 ，?：k } l f ，當(dāng)，為和函數(shù)∑厶形式，即，∈{ ∑w 3 G ，∑G ，∑u j ，∑q ％，∑乃，∑嶼乃) 時(shí)，給出了一個(gè)0 ( 2 ‘n ) 時(shí)間算法．當(dāng)k 為一固定值時(shí)，這兩個(gè)問(wèn)題是多項(xiàng)式可解的．(

3、 2 ) 具有到達(dá)時(shí)間，加工時(shí)間相同極小化加權(quán)總誤工的單機(jī)平行批排序問(wèn)題．B a p t i s t e 在【5 l 中給出了問(wèn)題l i P - b a t c h ；b < n ；乃= p ；r j I ，，，∈{ ∑w j ％，∑喲G ，∑T j }的一個(gè)o ( n s ) 時(shí)間的動(dòng)態(tài)規(guī)劃算法，并指出對(duì)于目標(biāo)函數(shù)∑嘶T j ，平行批等長(zhǎng)工件問(wèn)題的計(jì)算復(fù)雜性仍是未解的．本文中，我們將討論問(wèn)題l i P - b a t c h ；

4、b < n ；P i =p ；r l I ∑嘶乃．首先，我們假設(shè)W l ≥W 2 ≥?2W n 且d ls d 2 ≤?sd n ，即工件的權(quán)數(shù)與工期是反一致的．此時(shí)，通過(guò)適當(dāng)?shù)男拚?，∑t 吩乃就為一個(gè)有序的目標(biāo)函數(shù)，這使得我們的排序問(wèn)題具有特定的優(yōu)勢(shì)性質(zhì)．其次，建立動(dòng)態(tài)規(guī)劃參數(shù)及方程，給出一個(gè)O ( b 2 n 7 ) ( b < n ) 的時(shí)間動(dòng)態(tài)規(guī)劃算法求解最優(yōu)值．關(guān)鍵詞：?jiǎn)螜C(jī)；排序；平行批；工期；最大延遲；優(yōu)先約束；