We consider the non-preemptive scheduling problem on identical machines where there is a parameter B and each machine in every unit length time interval can process up to B different jobs. The goal function we consider is the makespan minimization and we develop an EPTAS for this problem. Prior to our work a PTAS was known only for the case of one machine and constant values of B, and even the case of non-constant values of B on one machine was not known to admit a PTAS.
翻译:我们考虑的是相同机器的不先发制人的时间安排问题,因为每个单位长度间隔的每台机器都有一个参数B,可以处理到B的不同工作。我们考虑的目标功能是最小化,我们为此开发了EPTAS。在我们工作之前,只有一台机器和B的常数值才知道PTAS,甚至一台机器上B的不连续值也不承认PTAS。