文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Two-dimensional packing problems A survey
侵权投诉

Two-dimensional packing problems A survey

Two-dimensional packing problems A survey

EuropeanJournalofOperationalResearch141(2002)

Two-dimensional packing problems A survey

Two-dimensional packing problems A survey

241–252

InvitedReview

Two-dimensionalpackingproblems:Asurvey

AndreaLodi*,SilvanoMartello,MicheleMonaci

DipartimentodiElettronica,InformaticaeSistemistica,UniversityofBologna,VialeRisorgimento2,40136Bologna,Italy

Received9March2001

Abstract

Weconsiderproblemsrequiringtoallocateasetofrectangularitemstolargerrectangularstandardizedunitsbyminimizingthewaste.Intwo-dimensionalbinpackingproblemstheseunitsare niterectangles,andtheobjectiveistopackalltheitemsintotheminimumnumberofunits,whileintwo-dimensionalstrippackingproblemsthereisasinglestandardizedunitofgivenwidth,andtheobjectiveistopackalltheitemswithintheminimumheight.Wediscussmathematicalmodels,andsurveylowerbounds,classicalapproximationalgorithms,recentheuristicandmetaheuristicmethodsandexactenumerativeapproaches.Therelevantspecialcaseswheretheitemshavetobepackedintorowsforminglevelsarealsodiscussedindetail.Ó2002ElsevierScienceB.V.Allrightsreserved.

Keywords:Two-dimensionalpacking;Binpackingproblems;Strippackingproblems

1.Introduction

Inseveralindustrialapplicationsoneisrequiredtoallocateasetofrectangularitemstolargerrectangularstandardizedstockunitsbyminimi-zingthewaste.Inwoodorglassindustries,rect-angularcomponentshavetobecutfromlargesheetsofmaterial.Inwarehousingcontexts,goodshavetobeplacedonshelves.Innewspaperspaging,articlesandadvertisementshavetobear-rangedinpages.Intheseapplications,thestan-dardizedstockunitsarerectangles,andacommonobjectivefunctionistopackalltherequesteditems

Correspondingauthor.Tel.:+39-051-209-3029;fax:+39-051-209-3073.

E-mailaddresses:alodi@deis.unibo.it(A.Lodi),smar-tello@deis.unibo.it(S.Martello),mmonaci@deis.unibo.it(M.Monaci).

*

intotheminimumnumberofunits:theresultingoptimizationproblemsareknowninthelitera-tureastwo-dimensionalbinpackingproblems.Inothercontexts,suchaspaperorclothindustries,wehaveinsteadasinglestandardizedunit(arollofmaterial),andtheobjectiveistoobtaintheitemsbyusingtheminimumrolllength:theprob-lemsarethenreferredtoastwo-dimensionalstrippackingproblems.Aswewillseeinthefollow-ing,thetwoproblemshaveastrictrelationinalmostallalgorithmicapproachestotheirsolu-tion.

Mostofthecontributionsintheliteraturearedevotedtothecasewheretheitemstobepackedhavea xedorientationwithrespecttothestockunit(s),i.e.,oneisnotallowedtorotatethem.Thiscase,whichistheobjectofthepresentarticle,re- ectsanumberofpracticalcontexts,suchasthecuttingofcorrugatedordecoratedmaterial(wood,glass,clothindustries),orthenewspaperspaging.

0377-2217/02/$-seefrontmatterÓ2002ElsevierScienceB.V.Allrightsreserved.

PII:S0377-2217(02)00123-6

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email