On improving approximate solutions to parallel sequencing problem and one of its generalizations model analysis

Abstract

One of the current research directions in scheduling theory concerns those problems in which interruptions are allowed during the job execution. Scheduling theory problems are widely used in modeling work, particularly production, processes related to planning. To solve them, methods and algorithms have been developed that allow optimizing the relevant processes depending on specific needs, such as reducing the total time to complete jobs, min-imizing the resources involved, completing the entire amount of jobs within the specified time frame, or reducing the time delay. One of such problems implies a given finite set of jobs, the order of execution of which is subject to technological restrictions. This set of jobs must be performed using the available amount of resources in the shortest time period. In mathemati-cal formulation, such an applied problem can be reduced to the vertices' of a digraph parallel sequencing problem. The sequencing problems are mostly NP-hard, but their subclasses have been identified, for the solution of which exact algorithms of polynomial complexity have been developed. The use of such known algorithms of polynomial complexity when solving sequencing problems for arbitrary graphs with equal vertex weights generally leads to approximate solutions. Oc-casionally it is possible for the objective function value to increase almost twice, compared to the optimal one. The possibility of improving approximate solutions to these problems by al-lowing job interruptions is investigated. One generalization of the parallel sequencing problem corresponds to a model where the limit on the number of vertices that can be placed at fixed locations is given by the corre-sponding vector. A modification of the algorithm for solving this generalized problem is pro-posed for cases when the corresponding graph is regular and belongs to the subclass of com-plete bipartite graphs.