论文标题
使用少量机器的顺序调度的平行解决方案
Parallel solutions for ordinal scheduling with a small number of machines
论文作者
论文摘要
我们在两种平行溶液方面研究了少量机器的序数制造计划。在序数计划中，众所周知，作业是通过非侵入尺寸进行分类的，但是特定尺寸不知道。对于两个并行解决方案的问题，需要设计两种解决方案，并且使用两者的最佳解决方案对每个输入进行算法的性能。我们发现，在两台和三台机器上最小化MakePAN的结果很紧张，并且具有与最佳算法相比，具有四台和五台机器的单个解决方案的最佳竞争比的算法。为了证明上限，我们使用一种新的方法来考虑两种解决方案的机器。
We study ordinal makespan scheduling on small numbers of identical machines, with respect to two parallel solutions. In ordinal scheduling, it is known that jobs are sorted by non-increasing sizes, but the specific sizes are not known in advance. For problems with two parallel solutions, it is required to design two solutions, and the performance of algorithm is tested for each input using the best solution of the two. We find tight results for makespan minimization on two and three machines, and algorithms that have strictly better competitive ratios than the best possible algorithm with a single solution also for four and five machines. To prove upper bounds, we use a new approach of considering pairs of machines from the two solutions.
