The problem of one machine with equal processing time and preemption

We consider the problem of minimizing the weighted average execution time of equal-length jobs performance on one machine at the specified time of job arrival and the possibility of their interruption. The computational complexity of this problem is currently unknown. The article proposes an algorithm for preprocessing input data that allows reducing the problem to a narrower and more regular class of examples. The properties of optimal solutions are substantiated. Based on them, an algorithm for constructing a finite subset of solutions containing an optimal schedule has been developed. A parametric analysis of the schedules in this subset has been carried out that makes it possible to form a subclass of schedules that are optimal at some values of weights. A polynomially solvable case of the problem is isolated. Tab. 1, illustr. 10, bibliogr. 16.