Summary of the impact

Many operations in daily life, from manufacturing to running a hospital, need to optimise the return on use of resources where volume and value are conditions. Scheduling theory tackles some of the hardest practical optimisation problems, not known to be solvable in reasonable computation time. Strusevich and Kellerer have been able to reformulate practical scheduling challenges as `knapsack problems' - dealing with volume and value constraints - and then design approximation algorithms which can be applied back to the original challenge. The work has attracted EPSRC funding, stimulated a new field of research which is developing fast, been widely published, led to presentations at international conferences including the 2009 Computers and Industrial Engineering conference attended by industry practitioners and is impacting on Combinatorial Optimisation research.

Underpinning research

This work has emerged as a continuation and extension of the studies done by Prof Strusevich at the University of Greenwich, together with Prof Hans Kellerer (Graz, Austria), over the past seven years prior to July 2013. Prof Kellerer co-authored the most complete research monograph on the knapsack problems, published by Springer in 2004.

Scheduling Theory is a problem area within Operational Research which studies optimisation problems, normally arising in production and service planning. Because the optimisation problems studied are not known to be solvable in reasonable computation time, one of the main focuses of scheduling research has been that of design and analysis of approximation algorithms. For various scheduling problems, approximation algorithms can be developed based on reformulations of the original problems in terms of Integer Mathematical Programming. The purpose of this research project was to:

(1) identify scheduling problems that allow a reformulation in terms of a knapsack problem, including its non-linear versions and extended linear versions;

(2) design fixed ratio approximation algorithms and approximation schemes for the relevant knapsack models;

(3) adapt the algorithms and schemes developed for the knapsack problem for solving the corresponding scheduling problems.

Profs Strusevich and Kellerer have identified a specific form of a knapsack problem to minimize a quadratic non-separable objective function that they have named the Symmetric Quadratic Knapsack Problem (SKQP). They have shown that:

(1) the continuous relaxation of the problem can be solved in strongly polynomial time provided that the function is convex;

(2) the integer version of the problem admits a constant ratio approximation algorithm based on an appropriate rounding mechanism of the fractional solution;

(3) the integer version can be solved in pseudo-polynomial time by dynamic programming (DP);

(4) the DP algorithm can be converted into a fully polynomial-time approximation scheme (FPTAS) for the problem, which is the best approximation result that can be achieved.

No other form of the quadratic knapsack problem more general than SKQP is known to possess all these properties [3.5, 3.6].

Further, they have identified a number of scheduling problems with minisum objective functions which can be formulated in terms of the SQKP [3.1, 3.3, 3.5, 3.6, 3.7, 3.10]. Prior to their study, none of these problems has been known to admit an FPTAS; moreover, for some of them no constant ratio approximation algorithms have been previously reported. The researchers have shown how an FPTAS for the SQKP can be converted into a scheme that behaves as an FPTAS for the corresponding scheduling problem.

A survey on this topic was invited by the Editor-in Chief of the journal 4OR, A Quarterly Journal of Operations Research, Professor Silvano Martello (Bologna, Italy). The survey written by Profs Kellerer and Strusevich was published in 2012, its journal version is 51 pages long and it also covers approximation and scheduling applications of the Half-Product Problem, which is a relaxation of the SQKP without a linear constraint [3.8].

The research described in this case study also includes design of approximation algorithms and schemes for scheduling problems based on the Half-product reformulations (application to scheduling with machine deterioration and maintenance, joint work with a Greenwich PhD student K. Rustogi [3.9]; a number of applications of the convex Half-product with and without the knapsack constraint [3.12], as well as on the use of various versions of the knapsack problem with a linear objective, including the sum-set problem (application to scheduling with transportation, joint work with a Greenwich colleague Dr A. Soper [3.10]), multi-index knapsack and the bicriteria knapsack problem (application to scheduling with speeding-up resources [3.2]).

The study on this topic was funded by EPSRC grant "Quadratic and Linear Knapsack Problems with Scheduling Applications" with Prof Strusevich as principal investigator and Prof Kellerer as a collaborator. It ran from January 2011 for two years; the value to the University of Greenwich was £23,306. The results have been reported in an invited Optimisation stream key-note presentation at the 55^th Conference of the Operational Research Society (Exeter, September 2013) [3.12].

References to the research

(REF1 Submitted staff in bold,**REF Output)

The work is described in the following publications, predominantly high impact mathematics journals:

Details of the impact

Manufacturing, public services, humanitarian aid - many operations in daily life depend on solving logistical challenges and optimising use of resources. Some problems have been found over decades to be mathematically intractable, not solvable in reasonable computation time. One set of optimisation problems is defined by conditions of volume and value. Known as the `knapsack problem', at its most simple it describes the burglar's dilemma: which valuable things should be put in the loot bag? But it has application wherever maximum return on investment, or getting maximum use from limited resources, is an issue, including investment portfolios, transport, pharmacy, retail etc. This case study describes the breakthroughs that Strusevich and Kellerer have made at the intractable end of knapsack problems. With research of this type, the route to impact on the factory floor or field of operations is not always direct. In this case, the impact lies in making the new knowledge available through peer-reviewed publications and conferences - used by industry and consultancies as well as fellow academics - which stimulates further research and application. Here we outline the evidence that the research is useful.

