| EPSRC Reference: |
EP/I018441/1 |
| Title: |
Quadratic and Linear Knapsack Problems with Scheduling Applications |
| Principal Investigator: |
Strusevich, Professor V |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Sch of Computing and Maths Sci |
| Organisation: |
University of Greenwich |
| Scheme: |
Standard Research |
| Starts: |
10 January 2011 |
Ends: |
09 January 2013 |
Value (£): |
23,306
|
| EPSRC Research Topic Classifications: |
| Mathematical Aspects of OR |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
Scheduling Theory is a problem area within Operational Research which studies optimisation problems, normally arising in production and service planning. Typically, scheduling problems are formulated in terms of jobs processed on machines, and it is required to create a schedule that optimises a certain objective function. Most of the problems of practical relevance studied in Scheduling Theory are among the hardest optimisation problems, so that it is unlikely that an exact solution to any of those problems can be obtained in reasonable computation time. Therefore, one of the main focuses of scheduling research has been that of design and analysis of approximation algorithms. Some of these algorithms are purpose-built and explore specific features of the structure of the problem under consideration. On the other hand, for various scheduling problems approximation algorithms can be developed based on reformulations of the original problems in terms of Integer Mathematical Programming. In particular, if a problem is reformulated as a version of the knapsack problem, then either the design of approximation algorithms will benefit from a well-studied area of knapsack problem approximation or such a reformulation may initiate studies of new knapsack models which are likely to advance both areas of Combinatorial Optimisation, i.e., Scheduling and Mathematical Programming. The knapsack problem is the most known and most studied Integer Programming problem. Simple as it is in the classical setting of maximizing a linear function with a single linear constraint and binary decision variables, this problem is traditionally seen as the main testing ground of algorithmic ideas in discrete optimisation. Besides, the family of knapsack problems goes far beyond a single constraint model, and includes various versions and extensions such as bounded and unbounded knapsack problems, multidimensional, multi-choice and multiple knapsack problems, multicriteria knapsack problems, the problems with non-linear, e.g., quadratic, objective functions and many more. Within this project we intend to identify scheduling problems that allow a reformulation in terms of a knapsack problem, including its non-linear versions and extended linear versions. For the relevant knapsack models we will develop algorithms for solving their continuous relaxations, design fixed ratio approximation algorithms and approximation schemes. We expect that this project will result in numerous examples of effective applications of various knapsack models to scheduling approximation algorithms. We see as an especially promising the study on the link between the scheduling problems with multi-sum objective functions and quadratic knapsack problems of a special structure. The results to be obtained will establish a closer interaction between Integer Programming and Scheduling, and will make a considerable impact on both fields. The total record of the collaborators exceeds 150 papers published in peer-reviewed journals. The project team will take advantage of mutually complementary skills: the expertise of Prof Strusevich in design of approximation algorithms for various scheduling models and deep knowledge of Prof Kellerer in all aspects of research on the knapsack problems, as well as in related areas of Combinatorial Optimisation, including scheduling and bin packing.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.gre.ac.uk |