一类复合并行机排序问题的多项式时间算法

在经典排序论中，一般都作以下两条假设：每台机器在任一时刻至多加工一个零件，每个零件在任一时刻至多被一台机器加工。本文研究在并行加工中多台机器可同时加工一个零件的排序问题，且每个零件可在固定的一个机器的子集上加工。在机器总数确定，零件加工可间断的条件下，设计出求这类问题最优解的计算方法，并研究这种问题的计算复杂性。

The Polynomial Time Algorithm for Solving Scheduling Multiprocessor Tasks Pm |mps, pmtn| C max

In the classical scheduling theory,it is generally assumed that a task can be processed by only one processor at a time and a processor is capable of processing at most one task at a tme.In the paper we discuss scheduling multiprocesser tasks,that is,more than one processor is allowed to execete one task at a time.Assume that each task is only processed by a fixed subset of processors and the number of processors which are used to execute all tasks is determined.Tasks are assumed to be preemptable.On conditions that above mentioned assumption are held an algorithm for solving the problem Pm |mps,pmtn| C max has been deduced,its computational complexity has been studied as well.