染色裝箱問題的相關(guān)研究.pdf

1、浙江大學(xué)理學(xué)院碩士學(xué)位論文染色裝箱問題的相關(guān)研究姓名：王鐘申請學(xué)位級別：碩士專業(yè)：運籌與控制論指導(dǎo)教師：張國川20070501A b s t r a c tB i n P a c k i n g i so n e o ft h e c l a s s i c a l c o m b i n a t o r i a l o p t i m i z a t i o n p r o b l e m s ．I t h a s b e e ne

2、x t e n s i v e l ys t u d i e d i nt h e p a s t a n d s h o w n i t si m p o r t a n c e i np r a c t i c a l a p p l i c a t i o n s d u r -i n g t h e d a i l y l i f e ．I n p r a c t i c e , t h e r e a r e m a n y

3、c o m p l i c a t e d v a r i a n t s w i t h m o r e o r c h a n g e dc o n s t r a i n t s t h a tm a k e s t h e m h a r d e r t h a n t h e c l a s s i c a lB i n P a c k i n g p r o b l e m ．I nt h i sp a p e r , w

4、e p r e s e n t a n i n t e r e s t i n g v a r i a n to ft h e p a c k i n g p r o b l e m a n d i t ss u b -p r o b l e m —M i n i m i z et h en u m b e r o fb i n s w i t ha r b i t r a r yc o l o r i n g c o n s t r

5、a i n t ( 2 c o l o r i n gc o n s t r a i n tr e s p e c t i v e l y ) ．O u r b i nc o l o r i n gp r o b l e m s a r e m o t i v a t e df r o m s e v e r a la p p l i -c a t i o n s i nn e t w o r k i n g a n dt r a n

6、s p o r t a t i o ni ns u p p l yc h a i n ．F o rE x a m p l e , w e n e e d t oe n c a p s u l a t e m a n y d a t ai n t o a p a c k e t i n n e t w o r k w h e n w e w a n t t o t r a n s m i tt h e m t oo t h -e r s

7、．I n s u c h a p p l i c a t i o n s ，e a c ht y p e o f i t e m s r e p r e s e n t s a l lt h e p a c k e t s f r o m a s i n g l e u s e r( o r a s i n g l et a s k ) a n d e a c h b i n r e p r e s e n t sa b u r s t

8、 o r a c h a n n e l ．B y m i n i m i z i n g t h e h i ．i n l -b e r o fb i n s u s e di nO U I c e r t a i nB i nC o l o r i n g P r o b l e m ，w e c a n m a x i m i z e t h ee f f i c i e n c yo ft h e t o t a l n e t

9、 w o r k ．I n t h i sp a p e r , w e c o n s i d e r t h e d u a l p r o b l e m o fm i n i m i z i n g t h e d i f f e r e n t n u m b e r o fc o l o r sa n d i t ss u b p r o b l e r a ．O u r o b j e c t i sm i n i m i

10、 z i n g t h en u m b e r o f b i n s u s e du n d e r t h ec o l o r c o n s t r a i n t s ．D i s c u s s i n gt h ep r o b l e mt h a t t h e c o l o rc o n s t r a i n ti so n l y2 ，w es h o wt h a t t h i sc a s ei s

11、N P - C o m p l e t e a n d g i v e a l i n e a ra l g o r i t h m w i t h a p p r o x i m a t i o n 4 ／3r a t i o ·A t l a s t , w ed i s c u s st h eg e n e r a lc a s et h a tt h ec o l o rc o n s t r a i n t i s