Scheduling on identical machines with preemption and setup times
研究了同型机上带准备时间的最小化最大完工时间调度问题，对两台机器给出动态规划并证明存在完全多项式时间近似方案，对多台机器提出启发式和遗传算法。
In this paper, we address the problem of scheduling jobs on identical machines for minimising the maximum completion time (makespan). Each job requires a sequence-independent setup time, which represents the time needed to prepare the machines for job execution. Then, we introduce a dynamic programme to solve the case with two machines, and show that this problem admits a fully polynomial time approximation scheme. For the case of m machines, we propose heuristics and an adapted genetic algorithm. Some numerical experiments are done to evaluate the proposed algorithms.