摘要
研究了工件有优先约束和尺寸大小关系的分批排序问题,这里目标函数为工件的极大完工时间,这类问题是NP—完备的.对工件加工时间相同和有特殊到达时间的情况给出了它的近似算法,并证明其最差性能比不超过2.
The paper focuses on the problem of batching scheduling with job sizes and precedence constraints. A 2-approximation algorithm is presented for the case where all jobs have identical processing times p and release dates ri =e＋kip for 1≤j ≤ n.
出处
《滨州学院学报》
2006年第3期18-22,共5页
Journal of Binzhou University
基金
国家自然科学基金项目(10171054)
山东省自然科学基金项目(Y2005A04)
关键词
分批排序
近似算法
最差性能比
优先约束
batching scheduling
approximation algorithm
worst- case performance ratio
precedence constraints
