Job shop scheduling using simulated annealing metaheuristic

Question

I am implementing a job shop scheduler using Simulated Annealing - each instance is represented by a disjunctive graph (described here). Basically, the neighbourhood action for the metaheuristic is inverting a randomly chosen disjunctive arc that lies on the critical path. The problem is that with some instances the metaheuristic reaches a point where the critical path in the graph only consists of conjunctive arcs, which leads to a situation when no arc can be inverted. Is there a way to overcome this?

Answer 1

If you have only conjunctive arcs on the critical path, you are dealing with technological precedence constraints (i.e. operations in the same job). There's nothing you can do to shorten those. I think you may have found the best solution in this case.