Polynomial algorithms for multiprocessor scheduling with a small number of job lengths
Polynomial algorithms for multiprocessor scheduling with a small number of job lengths
复制标题
具有少量作业长度的多处理器调度的多项式算法
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
F. Spieksma
中科院分区：
文献类型：
--
作者：
S. McCormick;Scott R. Smallwood;F. Spieksma
下面的问题最初是由一个问题引起的飞机维修周期的安排。每一个维修周期都是一项工作，维修设施是机器。在这种情况下，很少有不同类型的维护，所以很自然地考虑只有一个小的，固定数量C的不同类型的工作的问题。每种作业类型都有一个处理时间，每台机器的可用时间长度相同。一台机器一次最多只能处理一个作业，所有作业都在零时释放，没有到期日或优先级约束，并且不允许抢占。问题是是否有可能完成所有的工作。我们称这个问题为C作业长度的多处理机调度问题（MSPC）。排序问题，如MSPC，我们可以划分成一个相对较少的类型，使每种类型的所有作业是相同的，通常被称为高多重性问题。高重数问题很有趣，因为它们的输入非常紧凑：MSPC的输入仅由2C + 2个数字组成。对于C = 2的情况，我们提出了一个多项式时间算法。我们表明，该算法更多»产生一个时间表，使用最多三个不同的单机时间表，最小可能的数量。此外，我们将此算法的情况下，机器依赖的最后期限和多参数的情况下。最后，我们讨论了为什么我们的方法似乎没有扩展到C > 2的情况。«少
The following problem was originally motivated by a question arising in scheduling maintenance periods for aircraft. Each maintenance period is a job, and the maintenance facilities are machines. In this context, there are very few different types of maintenances performed, so it is natural to consider the problem with only a small, fixed number C of different types of jobs. Each job type has a processing time, and each machine is available for the same length of time. A machine can handle at most one job at a time, all jobs are released at time zero, there are no due dates or precedence constraints, and preemption is not allowed. The question is whether it is possible to finish all jobs. We call this problem the Multiprocessor Scheduling Problem with C job lengths (MSPC). Scheduling problems such as MSPC where we can partition the jobs into a relatively few types such that all jobs of each type are identical are often called high-multiplicity problems. High-multiplicity problems are interesting because their input is very compact: the input to MSPC consists of only 2C + 2 numbers. For the case C = 2 we present a polynomial-time algorithm. We show that this algorithmmore » produces a schedule that uses at most three different one-machine schedules, the minimum possible number. Further, we extend this algorithm to the case of machine-dependent deadlines and to a multi-parametric case. Finally, we discuss why our approach appears not to extend to the case C > 2.« less