Stability polyhedra of optimal permutation of jobs servicing

Consideration was given to minimization of the sum of weighted instants of completing servicing of $n$ customers by a single server, provided that the duration of jobs servicing may assume any real value from a given numerical interval. An algorithm of complexity $O$($n$) was developed to construct a polyhedron (parallelepiped) of the optimality of permutation of servicing of $n$ jobs that is contained in the domain of stability of the same permutation and comprises the polyhedron of its stability. For the randomly generated problems, experimental comparison was carried out of the dimensions and relative volumes of the optimality polyhedra and stability of the optimal permutation of servicing $n$ jobs under randomly generated scenarios.

Presented by the member of Editorial Board: A. A. Lazarev