BỘGIÁODỤCVIỆNHÀNLÂMKHOAHỌCVÀĐÀOTẠOVÀCÔNGNGHỆVIỆTNAMHỌCVIỆNKHOAHỌCVÀCÔNGNGHỆ-----------------NguyễnThanhHòaBÀITOÁNSẮPXẾPKHOVẬNVỚIRÀNGBUỘCSẮPXẾPChuyênngành:ToánứngdụngMãsố:8460112TÓMTẮTLUẬNVĂNTHẠCSĨTOÁNHỌCHàNội-2021
Côngtrìnhđượchoànthànhtại:HọcviệnKhoahọcvàCôngnghệ-ViệnHànlâmKhoahọcvàCôngnghệViệtNam.Ngườihướngdẫnkhoahọc:TiếnsĩLêXuânThanhPhảnbiện1:TiếnsĩLêHảiYếnPhảnbiện2:TiếnsĩNguyễnĐứcMạnhLuậnvănđượcbảovệtrướcHộiđồngchấmluậnvănhọptạiViệnHànlâmKhoahọcvàCôngnghệViệtNamvàohồi9giờ00phútngày12tháng11năm2021Cóthểtìmhiểuluậnvăntại:-ThưviệnHọcviệnKhoahọcvàCôngnghệ.
1MởđầuVớimộtlượnghànghóakhổnglồđượcsắpxếpvàluânchuyểnquacácbếncảngtrênthếgiớihàngngày,chúngtađangchứngkiếnsựbùngnổcủathươngmạiquốctếvàchuỗicungứngtoàncầu.Dođó,việcquảnlývàsắpxếphànghóamộtcáchhiệuquảtrongcácbếncảngngàycàngtrởnênquantrọngvàthiếtyếu.Cáchoạtđộngkhovậntạicácbếncảngcóthểđượcphânloạitheocácloạihìnhsauđây:sắpxếpcáchànghóacậpbếnvàotrongkhuvựckhobãi,bốcdỡcáchànghóatrongkhuvựckhobãiđểvậnchuyểnđếncácđiểmđếnkhác,sắpxếplạicáchànghóatrongcùngmộtkhuvựckhobãi,kếthợpsắpxếpvàbốcdỡhànghóakhimộtsốhànghóacầnđượcsắpxếpvàokhuvựckhobãitrongkhimộtsốhànghóacầnđượcbốcdỡkhỏikhuvựcđó.Trongcácloạihìnhhoạtđộngkhovậnđó,việcsắpxếphànghóacậpbếnvàotrongkhuvựckhobãiđóngvaitròtrungtâm,vìhiệuquảcủahoạtđộngđóảnhhưởngtớihiệuquảcủacáchoạtđộngkhác.Sắpxếpkhovậnlàbàitoánxuấthiệntrongnhiềungữcảnhthựctế(chẳnghạnnhưtrongcáccảngcontainer,cáctàucon-tainer,cáctrạmđỗtàuđiện).Dođó,bàitoánsắpxếpkhovậnđãtrởthànhđốitượngnghiêncứucủamộthướngchínhtrongvậntrùhọc(nhưđãchỉratrongbàibáotổngquan[1]).Trongphầngiớithiệucủabàibáo[2],cáctácgiảđãtrìnhbàymộttổngquancậpnhậtcácnghiêncứuvềchủđềnày:từthiếtkếcủakhuvựckhobãiđếnsựcânbằngvậtlýcủacáccấuhìnhsắpxếp,từđộphứctạptínhtoánđếnphươngphápgiảimộtsốlớpbàitoánnày,
2từcácbàitoánvớidữliệuchắcchắnđếncácbàitoánvớidữliệukhôngchắcchắn,v.v...Trongphầntiếptheocủabàibáo,cáctácgiảđãtổngquáthóamộtsốbiếnthểcủabàitoánsắpxếpkhovận,vànghiêncứubàitoánnàyvớicácràngbuộcsắpxếp.Sửdụngbàibáo[2]làmtàiliệuthamkhảochính,trongluậnvănnày,chúngtôinghiêncứumộtsốbàitoántốiưuliênquanđếnhoạtđộngsắpxếpkhovận.Môtảmộtcáchngắngọn,trongcácbàitoánđượcchúngtôinghiêncứu,chotrướcmộtkhuvựckhobãiđượctổchứcdướidạngcácngănxếp(stack).Khuvựckhobãinàyđãchứasẵnmộtsốhànghóa(items).Hànghóađếnbếncảngtheomộtdãycáctậphợpvàcầnđượcsắpxếpvàokhuvựckhobãi.Cácràngbuộcmangtínhkỹthuậtđốivớiquátrìnhsắpxếphànghóavàokhobãibaogồm:•Trongmỗingănxếp,cáchànghóađượcsắpxếptheothứtựvàosauratrước(last-in-first-out).•Cácngănxếpcócùngchiềucao,haychínhxáchơnlàcócùngsốhànghóacóthểchứatrongngănxếp.•Cácràngbuộcsắpxếpđượcchotrước,trongđóquyđịnhhànghóanàođượcsắpxếplêntrênhànghóanào.Chúngtôiquantâmđếncácmụctiêusau.•Tốithiểutổngsốngănxếpđượcsửdụng.•Tốithiểutổngsốhànghóađượcsắpxếpởvịtríkhôngthuậnlợichoviệcbốcdỡtheothứtựthờigianxuấtbến.
3Chương1Môtảbàitoán1.1KhuvựcsắpxếpChúngtađượcchotrướcmộtkhuvựckhobãi(còngọilàkhuvựcsắpxếp)đượctổchứcdướidạngmngănxếp(stack),mỗingănxếpcóvịtrícốđịnh.TậphợpcácngănxếpđượckýhiệulàQ={1, . . . , m}.Mỗingănxếpcóbtầng(level),vàtậphợpcáctầngtrongmộtngănxếpđượckýhiệulàL={1, . . . , b}.Nhưvậymỗingănxếpcóthểchứađượctốiđabđơnvịhànghóa.Hànghóađượcsắpxếpvàotrongcácngănxếptheothứtựvàosauratrước.Mỗiđơnvịhànghóađượcxếpvàotrongmộttầngnàođócủamộtngănxếp.Hànghóaphảiđượcđặttrênmặtđất,hoặctrênmộtđơnvịhànghóakhácđãđượcđặttrongkhuvựcsắpxếp.1.2ThứtựsắpxếpCótấtcảnhànghóatrongtậphợpI={1, . . . , n},đượcphânhoạchthànhhaitậphợp:Ifix chứacáchànghóađãđượcsắpxếpsẵntrongkhuvựcsắpxếp,I∗chứacáchànghóacònlạiđangchờđượcsắpxếpvàokhobãi.CấuhìnhsắpxếpcủahànghóatrongtậphợpIf ix đượcchotrướccốđịnh.HànghóatrongtậphợpI∗