Submodular Optimisation Techniques for Scheduling with Controllable Parameters

具有可控加工参数的调度问题(SCPP)在过去的30年里一直是一个重要的研究领域，近年来已经发展成为一个重要的研究领域，其应用领域包括供应链管理、作业管理、不精确计算、节能计算机处理等。通常，决策者可能会从给定的范围中选择实际工期，以便提前完成某些工作。减少处理时间可能会提高整体性能(满足到期日期、减少系统中的时间等)，但这通常会导致额外的成本或质量损失。调度目标的改进和实现的成本之间的权衡为决策者提供了一系列时间/成本选择。众所周知，许多SCPP问题都可以采用有效的求解程序。然而，直到最近，还没有提供处理这些问题的一般方法框架。在我们最近的协作研究中，我们发现SCPP问题可以归结为子模块系统(多面体及其推广，基本多面体等)中特殊区域上的优化问题。我们的第一项工作已经表明，使用子模块优化(SO)方法来解决SCPP问题具有明显的优势。所得到的算法比以前已知的算法更快、更优雅、更容易证明，并且能够求解更广泛的SCPP模型，包括那些没有先前研究历史的模型。较高的抽象水平不容易使OR的从业者和研究人员在他们的工作中使用SO的结果。特别是，SO技术在解决SCPP问题方面的优势并没有得到调度研究界的充分认可，而且经常被忽视。我们期待着调度的共同努力，因此研究人员将在这两个领域做出有趣的贡献，调度等。目前的项目可以通过联合起来并利用英国团队(Shakhlevich博士和Strusevich教授，他们的总发表论文超过100篇，主要是关于日程安排)和日本合作伙伴(Shoura博士，他以子模块优化和组合优化的基础研究而闻名)的互补技能来帮助实现这一目标。在这个项目中，我们打算研究几个有代表性的SCPP模型，产生它们的重新公式和高级程序来求解这些模型的两个版本：找到最小化总压缩成本的可行时间表的单准则问题和同时最小化所有作业的最大完成时间和总压缩成本的双标准问题。所获得的结果将对SO和调度这两个领域做出有趣的贡献，并为解决参数可控的复杂问题提供一种新的统一方法。

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.