We revisit the Online Polytope Scheduling Problem (PSP), where feasible schedules are subject to a set of constraints that constitute a polytope. For minimizing total (average) flow time of jobs, the algorithm Proportional Fairness (PF) has been shown to be -competitive with a small speed augmentation when the polytope is monotone, meaning that jobs' processing rates can only drop when more jobs are introduced. This result generalizes various scheduling problems and findings.

In this paper, we show that a weighted version of PF is -competitive for the \emph{-norm of flow time for monotone PSP} for any fixed . Such general algorithms have previously only been known for the -norm of flow time due to technical challenges despite the benefits of -norms in scheduling. This implies the \emph{first -competitive non-clairvoyant scheduling algorithms for uniformly related machines and restricted assignment cases}, which are special cases of unrelated machines, for the -norm. Non-clairvoyant algorithms do not assume knowledge of job sizes until their completion. We further develop another non-clairvoyant algorithm for the restricted assignment case that uses less speed augmentation, which has the potential to generalize to unrelated machines. Non-clairvoyant algorithms have been elusive for the -norm even for the restricted assignment case, just as they had been for the -norm for unrelated machines.