A Permutation-Based Neighborhood for the Blocking Job-Shop Problem with Total Tardiness Minimization

What is it about?

A permutation-based neighborhood for the blocking job-shop problem with swaps regarding a total tardiness objective is presented. A procedure to regain the feasibility of a neighbor is shown and with this partially defined solutions are completed to feasible schedules. The neighborhood is embedded in a simulated annealing. Computational experiments are done on randomly generated instances based on a single-track train scheduling problem as well as on benchmark instances. The results are compared to those obtain by solving the corresponding MIP formu- lations given in an earlier paper by the authors.

Featured Image