摘要
本文首次就带有优先序的分批排序问题进行了讨论,目标函数为最大完工时间．当优先序为链,一条链上的工件个数为n,而其它链的工件个数为常数,分批的容量B大于等于链的条数,在这种情况下,问题为多项式可解的．文中并讨论了几种特殊情况的多项式算法．
In this paper, we first study the problem of scheduling jobs with chain precedence constraints on a batching machine to minimize makespan. We present a polynomial algorithm for such a problem, where n jobs in one chain, a constant number of jobs in the other chains. We also give some polynomial algorithms for several special cases.
出处
《应用数学与计算数学学报》
2006年第1期19-25,共7页
Communication on Applied Mathematics and Computation
关键词
排序
批处理机
优先约束
算法复杂性
scheduling, a batching machine, precedence constraints, the complexity of algorithm
