Centre for Operational Research and Logistics

Events and Seminars

Research Seminar

Heuristics and Integer programming models for two applications in irregular shaped bin packing problems

The presentation will address the two-dimensional irregular shape bin packing problem. The first application arises in the glass cutting industry, for example, the cutting of glass for conservatories and as a result the packing must respect guillotine constraints. The second application is found in the ceramic industry, where pieces can be of any arbitrary shape. Almost all cutting and packing problems that include guillotine cuts deal with rectangles only, where all cuts are orthogonal to the edges of the stock sheet and a maximum of two angles of rotation are permitted. The literature tackling packing problems with irregular shapes largely focus on strip packing i.e. minimising the length of a single fixed width stock sheet, and does not consider guillotine cuts. Hence, the first problem combines the challenges of tackling the complexity of packing irregular pieces with free rotation, guaranteeing guillotine cuts that are not always orthogonal to the edges of the stock sheet, and allocating pieces to bins.

We present a hybrid algorithm that is a constructive heuristic that determines the relative position of pieces in the bin and guillotine constraints via a MIP model. We investigate two approaches for allocating guillotine cuts at the same time as determining the placement of the piece, and a two phase approach that delays the allocation of cuts to provide flexibility in space usage. Finally we describe an improvement procedure that is applied to each bin before it is closed. The second application relaxes the guillotine constraints and instead has to handle the issues of free rotation where pieces can be of any arbitrary shape. A similar MIP model is applied to place the pieces in the bin. However, in this approach pieces are preassigned to the bin by solving a one dimensional bin packing problems. Results for all these models will be presented.


Prof. Julia Bennell, Management School, University of Southampton


Lion Gate Building, LG 2.04C

Date and Time

Thu, 29 Jan 2015, 13:00 - 14:00 (BST)

For further information or any enquiries please contact our event co-ordinator, Jana Ries, at corl@port.ac.uk

Biography: Julia Bennell graduated in 1994 with a first class honours in mathematics and management science and received her PhD in Management Science in 1998 from the University of Wales. She was promoted to Prof of Management Science at the University of Southampton Management School in 2010. She is the director of CORMSIS (Centre of Operational Research, Management Science and Information Systems), one of the top three OR/MS research groups in the UK, that crosses the Management School and Mathematics, since 2011. She is Head of the Management Science Group in the Management School that includes around 27 academic staff since 2012. She is a member of the executive committee of the European working group on cutting and packing since 2005. She was chair of the executive committee of the Southern OR group between 2005-2009 and served on the general council of the OR society during that period.

Her main research interests are optimization models for logistics, specifically working in cutting and packing, vehicle routing, scheduling, network design and heuristic algorithms. She has published three invited review papers: two on cutting and packing in EJOR and JORS and one on runway scheduling in Annals of OR. She has also given keynote presentations in EURO 2009 and OR50 and invited to numerous workshops in these areas.

She has published over 35 papers in international journals including Management Science, European Journal of Operational Research, International journal of production research, International journal of production economics, Journal of heuristics, computers and OR, Journal of the operational research society. She has won just under £1m of research funding from a variety of sources including EPSRC (£320), BBSRC (£210) and KTP (£225). She has undertaken a variety of roles as guest editor, stream and session organiser, invited seminar speaker, and organised two international conferences in Southampton.