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.

Automated summary

This paper addresses the problem of scheduling jobs on identical machines to minimize the maximum completion time. The authors introduce a dynamic programming approach to solve the case with two machines and prove that it has a fully polynomial time approximation scheme. For the case of m machines, heuristics and an adapted genetic algorithm are proposed and evaluated through numerical experiments.