Academic Staff:
Research Students:
Overview:
The Network Analysis and Optimisation group focuses not only on complex modelling issues, such as the optimization of production planning in the face of uncertain data, but also on algorithms and solution approaches to solve large-sized instances where, for example, the phenomenon of combinatorial explosion makes optimal methods unviable. Members of the group have also developed software enabling the proof of conjectures and theoretical results in graph theory, particularly the GRAPHOGRAPH software, an ambitious project, involving several Universities, to develop multi-purpose scientific software for graph theory. The group is also interdisciplinary, working closely with computer science colleagues in the area of Evolutionary Computing.
Alistair Clark's Brazilian EPSRC project (reference: EP/D000483/1, with title:"Integrated Setup Sequencing & Lot-Sizing in Production Scheduling") was rated "Outstanding" in its overall assessment, with the top ranking in all 7 criteria.
Current doctoral studies within this group as follows:
Anush Poghosyan, since February 2007, under the supervision of Dr Vadim Zverovich.
The aim of Anush Poghosyan's PhD project is to develop the probabilistic method in order to prove upper bounds for various graph-theoretic parameters. Another aim is to disprove a number of known conjectures using a computer-aided approach.
Martin Serpell, since October 2007, under the supervision of Dr Alistair Clark.
The UK’s Office of National Statistics (ONS) often needs to protect the confidentiality of “sensitive” data in published tables, achieving this via a number of approaches collectively known as Statistical Disclosure Control (SDC). The sheer size of the tables means that existing methods are no longer possible to use. This project concerns the development of new mathematical models of how accurately a malicious “attacker” can estimate the value of data in sensitive cells in a table. Building on this the project will then develop techniques to create tables in which confidentiality is protected. The project will build on an existing collaboration between UWE and ONS which has generated experience in this area, and substantial research expertise in Mathematical Modelling (Dr Clark at UWE) and Evolutionary Computation (Dr Smith at UWE).
Andrea Staggemeier, since 2001, under the supervision of Dr Alistair Clark.The aim of the thesis was to better understand the use of hybrid approaches (i.e. combination of mathematical programming techniques and metaheuristic techniques) to solve complex problems such as the single-stage multi-machine simultaneous lot sizing and scheduling problem . The research demonstrates a successful implementation of hybrid evolutionary algorithm at little expense of either loss of generality, or inability to solve large instances.
Eli Toso, PhD student at the Federal University of Săo Carlos, Brazil and visiting student at UWE, Jan–May 2006, under the co-supervision of Dr Alistair Clark. Soon to defend.
The thesis proposes a mixed integer programming model for joint lot sizing and scheduling to a plant for animal feed compounds. A key characteristic of this industry is that certain products can perform a production line cleaning function if a sufficiently large lot is produced between two products that would otherwise require a cleaning
setup. Thus the sequence-dependent setup times do not always obey the triangular inequality. Tested on data from the plant, the model takes too long to solve exactly and so several alternative formulations and methods are developed to solve the model more quickly, based on variants of the Relax and Fix heuristic and the Asymmetric Travelling Salesman Problem (ATSP). The results confirm that the formulations are computationally effective and able to take economic advantage of the intermediate cleaning products. The models' schedules substantially improves on those practiced at the feed plant.
Selected Publications:
Araújo S. A. de, Arenales M. N. and Clark A. R., "Lot-Sizing and Furnace Scheduling in Small Foundries", Computers and Operations Research. vol. 35, issue 3, pp 916-932, March 2008.
Araújo S. A. de, Arenales M. N. and Clark A. R., "Joint Rolling-Horizon Scheduling of Materials Processing and Lot-Sizing with Sequence-Dependent Setups", Journal of Heuristics , vol. 13, no. 4, August 2007, pp 337-358.
V.E. Zverovich, The k-tuple domination number revisited. Applied Math. Letters. (2007) (to appear) [DOI Link].
A. Gagarin and V.E. Zverovich, A generalised upper bound for the k-tuple domination number. Discrete Math. (2007) (to appear) [DOI Link].
V.E. Zverovich, The computer system GRAPHOGRAPH. Electronic Notes in Discrete Math. 27 (2006), 109-110.
Clark A. R., " Rolling horizon heuristics for production and setup planning with backlogs and error-prone demand forecasts", Production Planning and Control., vol. 16, issue 1, January 2005, pp 81-97.
I.E. Zverovich and V.E. Zverovich, Basic perfect graphs and their extensions. Discrete Math. 293 (2005), 291-311.
I.E. Zverovich and V.E. Zverovich, The domination parameters of cubic graphs. Graphs and Combinatorics 21 (2)(2005), 277-288.
Clark A. R., "Hybrid Heuristics for Planning Lot Sizes and Setups", Computers and Industrial Engineering, vol. 45, issue 4, pp 545-562, December 2003.
Clark A. R., "Optimization Approximations for Capacity Constrained Material Requirements Planning Problems", International Journal of Production Economics, vol. 84, issue 2, pp 115-131, May 2003.
L. Volkmann and V.E. Zverovich, Proof of a conjecture on irredundance perfect graphs. J. Graph Theory 41 (2002), 292-306.
L. Volkmann and V.E. Zverovich, A disproof of Henning’s conjecture on irredundance perfect graphs. Discrete Math. 254 (2002), 539-554.
D. Rautenbach and V.E. Zverovich, Perfect graphs of strong domination and independent strong domination. Discrete Math. 226 (2001), 297-311.
Clark A. R. and Clark S. J., "Rolling-horizon Lot-sizing when Setup Times are Sequence-dependent", International Journal of Production Research, vol. 38, issue 10, pp 2287-2308, July 2000.
Any comments concerning this web site should be addressed to the AMG Webmaster.