Combinatorial Structure of Optimal Solutions to the Problem of a Single Machine with Preemption

The problem of minimizing the weighted average time to complete jobs on a single machine is considered. The release dates of jobs are fixed. The preemptions are possible. The processing times of all jobs are equal. The computational complexity this problem is unknown. An approach to the analysis of the structure of the optimal solutions is proposed. Polynomial algorithms are described for some important classes.