Một thuật toán lai giữa Ainet và tìm kiếm Tabu giải bài toán Single Row Facility Layout

Phiing Thi Thu Trang va Dtg T?p chl KHOA HOC & CONG NGH$ 162(02): 171 - 175

MOT THUAT TOAN LAI GIC A AINET VA TIM KIEM TABU GIAI BAI TOAN

SINGLE ROW FACILITY LAYOUT

Phiing Thj Thu Trang", Ngan Hoing My LinhS Vfl Diic Quang^

'Khoa Ngoai Ngir - DH Thdi Nguyen,

'Trudng Dai hoc supham - DH Thdi Nguyin

TOM TAT

Bki todn Single row facility layout \h mgt trong nhOng b^i todn tlm vj tri dSt co so quan trpng, khi

cac CO so dugc sSp xIp thing hang theo mgt tr^t tg nhit dinh sao cho chi phi di chuyen giQa cac co

so la nho nhSt. Bai toin da dugc chVmg minh la NP-kho va da c6 nhi^u thuat todn de xuat. Trong

bdi bdo nay, chiing toi Ah xudt thu|t todn lai gifta mang mien djch nhan t?io vd tim kiem Tabu cho

bai todn. Kit qua thil nghiem cho thSy, thuat toan moi d€ xuit cho ket qua tot hon vai thcri gian

ngin so vol mot so phuong ph^p da cong bo gdn iSy.

TCr khoa: He mien djch nhdn tgo, thugt todn aiNet, lim kiim Tabu, bdi todn vi tri ca sa

GlCil THIEU

Bai toan vi tri ca scf lien quan den viec tim

phuang an dat cac ca sis (ciia hang, ca quan,

nha may...) trong m^t khu v\rc de giam thieu

cdc lo^ii chi phi lien quan den sy tuong tac

giira cac co sa nhu chi phi v|n chuyen, chi

phi xay dyng, chi phi lien l^c.Vai mgt t^-p

cac ca so cho tru6c, bai toan Single Row

Facility Layout (SRFL) yeu cau tim each sip

xep chung dgc theo mgt duang thing de giam

thilu t6ng chi phi. Co rat nhieu bai toan thuc

tl d\ra tren bai toan SRFL nhu: s5p xIp vi tri

cac phong trong b?nh vi?n, sap xep cac phong

ban trong ca quan, sip xIp sach tren cac gia

sach trong thu vi?n,... [11].

SRFL la mgt bai toan thugc loai NP-kh6 va

da CO nhilu phuang phap chinh xdc cung nhu

xap xi dugc de xuat giai. Cdc phuang phap

chinh xac dugc cac tac gia cong bo nhu:

Simmon [19] dl xuat thu^t toan nhdnh can,

Armaral [5], [6] dl xuat thu$t toan quy hoach

nguyen, Kouvelis [13] de xuat thu^t toan quy

hoach dgng. Armaral [4] Al xuat phuang

phap sieu phSng cSt (cutting plane). Anjos

[1], [2], [3] dl xuat thu^t toan semidefinite

programing. Tuy nhiSn, cac phuang phap

chinh xac deu co dilm chung la g§p kho khan

khi giai quyet bai toan co khoi lugng tinh toan

va bo nhd luu tru 16n. Chinh vi v|y, cac thu^t

Tel: 01695 314806, Email: phungtkulrang sjl@tnu edu vi

toan heuristic va metaheuristic da dugc de

xuit lam giam chi phi tinh toan va thoi gian

chay ciia thuat toan ma van cho nhUng loi giai

chip nh^n dugc. Ravi Kothari va Diptesh

Ghosh da de xuat hai thuiit toan la Tabu-2opt

va Tabu-insert cho kit qua tot hon a mgt so

bg test [12], Solimanpur de xudt thuat toan

ACO [22] va PSO dugc Samarghandi dl xuat

[18]. Feristah Ozcelik da dl xu3t giai thusit lai

giiia giai thuat di truyen va tim kiem dia

phuang [17]. Sinem [20] dl xuit thuat toan

dan dai giai bai toan nhanh cho loi giai tot

trong thai gian ngan.

Opt-aiNet (Optimized Artificial Immune

Network) la thuat toan mang mien djch trong

h? miln djch nhan tao thudng su dyng dl giai

cac bai toan t6i uu tl hgp [8]. Thuat toan nay

sir dyng t|p cac khang thi (tuong tu nhu cac

ca thi trong giai thuat di truyen) qua qua trinh

tiin hoa san sinh ra cac khang the tot ban.

Tuy nhien, opt-aiNet co nhiing toan tii ma

trong GA (Genetic Algorithm) khong co nhu:

lo^ii thai khang thi kem, hay nhan rgng khang

thi tit,... Dilu nay giup cho thuiit toan opt￾aiNet cho kit qua tot hon thuat toan khac

trong mpt s6 truang hgp cy the [8]. Dya tren

^ tuang nhu v^y, chiing toi de xuat mgt thu|it

toan lai giQa thuat toan mang mien dich va

thuat toan tim kiem Tabu dl giai bai toan da

neu. Tinh hifu qua ciia thu^t toan dl xuat

dugc so sanh vai mgt so cong bo gan day,

171