【摘要】 研究带单服务器的两台平行机的排序问题的复杂性,每个工件在机器加工之前,必须由服务器先进行安装,在同一时刻每一个服务器只能安装一个工件,目标是使最大完工时间达到最小.在工件具有准备时间且所有加工时间等于1的条件下,证明该问题是强NP-困难的.更多还原

【Abstract】 The complexity of parallel machine scheduling problem with a single server is studied.Setup times are considered first if a job must be loaded on a machine.We assume that all setup times have to be done by a single server,which can handle at most one job at a time.The objective is to determine a feasible schedule,which minimizes the makespan.It was proposed that all release times existed and all processing times were constant,the problem was still NP-hard in the strong sense.更多还原