Chernykh K. Servakh V.
A study of combinatorial properties of optimal solutions of one single-machine scheduling problem
Reporter: Chernykh K.
This study aims at the problem of minimization of the equal-length jobs
performed on the same machine within the set jobs arrival time and with the
possibility of jobs interruption. This problem is one of a few that still have an un-
known computational complexity. The present article studies the combinatorial
structure of possible optimum solutions for this case.
The following approach is being proposed. The working weight is assigned
parametrically for the deadline jobs with the set jobs arrival time. The algorithm
developed in the working process turns into a basis for a finite subset of schedules
that definitely contains the optimum solution. The linear program calculates a
proper combination of weights that make each of the created schedules optimum.
Otherwise, the absence of this combination is proven. Therefore, it gets possible
to study the structure of optimum schedules as well as the reasons why some of
the schedules have a dearth of them.
This research studies some of the key examples, fathoms the main combi-
natorial features of optimum solutions, analyze the problem and distinguishes
polynomially solvable cases.
To reports list