A New Approach to Solve Job Sequencing Problem Using Dynamic Programming with Reduced Time Complexity

The classical algorithm which is dedicated to resolve job sequencing problem with a deadline (JSD) needs exponential time O(\( n^{2} \)), where sorting algorithm [O(\( nlog\left( n \right) \))-(Merge Sort)] must have to use to sort all the jobs in decreasing order of their profit and it is a greedy technique. To reduce the complexity of this classical algorithm, we nullify the sorting algorithm using dynamic programming approach in the proposed algorithm. The time complexity after using this approach reduces to O(\( mn \)), where no sorting algorithm [O(\( nlog\left( n \right) \))-(Merge Sort)] needed, which has been shown by proper explanation. Here, we were also given a novel approach to resolve the job sequencing problem using Dynamic Programming and it is a unique approach that always finds an optimal solution. By using this approach, a proper algorithm has been developed in this paper. Besides, finding maximum profit and the sequence of the job to obtain maximum profit, this algorithm gives the sequence of jobs for a specific profit or near a specific profit.