m臺同類機在線排序問題研究.pdf

1、浙江大學理學院碩士學位論文m臺同類機在線排序問題研究姓名：陳思霞申請學位級別：碩士專業(yè)：運籌學與控制論指導(dǎo)教師：談之奕20070501m 臺同類機在線排序問題研究A b s t r a c tT h i st h e s i sm a i n l yo o n c e r l l S o n l i n eu r n f o r mm a c h i n e s c h e d u l i n gp r o b l e m s ．W e

2、 I n ' s ti n t r o d u c e b a s i c n o t i o n s o f s c h e d u l i n g p r o b l e m , a p p r o x i m a t i o n a l g o r i t h m s a n dc o m p e t i t i v e a n a l y s i s ．I n C h a p t e r 2 ，w e i n v e s

3、 t i g a t eo n l i n ec o v e r i n gp r o b l e m O n m u n i f o r m m a c h i n e s ，t h eo b j e c t i v e i s t o m a x i m i z et h em i n j m u l nl o a d o f 腳m a c h i n e s ．W ea n a l y z e t h ep a r a m e t

4、 r i c l o w e r b o u n d f o r t h ep r o b l e m a n d t h e p a r a m e t r i c c o m p e t i t i o nr a t i of o r L S ja l g o r i t h m ．W ep r o v e t h a t L s ，i s t h e b e s tp o s s i b l e O n —l i n ea l g

5、 o r i t h mf o rt h i sp r o b l e m ．1 1 1 e p a r a m e 伍c 唧曬廿v c 咖i 0 訌再5 ，’I nC h a p t e r 3 ，w e f i s ti n v e s t i g a t e o n l i n es c h e d u l i n g p r o b l e m 0 1 1 m u n i f o r mm a c h i n e s ，也co

6、b j c c t i v e i s t o m i n i m i z et h em a x i m u mm a c h i n e c o m p l e t i o nt i m e ．W ep r o v e t h a tt h ep a r a m e t r i c c o m p e t i t i o nr a t i of o r L S 。a l g o r i t h m f o rt h eg e n e

7、 r a lp r o b l e m ，i ．e ．t h e s p e ．／．, d so f t h e m a c h i n e s a t e 吼，s 2 9 , o o ) s m ( ^ 5 s 2 ‘?‘5 ．) ，i s l e s s t h a n∑s 』喁沏一七)m i n 上l _ —————一． “五”薹s ，T h e nw e p r o v e t h ep a r a m e t r i c l

8、o w e r b o u n d f b f t h ep r o b l e m o f t h r e e s p e c i a lm a c h i n e s ．i ．e ．t h eS p e e d s o f t h e m a c h i n e s a r e 1 , 1 ，s ( 1 < s < 2 ) ，i s! ：；壟堅 1 。。。。，s 。+ 2 a—s 2 + —3 $ 口《s ‘壓一1 ，s

9、 + 2’_ s + 2 壓一1 《J s 壓， 2’半 壓t s ‘下, J 5 + 1 ， 5 Zs —, f 5 —+ 1 。5 。2 ． S 一‘5 ‘Z ．K e y W o r d s ：S c h e d u l i n g , O n —l i n e ，P a r a m e t r i c c o m p e t i t i o nr a t i o a n a l y s i s ，P a r a m e t r