Given a digraph G=(V,A), a weight for each node in V and a weight for each arc in A, the Sequential Ordering Problem (SOP) consists of finding a Hamiltonian path, such that a release data and a deadline for each node and precedence relationships among nodes are satisfied and a linear function is minimized. In the present case, the objective function is the maximum cumulated potential of the nodes (also, the so-called makespan). The SOP has a broad range of applications, mainly in production planning and manufacturing systems. Nodes represent jobs (to be processed on a single machine), arcs represent sequencing of the jobs, the nodes’ weights are the processing time for the jobs, the arcs’ weights are the setup times for two consecutive jobs, and the cumulated potential of a node is the completion time of a job. The goal is to produce a feasible scheduling of the jobs so that the makespan is minimized. The authors present an approximate algorithm for improving feasible solutions to the SOP. The algorithm is based on two local search κ-opt procedures to reduce the makespan while satisfying the time window (i.e. release date and deadline) and precedence constraints, for κ=3 and 4. The complexity of the algorithm is O(bn4), where n denotes the number of nodes and b is the average number of precedences per node. Extensive computational experience and implementation aspects are reported for very large-scale instances up to 3000 nodes and 9000 precedences. Experience with real-life cases is also reported.
