Computational complexity and solution algorithms for a vector sequencing problem

• The considered vector sequencing problem is strongly NP-hard.
• A fast neighborhood search is constructed.
• Branch and bound and parallel metaheuristic algorithms are proposed.
• Numerical analysis of the algorithms is provided.

In many cases, if something is done once, it can be reused faster or by a lower cost. Such dependencies occur in data processing, software development, project planning, machine purchasing or construction plans and many others. In this paper, we express related problems as a vector sequencing problem and prove it to be strongly NP-hard. To solve it, we provide an exact branch and bound method. Furthermore, efficient heuristic and parallel metaheuristic algorithms are constructed that are based on a fast neighborhood search. Their efficiency is verified during an extensive computational experiments.