带链优先约束的单机分批排序问题

摘要

本文讨论的是排序问题中的分批排序问题1｜chains,B=m｜Cmax。假设链chains的条数为m，每批的容量为B，本文给出这个问题的算法、算法的多项式复杂性证明，并且在证明过程中推导出将m条链进行分批排序的运算次数公式：(n1+n2+…+nm)！n1！·n2！…nm！。%We consider the problem of scheduling jobs with chain precedence constraints and puts forward "a Al-gorithm of Amalgamate Chain" to solve some batch scheduling problems. For this problem1|chains,B=m|Cmax,we con-sider a set of mchains,where n jobs in one chain,a constant number of jobs in the other m-1 chains,and pre-sent a polynomial algorithm (n1+n2+…+nm)!n1!·n2!…nm! for this case 1|chains,B=m|Cmax.