Quadratic and Linear Knapsack Problems with Scheduling Applications

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.

The focus of this project is on obtaining approximation algorithms and schemes for (non-linear) knapsack and scheduling problems, as well as on determining classes of non-linear knapsack problems that admit strongly polynomial algorithms for their continuous relaxation. At this point, the content of this project is rather theoretical, although the addressed problems do have a wide range of applications to production, supply chain management and finance. This project emerges as a continuation and extension of the studies done by the project team over the past five years, and there is strong evidence that the obtained results which link scheduling problems with quadratic knapsack models have already had a noticeable impact on Combinatorial Optimization and adjacent areas of research. 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 OR 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: Prof Strusevich at the Department of Computer Science of Royal Holloway, at the Faculty of Mathematics of the University of Southampton, and Prof Kellerer at Laboratoire d'Informatique, de Robotique et de Microlectronique de Montpellier (France), at the Robert H. Smith School of Business, University of Maryland (USA) and the Department of Logistics and Maritime Studies of the Hong Kong Polytechnic University. There are several follow-up papers written by other research teams that expand/improve on our results obtained so far. The area covered by this project is vibrant and developing fast, with almost no history prior to 2005. Several established research teams are competing in the area. Our team, as an initiator, still can be seen as holding the leading position, and this project, if funded, will allow us to maintain the leadership. Because of the existing competition, we want to make a fast progress, so that not the duration but rather the intensity of the project matters. We think that the duration of the project should be two years with six major project meetings, three at each location, Greenwich and Graz. One of the meetings in Graz is planned to be accompanied by a research seminar to be hosted by the University of Graz. The choice of the venue (Graz, and not Greenwich) is due to the fact that there is a high concentration in Graz of the specialists working in related areas. Besides, the central location of Austria in Europe would make it easier for the seminar to be attended by the colleagues from other countries, in particular, France, Germany and Italy. The project team will make efforts to secure funds from alternative sources in order to attend major conferences organised by the Operational Research Society, EURO, IFORS, INFORMS, and the Mathematical Programming Society to disseminate the preliminary and final results of the project. We are planning to organise a special session on the topic for one of the forthcoming EURO conferences with possible participation of the other teams involved in similar research from the University of Metz (France) and Saarbrucken (Germany). Additionally, we hope that our successful work on this project will lead to invited presentations, as it did in the past. One of the objectives of the project is to write a survey that gives a comprehensive exposition of our techniques. We have accepted an invitation from the editors of the journal 4OR to produce such a survey. We will develop a web-site devoted to this project, with the links to the studied problems, obtained results and relevant publications, including the follow-up papers.