Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches
Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches
复制标题
DOI：
10.1016/j.ejor.2017.08.034
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
A. Shioura;N. V. Shakhlevich;V. Strusevich
中科院分区：
文献类型：
--
作者：
A. Shioura;N. V. Shakhlevich;V. Strusevich
本文综述了加工时间可控的排序问题的最新研究成果。强调的是方法方面，包括参数流技术和方法解决数学规划问题的子模块化的约束。我们表明，使用这些方法产生快速算法解决问题的单机或并行机，一个或多个目标函数。对于广泛的问题，可控的处理时间，我们报告的算法与运行时间相匹配的相应问题与固定的处理时间。作为一个副产品，我们提出了最好的算法，一些问题的并行机，传统上研究的身体内的调度与不精确的计算。
This paper provides a review of recent results on scheduling with controllable processing times. The stress is on the methodological aspects that include parametric flow techniques and methods for solving mathematical programming problems with submodular constraints. We show that the use of these methodologies yields fast algorithms for solving problems on single machine or parallel machines, with either one or several objective functions. For a wide range of problems with controllable processing times we report algorithms with the running times which match those known for the corresponding problems with fixed processing times. As a by-product, we present the best possible algorithms for a number of problems on parallel machines that are traditionally studied within the body of research on scheduling with imprecise computation.