An Investigation of Cutting/Packing and Planning using Automated Algorithm Selection
School of Computer Science and IT, University of Nottingham : Graham Kendall and Edmund Burke
Management Science Research Group, University of Southampton : Julia Bennell
Previous Research and Track Record
This proposal is requesting funds to conduct ambitious research into an algorithm that has eluded researchers for many years. If, a robust implementation can be realised it has the potential to make significant advances in many areas. In particular, the domain of cutting and packing will benefit and this proposal has the potential to revolutionise that domain. This domain should not be under-estimated as it covers many industries. To name just a few, it includes glass manufacturers, shoe manufacturers, the textile industry, the building industry (e.g. companies which have to supply polycarbonate for conservatories), cardboard suppliers (such as those supplying the packaging industry) and companies using automated metal cutting machines. Beyond the domain of cutting and packing there are other domains that will benefit from this research. Robot navigation is an obvious one and we will explore this domain within this proposal. In addition, areas such as vision analysis and image processing will also benefit. The work will be carried out within the Inter-disciplinary Optimisation Laboratory (IOL) at the University of Nottingham and at The University of Southampton.
The Inter-Disciplinary Optimisation Laboratory (IOL) : The Inter-disciplinary Optimisation Laboratory (IOL) at the University of Nottingham underpins much of the inter-disciplinary research being carried out within the university. The lab is based on the brand new £50M Jubilee Campus and provides a supportive framework and environment in which to build on existing collaborations and to develop exciting research directions at the interface of several disciplines. It supports close collaboration between the School of Computer Science and IT, The School of Chemistry, The School of Nursing, The School of Mechanical, Materials, Manufacturing Engineering and Management and the School of Psychology. The laboratory is currently funded by four external grants (from EPSRC, BBSRC, ESRC and the DTI) to a total value of just over £600K. These grants involve collaboration across the 5 schools. In addition, EPSRC has recently funded an Inter-disciplinary Scheduling network (involving over twenty UK universities) to the value of £60K. This network is situated within the laboratory. This proposal will be situated in the lab.
The School of Computer Science and Information Technology : The Automated Scheduling, Optimisation and Planning (ASAP) Research Group (http://www.asap.cs.nott.ac.uk) at the University of Nottingham is located within the School of Computer Science and Information Technology. The school received a grade 5 in the recent RAE. ASAP has been carrying out highly successful research into the development and application of meta-heuristic techniques and hybridisations to scheduling and optimisation problems for the last 9 years. It has been at the forefront of research in the area during this period and is internationally recognised for its work. The group currently comprises 5 members of academic staff, 8 research assistants, 25 PhD students and two secretaries. The investigators have many years of experience in research and in the commercial sector.
The Centre for Operational Research : The Centre for Operational Research, Management Science and Information Systems (CORMSIS) at the University of Southampton provides a forum for collaborative research involving the School of Management and the School of Mathematics. The centre combines the expertise of the two schools in joint major research areas; these include combinatorial optimisation, health simulation and risk. As a result links between the two schools have been significantly strengthened, leading to one of the largest OR research groups in the UK. It has a rapidly growing postgraduate intake. The group holds two EPSRC grants, employs 4 research assistants and has 19 PhD students.
The Research Team
Dr Graham Kendall was recently promoted to senior lecturer in the School of Computer Science and Information Technology at the University of Nottingham. Prior to starting his academic career he worked in the IT computer industry for 15 years where he held a number of positions and was responsible for upwards of 50 people. He is a member of the Automated Scheduling, Optimisation and Planning (ASAP) research group, a member of the EPSRC Peer Review College and deputy director of the interdisciplinary optimization lab. His PhD research [[1]] was directly related to the areas which this proposal addresses. He has published the results from his thesis in international conferences and journals [[2],[3],[4],[5],[6],[7]]. Since completing his PhD, Dr Kendall has continued to carry out research in cutting and packing with the award of two grants. A TCS (Teaching Company Scheme) award (“New Approaches to Produce Efficient Nesting Patterns”: TCS3047) is working with an engineering company to produce the next generation of automated cutting and packing software. Dr Kendall also holds an EPSRC CNA (Case for New Academics) award (“Applying meta-heuristics and hyper-heuristics to stock cutting”: CNA 00802329) which is being supported by the same engineering company. His recently awarded EPSRC fast stream grant (“Investigate Novel Methods for Optimising Shelf Space Allocation”: GR/R60577/01) is also carrying out research in a related area. In addition, Dr Kendall has also broadened his research interests and has published key papers on adaptive and evolutionary learning with a particular emphasis on game playing and uncertain environments [[8],[9],[10],[11]]. In total, he has published over 25 refereed papers in international journal and conferences. He is also a co-investigator on five other external awards (from EPSRC and BBSRC) totaling £613,000. In total, Dr Kendall has attracted external funding totaling over £840,000.
Dr Kendall is Chairing the Organising Committee and Co-Chairing the Programme Committee (with Prof Burke and Dr Petrovic) of the forthcoming MISTA conference in August 2003 and is editor of the selected papers volume of that conference (The 1st Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2003) (to be published by Kluwer)). He is chairman of the international steering committee for the conference. He is co-editing the Kluwer book for the INTROS’03 (INtroductory TutoRials in Optimization and Search Methodologies) workshop (with Prof Burke). He will be a co-editor of the Proceedings of the 2003 Genetic and Evolutionary Computation Conference (GECCO 2003) (published by Springer Verlag). Dr Kendall is an Associate Editor of The 2002 & 2003 International Conference on Machine Learning and Applications (ICMLA’02/ICLMA’03) and organised a special session entitled “Machine Learning for ‘Games’ of Perfect and Imperfect Information” at ICMLA’02. Dr Kendall is a member of the editorial panel of a feature issue of the European Journal of Operational Research (EJOR) on “Timetabling and Rostering”. Dr Kendall co-organised two workshops at the Genetic and Evolutionary Computation Conference (GECCO 2002), New York, July 2002 entitled “Scheduling : Bringing Together Theory and Practice” and “Scheduling and Logistics”. At the 2001 conference Genetic and Evolutionary Computation Conference (GECCO 2001), San Francisco, July, 2001) he co-organised a workshop at this conference entitled “The Next Ten Years of Scheduling Research”. Dr Kendall has served on 8 program/technical committees since 2001.
1. Program Committee: Computers and Games 2002 (CG'02), Edmonton, Canada, July 24-27, Edmonton, Canada
2. Program Committee: 8th International Conference on the Simulation and Synthesis of Living Systems (Artificial Life VIII), University of New South Wales, Sydney, New South Wales, Australia, 9-13 December 2002.
3. Program Committee: 4th International Conference on Recent Advances in Soft Computing (RASC2002), 12 – 13 December 2002, Nottingham Trent University, Nottingham, UK
4. Technical Committee: Congress of Evolutionary Computation (CEC-2002), Honolulu, Hawaii, USA May 2002;
5. Program Committee: 3rd International Workshop on Memetic Algorithms (WOMA III) (held in conjunction with the 7th International Conference on Parallel Problem Solving from Nature (PPSN VII), Granada, Spain, September 2002;
6. Program Committee: 4th Metaheuristics International Conference (MIC 2001), July 2001, Porto, Portugal
7. Program Committee: International Conference on Artificial Intelligence (IC-AI’2001), Las Vegas, Nevada, USA, June 2001
8. Technical Committee: Congress of Evolutionary Computation (CEC-2001), May 2001, Korea.
Dr Julia Bennell holds a lectureship in the School of Management at the University of Southampton. She is a member of the Centre for Operational Research, Management Science and Information Systems. She has been a member of the Operational Research Society since 1995 and secretary of the Southern Operational Research Group since 1999. Her research expertise is directly related to the application of the research proposal and she has published [34] one of the few documented procedures that begins to address the issues detailed in this proposal. Her Ph.D. research focus was in the area of irregular stock cutting or nesting problems and she has continued to develop a substantial and internationally respected body of research in the area. She has a strong grounding in mathematics, studying pure mathematics and OR at undergraduate level, and has undertaken research as part of her Ph.D. in some of the key mathematical concepts that underpin this proposal. Her work has been published in highly respected international journals and presented at international conferences [30,29,28]
Dr Bennell’s research interest into stock cutting and scheduling [[12]] problems has developed in parallel with her interest in the use of meta-heuristic techniques and artificial intelligence. As a result she has developed research projects in a broader range of applications, with particular emphasis in financial markets [[13],[14],[15]] She was a co-investigator on a highly successful project funded by FITCH IBCA; the third largest international credit rating agency. Her role was to supervise the research and the development of Artificial Neural Networks to classify sovereign credit ratings.
Professor Edmund Burke leads the ASAP Research Group and is Director of the Inter-disciplinary Optimisation Lab at the University of Nottingham. He is a member of the EPSRC Peer Review College and is chairman of the Steering Committee of the EPSRC Inter-disciplinary Scheduling Network. Professor Burke is Editor-in-chief of the Journal of Scheduling, Area Editor for Combinatorial Optimisation of the Journal of Heuristics and is an Associate Editor of the IEEE Transactions on Evolutionary Computation. He is also a co-editor of a forthcoming feature issue of the European Journal of Operational Research on “Timetabling and Rostering”. He is chairman of the steering committee of the international series of conferences on the Practice and Theory of Automated Timetabling (PATAT). He has been co-chairman of the programme committee and co-editor of the conference proceedings and Selected Papers volumes (published by Springer) since 1995. This has covered 4 PATAT conferences (Edinburgh 1995, Toronto 1997, Konstanz 2000 and Gent 2002). He will be Co-Chair of the Programme Committee of the forthcoming international conference on “Multi-disciplinary Scheduling: Theory and Applications” (MISTA) (proceedings published by Kluwer) to be held at Nottingham in August 2003. Professor Burke is a co-ordinator and chairman of the organising committee of the EURO Working Group on Automated Timetabling which is funded by EURO (the EUropean association of Operational Research societies). He has been a member of the Programme (or refereeing) committees of over 25 international conferences since 1994. During his career he has published over 75 refereed papers and has been awarded 17 externally funded grants worth £2.1M from 3 research councils (EPSRC, ESRC, BBSRC) and other sources.
Commercial Collaborators
Gower Optimal Algorithms Ltd (GOAL) is a long established UK based specialist software development company. They focus on providing software solutions in the fields of Logistics and Scheduling. GOAL currently have around 50 customers world-wide including Estee Lauder, Guiness UDV, Johnson & Johnson, Panasonic, TDG Logistics, Whitman Laboratories and Woolworths. To date all of GOAL’s cutting and packing software deals with rectangular or circular objects but they are interested in expanding to irregular objects. Of particular interest is the problem of packing identical 2-D footprints into a fixed rectangular area [[16],[17],[18]]. Dr Kathryn Dowsland is a director of GOAL. She was awarded an Industrial Fellowship from the University of Nottingham in 2001 (associated with the ASAP research group). She was, until 2001, a Reader in Operational Research at the University of Wales Swansea. She has an outstanding international academic publication record (over 30 refereed papers in major journals). Dr Kath Dowsland has been involved in cutting and packing since 1982 (MSC (by research) in 1982 and PhD in 1985). She has continued to be active in the area since this time [[19],[20],[21],[22],[23],[24],[25],[26],[27],[28],[29],[30],[31]] and has written two invited reviews on the subject [[32],[33]] and organised several cutting and packing streams at international OR conferences (e.g. IFORS, 1996) and given several tutorial papers on cutting and packing at national and international conferences.
Summary
The recent Dearing report said (Item 68 in the List of Recommendations) “We recommend to the Research Councils that they review their mainstream teaching and research funding arrangements to ensure that they do not discourage collaboration between institutions; and that, where appropriate, they encourage collaboration.” This proposal gives EPSRC the opportunity to fund high risk, high return, adventurous research which will be carried out by two institutions which, the recent RAE, recognised carries out internationally leading research.
The research team we have assembled for this project provides an excellent mix of researchers. Dr. Bennell and Dr. Kendall carried out their Ph.D. research in precisely the area that this proposal addresses and both have recently presented revised NFP algorithms [1,[34]]. Prof. Edmund Burke supervised Dr Kendall’s Ph.D. and Dr Dowsland supervised Dr Bennell’s Ph.D. In addition, Dr Dowsland was the external examiner for Dr Kendall’s Ph.D. Dr Dowsland currently holds an industrial fellow position at The University of Nottingham, which she combines with running Gower Optimal Algorithms Ltd. Therefore, the three investigators and Dr Dowsland have not only carried out leading international research in this area in the recent years but already have a proven track record of working successfully together.
Through this proposal, we are bringing together investigators who are active in the field, have recently published in this precise area and have a “score to settle” with the algorithm that this proposal addresses. Two recent Ph.D. projects (Bennell and Kendall) have been devoted to this area and, whilst advances have been made, neither thesis has completely solved the problem. Through this proposal, the EPSRC has the opportunity to allow the definitive NFP algorithm to be produced, to give researchers a toolbox of algorithms related to this area and to make significant advances in areas which will benefit from a robust NFP algorithm.