Conditions for length reduction of the parallel sequence of special digraphs’ vertices in the presence of interruptions

Abstract

In the scheduling theory, both theoretical and applied problems related to the planning of production processes, the design of computer systems, etc. are considered. In particular, there is a subclass of problems called parallel sequencing problems. Their mathematical for-mulation can often be reduced to optimization problems on directed graphs, where a given set of vertices corresponds to a set of jobs required for execution, and arcs specify a partial or-der corresponding to various technological constraints. The classical variant implies that in-put data are the finite set of jobs with equal execution times (defined as 1) represented as di-graph G and one of the sequence parameters (length or width). The undefined parameter needs to be minimized. On the contrary to the classical ones, in applied problems, the duration of the jobs often differs. That is why the question of whether to allow or forbid interruptions during job execu-tion is widely considered. The efficiency of using interruptions was proven for the cases when the corresponding digraph has a series-parallel, bipartite structure or belongs to the subclass of trees which allows graceful labeling. As graph structure plays a key role in the evaluation of profit from interruptions the graph labeling topics are of a big interest as well, such as those that use combinatorial configurations. This paper is devoted to the research of possible profit from interruptions in cases when G is a directed caterpillar. The effectiveness of the impact of interruption allowance on the objective function value was analyzed depending on the arcs' orientation, the weight coeffi-cient values of the vertices, and the structure of specific graphs. Theoretical results for evalu-ating the profit were obtained and formulated in the form of a theorem.