Centre for Operational Research and Logistics

Events and Seminars

Research Seminar

Split-Merge: Using Exponential Neighborhood Search for Scheduling a Batching Machine

This study addresses the problem of scheduling a single batching machine to minimize the maximum lateness with a constraint restricting the batch size. A solution for this NP-hard problem is designed by a selection of jobs for each batch and an ordering of those batches. As an alternative, we choose to represent a solution as a sequence of jobs. This approach is justified by our development of a dynamic program to search a schedule that minimizes the maximum lateness while preserving the underlying job order. Given this solution representation, we are able to de ne and evaluate various job-insert and job-swap neighborhood searches. Furthermore we introduce a new neighborhood, named split-merge, that allows multiple job inserts in a single move.

The split-merge neighborhood is of exponential size, but can be searched in polynomial time by dynamic programming. Computational results with an iterated descent algorithm that employs the split-merge neighborhood show that it compares favourably with corresponding iterated descent algorithms based on the job-insert and job-swap neighborhoods.

Biography: Dr Xiang Song was appointed as a Lecturer at the Department of Mathematics, University of Portsmouth in 2011. Her research expertise is in the area of cutting and packing problems with a focus on column generation, dynamic programming and artificial intelligence. Her research includes both the development of general mathematical theory, and the development and comparison of computational experiments.

Dr Xiang Song's PhD was awarded in 2004 by two institutes: CIMS, Shenyang Institute of Automation, Chinese Academy of Sciences, and Dèpartement GSI, Université de Technologie de Troyes. She has worked in several EPSRC projects, and her results and active engagement have driven the projects and opened new research avenues. As a research assistant, she has worked in the project “An Investigation of Cutting/Packing and Planning using Automated Algorithm Selection” (Ref No: GR/S52414/01, 2004-2008). This project was funded by EPSRC and was evaluated as outstanding. As a senior research fellow, she has worked in another project “The LANCS (Lancaster, Nottingham, Cardiff and Southampton) Initiative in Foundational Operational Research: Building Theory for Practice”, (EP/F033214/1, 2008-2011), funded by EPSRC. This project has committed to a major expansion of research capacity in its theoretical foundations, supported by the additional resources available as a result of the current Science and Innovation call.


Dr Xiang Song, Department of Mathematics, University of Portsmouth


Lion Gate Building, LG 2.01

Date and Time

Thu, 12 Mar 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