摘要
研究了工件有不同的到达时间和平行链约束(也就是每一个工件至多有一个前驱和一个后继)的情形.考虑有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.
出处
《滨州学院学报》
2007年第6期26-29,共4页
Journal of Binzhou University
基金
国家自然科学基金项目(10171054)
山东省自然科学基金项目(Y2005A04)
关键词
排序
分批排序
优先约束
scheduling
batching scheduling
precedence constraints
