Leah Epstein, Asaf Levin

We consider basic problems of non-preemptive scheduling on uniformly related machines. For a given schedule, defined by a partition of the jobs into m subsets corresponding to the m machines, C_i denotes the completion time of machine i. Our goal is to find a schedule which minimizes or maximizes \sum_{i=1}^m C_i^p for a fixed value of p such that 01 the minimization problem is equivalent to the well-known problem of minimizing the \ell_p norm of the vector of the completion times of the machines, and for 0

Sign up or login to leave a comment