求解裝箱問題的遺傳算法-南昌航空大學期刊網

1998 2 Journal of Nanchang Institute of Aeronautical Technology 21998

方　平　　　　李　娟

( 南昌航空工業學院) 　( 西北工業大學)

: ( Bin Packing) ,

, , D( irst it De-

creasing) ,

: ; ; ;

: TP301. 6

( )

( Bin Packing) , :

1 2 n i

n u , u , , u , v ( u ) (0, 1] ,

( i = 1, 2, , n) 1, n

?

, NP ,

, ( ) ( ) (

N Next it irst it D irst it Decreas-

[ 1]

ing) ,

, ,

D

1

1. 1

B 1,B2 , ,B k , ( K n) n k ,

k

, , k

ui ( i = 1, 2, , n) ,

收稿日期: 1988- 04- 10　　　　　第一作者: 方平, 男, 1962 年出生, 講師

21

:

3 1 8 1 3 1

B B B B B B

n

( ) , 1n - 1B 3 ; 24n

B 1 ; 3B 8 , B 1,B2 , ,B k

1. 2

i i j

m ,B ( u ) u ,S

Bj ,

:

m m

f (X ) = m (m - sj ) = m {m - [ v ( ui) - max( 0, v ( ui) - 1) ] }

j = 1 j = 1 B ( u ) = B B ( u ) = B

i j i j

Bj

,

:

Cmax - f (X ) ,f (X ) < Cmax

g ( X ) =

0 , F (X ) Cmax

Cmax ,

1. 3

[ 2]

, ;

;

2

,

, ,

, ,

D , , D

, ,

D : ,

; ,

D

:

( 1)

(2) B i ,

B i+ 1

22

( 3) Bm ,

, m m