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

作　　者：刘伟[1] 

机构地区：[1]日照职业技术学院,山东日照276826

出　　处：《高教学刊》2015年第9期49-50,共2页Journal of Higher Education

摘　　要：本文讨论的是排序问题中的分批排序问题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 Algorithm of Amalgamate Chain＂ to solve some batch scheduling problems. For this problemllchains,B=m｜Cmax, we consider a set of mchains, where n jobs in one chain, a constant number of jobs in the other m-1 chains, and present a polynomial algorithm（n1＋n2＋…＋nm）!n1!·n2!…nm!for this case llchains,B=m｜Cmax.

关 键 词：链优先约束 排序 目标函数 

分 类 号：G642[文化科学—高等教育学]