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.