The research focuses on obtaining approximation algorithms and schemes for knapsack and scheduling problems, as well as on determining classes of non-linear knapsack problems that admit strongly polynomial algorithms for their continuous relaxation. It is an example of successful collaboration between Scheduling and Mathematical Programming specialists, with beneficiaries from both these areas. Specialists in Scheduling Theory and its applications will benefit from a unified and efficient framework for handling several classes of hard-to-solve problems. On the other hand, the researchers that specialise in Integer Non-linear Programming will receive approx- imation techniques that the area definitely lacks at the moment. Similar benefits will be provided by the fast algorithms for solving continuous relaxations of non-linear problems. The techniques used for designing the FPTASs will interest researchers in Theoretical Computer Science.

The area covered by this case study is vibrant and developing fast, with almost no history prior to 2005. Several established research teams are competing in the area. The team consisting of Profs Strusevich and Kellerer is an initiator and still can be seen as holding the leading position.

They started reporting their findings related to this case study in 2005. As an invited speaker, Prof Strusevich made a presentation at the conference of the European Chapter of Combinatorial Optimization in 2005, the main annual forum of European researchers in Combinatorial Optimization. There is a strong interest in our work from applied researchers and practitioners; for example, Prof Kellerer gave an invited talk at the 39th International Conference on Computers and Industrial Engineering in 2009. Besides, the members of the team have delivered several invited talks at research meetings and seminars in the UK, France, USA and Hong Kong.

There is strong evidence that the obtained results which link scheduling problems with knapsack models have already had a noticeable impact on Combinatorial Optimization and adjacent areas of research. For example, as shown by the Strusevich-Kellerer research, in order to be able to convert an FPTAS for the quadratic knapsack problem into an FPTAS for the corresponding scheduling problem, the latter must admit a constant ratio approximation algorithm. This fact has stimulated the interest to the development of such approximation algorithms, and several papers by various research teams that include academics from France, Germany, Italy and the Netherlands appeared almost simultaneously in 2008-2010 [5.2, 5.4, 5.8, 5.9].

Since 2005 we have been reporting on various stages of the development of an FPTAS for a single machine scheduling problem to minimize the weighted sum of the completion times by adapting an FPTAS for the quadratic knapsack problem. Several research teams have contributed towards the design of faster, purpose-built schemes for the problem [5.3, 5.4, 5.6].

In 2006 Kellerer and Strusevich published a paper on a single machine problem to minimise the total weighted tardiness with respect to a common due date, where we reduced the problem to a version of a quadratic knapsack problem and designed an FPTAS for its solution. This publication was followed by Karakostas et al [5.6] who extended our approach to the problem with a fixed number of due dates, and by Kacem [5.3], who presented an FPTAS with an improved running time for the initial problem with a single due date.

Along with the Strusevich-Kellerer team, academic groups from the Netherlands and China independently use various mathematical programming reformulations (linear and quadratic) for scheduling models with speeding-up resources [5.1, 5.7], evidence of wider interest in this field.

In most of the scheduling applications, Strusevich and Kellerer use a version of the SQKP with a convex objective function to develop fast approximation schemes. Recently Z. Xu has proved that in many case the assumption of convexity can be relaxed, since the SKQP in the general form admits an approximation algorithm with a polynomial worst-case ratio.

Sources to corroborate the impact

This case study is strongly related to the LANCS initiative that contains a main research cluster on discrete optimisation and non-linear optimisation, with the stress on the connections between these two branches of mathematical programming: see http://www.lancs-initiative.ac.uk/ .

Papers by other research teams, which can be seen as initiated by this case study:

5.1 A. Grigoriev, M. Uetz. Scheduling jobs with time-resource tradeoff via nonlinear programming. Discrete Optimization, 2009, 6, 414-419.

5.2 I. Kacem. Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval. Computers & Industrial Engineering, 2008, 54, 401-410.

5.3 I. Kacem. Fully polynomial-time approximation scheme for the weighted total tardiness minimization with a common due date. Discrete Applied Mathematics, 2010, 158: 1035-1040.

5.4 I. Kacem, C. Chu. Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period. European Journal of Operational Research, 2008, 187, 1080-1089.

5.5 I. Kacem, A.R. Mahjoub. Fully polynomial time approximation scheme for the weighted flow- time minimization on a single machine with a fixed non-availability interval. Computers & Industrial Engineering, 2009, 56, 1708-1712.

5.6 G. Karakostas, S.G. Kolliopoulos, J. Wang. An FPTAS for the total weighted tardiness problem with a fixed number of distinct due dates. Lecture Notes in Computer Science, 2010, 5609: 238-248

5.7 W. Luo, L. Chen, G. Zhang. Approximation algorithms for scheduling with a variable machine maintenance. Lecture Notes in Computer Science, 2010, 6124, 209-219.

5.8 A. Marchetti-Spaccamela, N. Megow, M. Skutella, L. Stougie. Robust sequencing on a single machine. Matheon Preprint 533, 2008.

5.9 N. Megow, J. Verschae. Short note on scheduling on a single machine with one non-availability period. Matheon Preprint 557, 2009.

5.10 Z. Xu. A strongly polynomial FPTAS for the symmetric quadratic knapsack problem. European Journal Operational Research, 2012, 218: 377-381