带有链优先约束的分批排序  

Batch-scheduling Jobs with Chain Precedence Constraints

作　　者：马冉[1] 张玉忠[2] 邹娟[3] 

机构地区：[1]河南理工大学数学与信息科学学院,河南焦作454000 [2]曲阜师范大学运筹与管理学院,山东日照276826 [3]曲阜师范大学数学学院,山东日照276826

出　　处：《滨州学院学报》2007年第6期26-29,共4页Journal of Binzhou University

基　　金：国家自然科学基金项目(10171054);山东省自然科学基金项目(Y2005A04)

摘　　要：研究了工件有不同的到达时间和平行链约束(也就是每一个工件至多有一个前驱和一个后继)的情形.考虑有m条链,其中一条链上包含n个工件,其余的m-1条链上的工件数总和为常数,给出了一个多项式算法.同时指出,对于其他正则单目标函数也是多项式可解的.The batch-scheduling problem where jobs with different release dates are under parallel chain-type（i, e. every job has at most one direct predecessor and at most one direct successor） is discussed in this article. A polynomial algorithm of minimizing the makespan for the case where one of m chains contains n jobs and the others contain a constant number of jobs is presented. In addition,we have shed light on the fact that for the other regular objective functions there exist polynomial algorithms for the same case.

关 键 词：排序 分批排序 优先约束 

分 类 号：O223[理学—运筹学与控制论]