权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Submodular Optimisation Techniques for Scheduling with Controllable Parameters

可控参数调度的子模优化技术

基本信息

批准号：
EP/J019755/1
负责人：
Natalia Shakhlevich
金额：
$ 3.06万
依托单位：
University of Leeds
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2013
资助国家：
英国
起止时间：
2013 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FJ019755%2F1
关键词：
Submodular Optimisation Techniques Scheduling Controllable

项目摘要

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.

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