Reducing efficiently the search tree for multiprocessor job-shop scheduling problems

What is it about?

The multiprocessor job-shop scheduling problem with unrelated parallel machines as a generalization of the classical job-shop problem with minimizing the makespan is considered. The practical behavior of a method for the preliminary reduction of the solution space suggested by Vakhania and Shepin is exploited.

Featured Image

Why is it important?

The theoretical estimation that this results in an exponential reduction of the whole set of feasible solutions with a probability close to 1 was certified by intensive computational experiments. The tested reduction algorithm allowed to solve many of the instances considered to optimality.