工件可中断的周期维护混合平行机调度问题

Research on Hybrid Parallel Machines Scheduling Problem Based on Maintenance Significance

有m台平行机,其中m_1台机器需要周期维护,记m_1台机器每次维护时长为w,维护周期为T,余下的m-m_1台机器不需要周期维护,有n(n> m)个加工时长相同的工件被放在m台机器上加工,工件在加工过程中可中断,通过分类讨论的方法,目标函数是最小化时间表长,同时给出相应的最优多项式时间算法。

There are m parallel machines, which including m1 machines needs periodic maintenance, assume that the maintenance time for each machine is w and maintenance cycle for each machine is T, the rest of the m minus m1 machines with no need for periodic maintenance, there are n （ n greater than m） jobs that are not only nonpreemptive during processing but also with the same processing time be processed by m parallel machines, the objective function is to minimize the schedule length, at the same time the corresponding optimal polynomial time algorithm is given.