工件带到达时间和服务器的平行机排序问题复杂性和启发式算法

Complexity and Heuristic Algorithm for Parallel Machine Scheduling Problem with Release Times and a Single Server

研究带到达时间和单服务器的平行机排序问题,工件在加工之前均有一定的安装时间,且所有安装时间均由单服务器来完成.证明在只有两台平行机的情况下,带到达时间和单服务器的平行机排序问题是强NP-困难的,对于有m台平行机的情况,给出一种改进的启发式算法,并证明该算法的紧界为2.

We discuss parallel machine scheduling problem with a single server. Before processing,each job must be loaded on a machine,which takes certain setup time.All these setups have to be done by a single server,which can handle at most one job at a time.For the two-machine case,we prove that problem is NP-hard in the strong sense even if all processing times are equal to 1.A simple heuristic algorithm is shown to create schedule with the makespan that is at most twice the optimum value for the m-machine.