The Problem of One Machine with Equal Processing Time and Preemption

We consider the problem of minimizing the weighted average execution time ofequal-length jobs performance on one machine at the specified time of job arrival and thepossibility of their interruption. The computational complexity of this problem is currentlyunknown. The article proposes an algorithm for preprocessing input data that allows reducing theproblem to a narrower and more regular class of examples. The properties of optimal solutions aresubstantiated. Based on them, an algorithm for constructing a finite subset of solutions containingan optimal schedule has been developed. A parametric analysis of the schedules in this subset hasbeen carried out that makes it possible to form a subclass of schedules that are optimal at somevalues of weights. A polynomially solvable case of the problem is isolated.