On the necessary conditions for the existence of dense sequencing in the classical parallel sequencing problem

Abstract

The rapid development of the scheduling theory in the middle of the last century was linked to the variety of important practical applications of the problems it considers. Special attention was paid to problems in which the order of job execution is subject to certain technological constraints. One of the common mathematical models of these problems is the parallel sequencing problem. We consider the classical problem of minimizing the length of a sequencing for a given width, in which the target sequencing is dense. Since the polynomial tractability of these problems for fixed width > 2 is unknown, the main areas of research on this prob-lem include searching for classes of graphs for which exact polynomial algorithms exist, developing approximate algorithms and ways to prune state space search schemes. Substantial progress has been made in recent years in the development of approxi-mate algorithms with quasi-polynomial complexity and algorithms based on metaheuris-tics. In addition to the classical problem, scientists also consider its generalizations, which have more complex structures of jobs and workers, additional constraints on the job execution, other objective functions, etc. Due to the development of fog computing in recent years, many articles have been devoted to the study of such problems within this particular application area. The aim of this study was to investigate the constraints imposed on intermediate graphs by the condition of density of the target sequencing in the branch-and-bound method, to derive the necessary conditions for the existence of a dense sequencing and to propose methods to test them. The necessary conditions for the existence of a dense sequencing when using the branch-and-bound method, related to the limited capacity of places and the possibility of filling them, are investigated. The obtained conditions were reduced to a single one, and efficient algorithms to test it in general and for graphs with all vertices on critical paths were proposed. In addition, the study also resulted in new improved lower bound esti-mates of the sequencing length and generalization of special sequencings in which the vertices occupy the leftmost and rightmost possible places, that take into account the se-quencing width.