Parallel machine scheduling: A probabilistic analysis
研究了m台机器n个作业的并行机调度问题的最小完工时间，利用经验过程理论推导出调度常数θ，证明随机加工时间下最小完工时间几乎必然随n线性增长，并分析了其与θn的差异。
The minimum makespan of the general parallel machine scheduling problem with m machines and n jobs is studied. As for a number of other important combinatorial problems, the theory of empirical processes proves to be a very elegant and powerful tool for the probabilistic analysis of the solution value. It is used in this paper to derive a scheduling constant θ such that, for random processing times, the minimum makespan almost surely grows as θn when n goes to infinity. Moreover, a thorough probabilistic analysis is performed on the difference between the minimum makespan and θn. Explicit expressions for the scheduling constant are given for an arbitrary number of unrelated machines with identically distributed processing times (with an increasing failure rate), and for an arbitrary number of uniform machines and generally distributed processing times. © 1996 John Wiley & Sons, Inc.