Minimizing total completion time with machine-dependent priority lists
研究了并行机器调度中每台机器有独立作业优先级列表时，最小化总完工时间的问题，区分了同速机和异速机、机器依赖和相同优先级列表等情形，并确定了问题的计算复杂性边界。
We consider a natural, yet challenging variant of the parallel machine scheduling problem in which each machine imposes a preferential order over the jobs and schedules the jobs accordingly once assigned to it. We study the problem of minimizing the total completion time, distinguishing between identical and unrelated machines, machine-dependent and identical priority lists, or a constant number of different priority classes. Additionally, we consider the setting in which the priority list on a machine must satisfy longest processing time first. We resolve the computational complexity of the problem and provide a clear distinction between problems that are polynomial time solvable and APX-hard.