带有扩充链优先约束工件的分批排序问题  

Batching and Scheduling Jobs with Chain Precedence Constraints

作　　者：张传林 刘勇[2] 王成飞[2] 

机构地区：[1]日照广播电视大学教学科研处,山东日照276826 [2]曲阜师范大学运筹与管理学院,山东日照276826

出　　处：《科技导报》2008年第6期63-65,共3页Science & Technology Review

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

摘　　要：提出一种工具之间带有扩充链的优先约束的分批排序问题,这种扩充链上既有优先序工件又有无约束工件(工件个数不定)。目标为极小化最大完工时间。优先约束为有m个优先约束集,其中一个"扩充链"上有n个工件,其余m-1条链上的工件数为常数,工件的加工不可中断。问题1chains,B=mCmax为多项式可解,同时给出了问题的一个多项式算法。A kind of batch schedule with chain precedence constraints is put forward. The problem of batching and scheduling jobs with chain precedence constraints is considered, where the objective function is the makespan. The precedence constraints contain a generalized chain. There are n jobs in one chain of extension, and a constant number of jobs in the other m-1 chains. The processing time of jobs is unconstrained and the process can not be interrupted. By using the inductive method, a polynomial algorithm for 1 ｜ chains, B=m｜ Cmax is presented. But, when the number of batch processing jobs is not equal to m, the general problem of chain precedence constraints is still very complicated, and remains for further studies.

关 键 词：排序 批处理机 扩充链 多项式算法 

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