DNAVS: an algorithm based on DNA-computing and vortex search algorithm for task scheduling problem

In this paper, we present DNAVS algorithm for the general job-shop scheduling problem (also known as Flexible JSSP). JSSP is an NP-complete problem, which means there is probably no deterministic or exact algorithm that can find the optimum solution in polynomial time for arbitrary instances of the problem, unless, P = NP. In the DNA computing algorithm, although the hardware is not accessible, in the future, we will have those computers that work based on biological hardware. Their most important advantages over silicon-based computers are their capacity for data storage. DNAVS is an improvement of the DNA computing algorithm by using a metaheuristic search algorithm called vortex search (VS) algorithm. The strongness of DNA computing is its parallelization. In the unavailability of DNA computers, the DNAVS reduces the time complexity of DNA computing by employing the VS algorithm. The efficiency of the DNAVS has been tested with standard test instances of job-shop scheduling problems. Our implementation results show that the DNAVS algorithm works effectively even for large scale instances on currently silicon-based computers.

Automated summary

This paper introduces the DNAVS algorithm for the general job-shop scheduling problem, utilizing parallelization in DNA computing. DNAVS reduces the time complexity of DNA computing by employing the VS algorithm and shows effectiveness on currently silicon-based computers.