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

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

2、能的構(gòu)形進行枚舉，并給出一個0 ( 2 ‘n l o g k n 2 ) 時間的算法求解L 。。最優(yōu)值．最后對于問題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 ％，∑乃，∑嶼乃) 時，給出了一個0 ( 2 ‘n ) 時間算法．當(dāng)k 為一固定值時，這兩個問題是多項式可解的．(

3、 2 ) 具有到達時間，加工時間相同極小化加權(quán)總誤工的單機平行批排序問題．B a p t i s t e 在【5 l 中給出了問題l i P - b a t c h ；b < n ；乃= p ；r j I ，，，∈{ ∑w j ％，∑喲G ，∑T j }的一個o ( n s ) 時間的動態(tài)規(guī)劃算法，并指出對于目標函數(shù)∑嘶T j ，平行批等長工件問題的計算復(fù)雜性仍是未解的．本文中，我們將討論問題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ù)與工期是反一致的．此時，通過適當(dāng)?shù)男拚?，∑t 吩乃就為一個有序的目標函數(shù)，這使得我們的排序問題具有特定的優(yōu)勢性質(zhì)．其次，建立動態(tài)規(guī)劃參數(shù)及方程，給出一個O ( b 2 n 7 ) ( b < n ) 的時間動態(tài)規(guī)劃算法求解最優(yōu)值．關(guān)鍵詞：單機；排序；平行批；工期；最大延遲；優(yōu)先約束；