AN INEXACT ALGORITHM FOR THE SEQUENTIAL ORDERING PROBLEM

The Sequential Ordering Problem (SOP) consists of finding the permutation of the nodes from the set N, such that it minimizes a C-based function and does not violate the precedence relationships given by the set A. Strong sufficient conditions for the infeasibility of a SOP's instance are imbedded in a procedure for the SOP's preprocessing. Note that it is one of the key steps in any algorithm that attempts to solve SOP. By dropping the constraints related to the precedence relationships, SOP can be converted in the classical Asymmetric Traveling Salesman Problem (ATSP). The algorithm obtains satisfactory solutions by modifying the optimal solution to the related Assignment Problem (AP) if it is not a Feasible Sequential Ordering (FSO). The new solution 'patches' the subtours (if any) giving preference to the patches with zero reduced cost in the linking arcs.