Solving certain problems of scheduling theory by the methods of quadratic optimization

Abstract

The pipeline task of scheduling theory (flow shop) with the standard constraints, the variables of which are the times of the beginning of processing of each of the tasks on the corresponding device are investigated. Tasks of this type belong to the NP-complex class with the number of processing devices more than two. The number of calculations and the search time for the optimal schedule grow in proportion to n !, where n is the number of jobs.

By some transformations the constraints of the pipeline task are reduced to analytical functions of the unknown variables, and the objective function to the linear function of these variables. The number of functions, the constraints of the optimization problem, depends polynomially on the number of tasks of the original pipeline task. Then, using the method of exact quadratic regularization (EQR), let’s pass to the problem of convex optimization. Since the number of constraints depends polynomially on the number of jobs, the search time of the optimal schedule will grow polynomially for a fixed accuracy of the solution.

Thus, the NP-complex problem of scheduling theory is transformed to the problem of convex optimization with a linear objective function. It is shown that any pipeline problem of scheduling theory reduces to the problem of a minimum of a linear function with a set of linear and quadratic constraints, that is, to a problem of convex optimization. A model example is considered and an optimal schedule with a given accuracy is obtained by the method of exact quadratic regularization.