Impact of deadline intervals on behavior of solutions to the random Sequencing Jobs with Deadlines problem

The paper analyzes the influence, exerted by the mutual relations of deadline intervals on behavior of the optimal solution values for the random Sequencing Jobs with Deadlines (SJD) problems. An asymptotically sub-optimal algorithm is proposed. It is assumed that the problem coefficients are realizations of independent uniformly distributed random variables and deadlines are deterministic. The results, presented in the paper, significantly extend knowledge on behavior of the optimal solutions to the SJD problem in the asymptotical case.