2012-2013: Linking submodular optimisation to scheduling with controllable parameters.

Code: EP/J019755/1.

Funded by the EPSRC (Small Grant Scheme).

Principal investigator: Natalia Shakhlevich, University of Leeds.

Collaborator: Vitaly Strusevich.

Visiting researcher: Akiyoshi Shioura, Tohoku University, Sendai, Japan.

Total value: £30,000. Value to the University of Greenwich: £16,000.

The project is aimed at reformulation scheduling problems on a single machine and parallel machines in terms of linear programming problems with sub-modular constraints, in particular over a sub-modular polyhedron intersected with a box. For the latter problem, an efficient decomposition algorithm is developed leading to fast algorithms for related scheduling problem to minimise the total job compression cost. Sub-modular reformulations also help to design fast algorithms for bicriteria scheduling problems.

2011-2013: Quadratic and linear knapsack problems with scheduling applications.

Code: EP/018441/1.

Funded by the EPSRC.

Principal investigator: Vitaly Strusevich.

Collaborator: Hans Kellerer, University of Graz, Austria.

Value to the University of Greenwich: £23,000.

This project, completed in Janury 2013, focused on the development of fully polynomial-time approximation schemes for Boolean programming problems, such as the half-product problem and its modification and variants of quadratic knapsack problem, as well as on adaptation of these schemes to solving a range of scheduling problems with mini-sum objectives.