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.