Submodular Optimisation Techniques for Scheduling with Controllable Parameters

Scheduling with Controllable Processing Parameters (SCPP) has been pursued for the past 30 years and has recently developed into an important field of study with various application areas including supply chain management, operations management, imprecise computation, power-aware computer processing, etc. In the SCPP models, some problem parameters such as job processing times are often not fixed but can be controlled. Typically, the decision-maker may choose the actual durations from a given range to allow some jobs to be completed earlier. Reducing the processing times may improve the overall performance (meeting the due dates, reducing the time in the system, etc.), but this usually incurs additional costs or quality losses. The trade-off between the improvement of a scheduling objective and the cost at which that can be achieved gives the decision-maker a range of time/cost options to select from.

Many SCPP problems are known to admit efficient solution procedures. However, until recently no general methodological framework to handle these problems has been offered. Moreover, the problems arising from different application domains but sharing the same underlying model were often treated independently without a careful study of their common properties.

In our recent collaborative study we have discovered that SCPP problems can be reduced to optimisation problems over special regions that fall into the category of Submodular Systems (polymatroids and their generalisations, base polyhedra, etc.). Already our first work has shown a definite advantage of using the Submodular Optimisation (SO) methods for solving SCPP problems. The resulting algorithms are faster, more elegant and easier to justify than those known earlier and are capable of solving a wider range of SCPP models, including those with no prior history of study.

A high level of abstraction does not easily allow practitioners and researchers in OR to employ the results of SO in their work. In particular, the advantages of the SO techniques, which are especially promising for solving SCPP problems, are not fully acknowledged by the scheduling research community and often overlooked. We anticipate that combined efforts of the scheduling and SO researchers will make interesting contributions to both fields, Scheduling and SO. The current project can help in achieving this goal by joining forces and taking advantage of the complementary skills of the UK team (Dr. Shakhlevich and Prof. Strusevich with their total publication record exceeding 100 journal papers, mainly on scheduling) and of the Japanese partner (Dr. Shioura who is famous for his fundamental research in Submodular Optimisation and Combinatorial Optimisation in general).

Within this project we intend to study several representative SCPP models producing their SO reformulations and advanced procedures for solving two versions of those models: the single criterion problem of finding a feasible schedule minimizing the total compression cost and bicriteria problems of simultaneous minimisation of the maximum completion time of all jobs and total compression cost. The obtained results will make interesting contributions to both fields, SO and Scheduling, and provide a new unified methodology for tackling complex problems with controllable parameters.

The proposed project brings together specialists in two branches of Operational Research (OR), namely Scheduling and Submodular Optimization, and through their collaboration will make important contributions to both these fields by designing advanced SO techniques for the SCPP models.

Scheduling theory will benefit from a unified and efficient framework for solving an important class of complex problems. Its range of solution techniques will be enhanced with advanced and intellectually challenging techniques of Submodular Optimisation. The SO methods that we intend to develop and apply to the SCPP problems will not only extend the toolkit of scheduling techniques, but lift the development of scheduling algorithms to a new, higher level.

Submodular Optimisation is an essential part of Combinatorial Optimisation and one of the most sophisticated areas related to Mathematical Programming, Computational Geometry and Computer Science in general. It has a major impact, and researchers active in this field are viewed as the top-ranked professionals. However, a high level of abstraction often prevents practitioners and researchers in general OR from an easy employment of the SO methods in their work. The advantages of the SO techniques are not fully acknowledged by the general OR community and often overlooked. We expect that this project will deliver convincing examples of effective applications of SO to Scheduling. This will encourage the SO research community to look for other possible links to applied branches of OR. On the other hand, aware of our successful experience, OR researchers motivated by practical applications may think of using methods of SO and Combinatorial Optimisation in general in their work.

The project team consists of two British investigators and a foreign collaborator. The idea of a systematic use of the SO methods for solving the SCPP problems comes from earlier papers by Dr. Shakhlevich and Prof. Strusevich, but the power of the project team has been considerably enhanced with the arrival of Dr. Shioura, who represents a new generation of the international leading specialists in SO. His proficiency in the theoretically challenging area of SO is combined with his interest and knowledge of the applied areas of combinatorial optimisation. His portfolio includes most prominent theoretical results in SO and practical results for applied problems, e.g., in the context of computer vision, combinatorial auctions, and resource allocation. This combination of two types of expertise makes Dr. Shioura the most valuable contributor to our interdisciplinary project.

Our earlier collaboration with Dr. Shioura has revealed that he has a rather unique vision of scheduling models which allows him to identify their submodular nature and to exploit their properties, often in a very unusual way. That `refracted' vision of scheduling models often leads to innovative algorithmic ideas which do not have counterparts in traditional scheduling research.
All three member of the team enjoy working together, we learn from each other and benefit from our complementary skills. We have no doubts that once elaborated in full, breakthrough ideas that we intend finalise in this project will have a major impact on the way scheduling researchers treat SCPP. On the other hand, new SO reformulations of the SCPP models emerging from our study will motivate further developments in the area of SO.

The project will contribute to building a stronger bond between the British Operational Research community and the Japanese top-ranked experts in Mathematical Programming. It will also help to stimulate co-operation between the British OR specialists with the Scheduling Society of Japan, an organisation that is unique to Japan.