5th Porto Meeting on MATHEMATICS for INDUSTRY

10th and 11th April 2014

Short Presentations

• 14h30 Rui Rei, "Tree Search for the Recursive Circle Packing Problem"
• 15h00 Margarida Carvalho, "Lot sizing games"
• 15h30 Filipe Brandão, "Bin Packing and Related Problems: General Arc-flow Formulation with Graph Compression"
• 16h00 Bruno Vieira, "Multi-criteria decisions on unit commitment"

16h30 Coffee break

• 17h00 Ana Carvalho, "Mathematical model for HIV dynamics in HIV-specific helper cells"
• 17h30 Isabel Cristina Lopes, "Scheduling aircrafts’ engine repair process: a mathematical model"
• 18h00 Eliana Costa e Silva "A Mathematical Model for Supermarket Order Picking"  

Abstracts

• Rui Rei, "Tree Search for the Recursive Circle Packing Problem"

Abstract: The Recursive Circle Packing Problem has direct practical application in the tube industry, where tubes of various inner and outer diameters must be packed in rectangular containers for shipping to customers. Although the problem can be posed in various ways, in this paper we focus on maximizing the total value of the tubes packed in a single container, allowing tubes to be placed inside other tubes recursively.
We explore the application of several variants of Tree Search to this problem, propose symmetry-breaking optimizations, and study the threshold of complete search using toy instances. Finally, we conduct a full computational experiment on a small set of benchmark instances, comparing adaptations of the proposed algorithms for incomplete search to previous results.

• Filipe Brandão, "Bin Packing and Related Problems: General Arc-flow Formulation with Graph Compression"

Abstract: We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems --- including multi-constraint variants --- by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without weakening the model. As opposed to our method, which provides strong models, conventional models are usually highly symmetric and provide very weak lower bounds.

Our formulation is equivalent to Gilmore and Gomory's, thus providing a very strong linear relaxation. However, instead of using column-generation in an iterative process, the method constructs a graph, where paths from the source to the target node represent every valid packing pattern. The same method, without any problem-specific parameterization, was used to solve a large variety of instances from several different cutting and packing problems. We report computational results obtained with many benchmark test data sets, all of them showing a large advantage of this formulation with respect to the traditional ones.

References:
Brandão, F. and Pedroso, J. P. (2013). Bin Packing and Related Problems:
General Arc-flow Formulation with Graph Compression. Technical Report
DCC-2013-08, Faculdade de Ciências da Universidade do Porto, Universidade do
Porto, Portugal. Available at: http://arxiv.org/abs/1310.6887

Brandão, F. and Pedroso, J. P. (2013). Multiple-choice Vector Bin Packing:
Arc-flow Formulation with Graph Compression. Technical Report DCC-2013-13,
Faculdade de Ciências da Universidade do Porto, Universidade do Porto, Portugal.

Brandão, F. and Pedroso, J. P. (2013). Cutting Stock with Binary Patterns:
Arc-flow Formulation with Graph Compression. Technical Report DCC-2013-09,
Faculdade de Ciências da Universidade do Porto, Universidade do Porto, Portugal.

Brandão, F. (2012). Bin Packing and Related Problems: Pattern-Based Approaches.
Master’s thesis, Faculdade de Ciências da Universidade do Porto, Portugal.

•  Isabel Cristina Lopes, "Scheduling aircrafts’ engine repair process: a mathematical model"

Authors:
Isabel Cristina Lopes,
UNIAG/ESEIG-IPP/UM

Eliana Costa e Silva,
CIICESI/ESTGF-IPP/UM/UPT

Jorge Orestes Cerdeira,
FCT-UNL/ISA-UTL

Abstract:
We address a real world scheduling problem concerning the repair process of aircrafts' engines by TAP - Maintenance & Engineering (TAP-ME), which is  the maintenance, repair and overhaul organization of TAP Portugal, Portugal's leading airline.
A mixed integer linear programming formulation based on the flexible job shop scheduling is presented, allowing operations to be executed on the same workstation by any processor of a  given set, with the objective of minimizing the total weighted tardiness.
Computational experiment on a real instance provided by TAP-ME from a regular working week was successful in finding an optimal solution. We also tested the model using benchmarking instances available in literature.

• Eliana Costa e Silva "A Mathematical Model for Supermarket Order Picking" 

Eliana Costa e Silva
CIICECI/ESTGF-IPP/UM, e-mail: eos@estgf.ipp.pt

Manuel Cruz
LEMA/ISEP-IPP, email: mbc@isep.ipp.pt

Isabel Cristina Lopes
UNIAG/ESEIG-IPP/UM, email: cristinalopes@eu.ipp.pt

Ana Moura
LEMA/ISEP-IPP and CMUP, email: aim@isep.ipp.pt

Order picking consists in the retrieving of a number of items from the storage locations to satisfy a number of independent customers' orders.  It is generally recognized as one of the most significant activities in a warehouse (Koster et al, 2007). According to different authors, the order picking accounts up to 50% (Frazelle, 2001) or even 80% (Van den Berg, 1999) of the total warehouse operating costs. The critical issue in today's business environment is to simultaneously reduce the cost and increase the speed of order picking. We address the problem of order picking in one of the Portuguese largest companies in the grocery business. Each operator steers the trolley on the shop floor to select items to multiple costumers. For each order, a picker may have to walk a considerable distance. This problem was proposed at the 92nd European Study Group with Industry (ESGI92). The objective is to improve their grocery e-commerce and bring it up to the level of the best internatio
 nal practices. In particular, the company wants to improve the routing tasks in order to decrease distances. For this purpose, a mathematical model for a faster open shop picking was developed. In this talk we describe the problem as well as some preliminary results and conclusions.