Improving job-shop schedules through critical pairwise exchanges

In this paper, we consider a job-shop scheduling problem. The criterion to be minimized is the makespan. To reach this goal, we propose a heuristic algorithm which gradually improves a given schedule by reversing the order in which some tasks are performed on machines. The job-shop scheduling problem being modelled as a disjunctive graph, reversing the order of two consecutive tasks which are performed on a given machine is equivalent to reversing the direction of a critical disjunctive arc. The important fact is that, due to the results proposed in this paper, we are able to choose the critical disjunctive arc to be reversed such that the makespan decreases at each iteration if the critical path is unique; otherwise, at least as many iterations as the number of critical paths are needed. This approach is simple and easy to implement.