Preemptive scheduling of parallel jobs of two sizes with controllable processing times
Preemptive scheduling of parallel jobs of two sizes with controllable processing times
复制标题
抢占式调度两种规模的并行作业，处理时间可控
DOI：
10.1007/s10951-023-00782-w
复制
发表时间：
2023
影响因子：
2
通讯作者：
Shakhlevich Natalia V.
中科院分区：
文献类型：
--
作者：
Shioura Akiyoshi;Strusevich Vitaly A.;Shakhlevich Natalia V.
在并行机调度中，作业的大小被定义为同时需要处理该作业的机器的数量。本文考虑一类调度问题，其中工件集由两种尺寸的工件组成：常规工件（每个工件需要一台机器来处理）和并行工件（每个工件需要在多台机器上同时处理）。加工时间是可控的，它们必须从给定的时间间隔中选择，以保证存在一个抢占式的时间表，在这个时间表中，所有的作业都在一个共同的截止日期前完成。我们的目标是最大限度地减少总压缩成本，这反映了处理时间的可能减少。与传统作业的经典调度问题不同，所考虑的模型不能直接用子模块优化方法处理。我们减少了问题，以最大限度地提高总加权工作的所有工作参数化的总工作的并行作业。通过分别寻找并行作业的最大总加权工作和常规作业的最大总加权工作的断点来提供解决方案。这导致了一个多项式时间算法，它不会比执行作业参数排序所需的速度慢。
In parallel machine scheduling, a size of a job is defined as the number of machines that are simultaneously required for its processing. This paper considers a scheduling problem in which the set of jobs consists of jobs of two sizes: the conventional jobs (each job requires a single machine for its processing) and parallel jobs (each job to be simultaneously processed on more than one machine). The processing times are controllable, and they have to be chosen from given intervals in order to guarantee the existence of a preemptive schedule in which all jobs are completed by a common deadline. The objective is to minimize the total compression cost which reflects possible reductions in processing times. Unlike problems of classical scheduling with conventional jobs, the model under consideration cannot be directly handled by submodular optimization methods. We reduce the problem to maximizing the total weighted work of all jobs parametrized with respect to total work of the parallel jobs. The solution is delivered by separately finding the breakpoints for the maximum total weighted work of the parallel jobs and for the maximum total weighted work of the conventional jobs. This results in a polynomial-time algorithm that is no slower than needed to perform sorting of jobs’ parameters.
登录
查看更多内容
影响因子：
2
作者：
A. Kononov;Y. Kovalenko
通讯作者：
Y. Kovalenko
参数化调度的快速算法来自于参数化最大流的扩展
DOI：
--
发表时间：
1996
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
J. Yates;W. Orlikowski;Kazuo Okamura;S. McCormick
通讯作者：
S. McCormick
计算并行任务的最佳抢占式调度：线性编程方法
影响因子：
2.7
作者：
K. Jansen;Lorant Porkolab
通讯作者：
Lorant Porkolab
DOI：
10.1016/j.ejor.2017.08.034
发表时间：
2018-05
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
A. Shioura;N. V. Shakhlevich;V. Strusevich
通讯作者：
A. Shioura;N. V. Shakhlevich;V. Strusevich
DOI：
10.1287/ijoc.2017.0758
发表时间：
2017-09
期刊：
INFORMS J. Comput.
影响因子：
--
作者：
A. Shioura;N. V. Shakhlevich;V. Strusevich
通讯作者：
A. Shioura;N. V. Shakhlevich;V. Strusevich