多机排序问题pm｜fix_j，pmtn｜C_（max）的多项式时间算法

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

THE POLYNOMIAL TIME ALGORITHM FOR SOLVING SCHEDULING MULTIPROCESSOR TASKS Pm|fix_j,pmtn| C_(max)

In the classical scheduling theory,it is generally assumed that a task can he processed by only one processor at a time and a processor is capable of processing at most one task at a time.In the paper we discuss sceduling multiprocessar tasks,that is,more than one processor is allowed to execute 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 conditrons that above mentioned assumption are held a algorithm for solving the problem pm |fixj,pmtn|Cmax has been deduced,its computational complexity has been studied as well.