| 带有扩充链优先约束工件的分批排序问题 |
| |
| 引用本文： | 张传林,刘勇,王成飞.带有扩充链优先约束工件的分批排序问题[J].科技导报(北京),2008,26(6):63-65. |
| |
| 作者姓名： | 张传林 刘勇 王成飞 |
| |
| 作者单位： | 日照广播电视大学教学科研处,山东日照,276826;曲阜师范大学运筹与管理学院,山东日照,276826 |
| |
| 基金项目： | 国家自然科学基金
,
山东省自然科学基金 |
| |
| 摘 要： | 提出一种工具之间带有扩充链的优先约束的分批排序问题,这种扩充链上既有优先序工件又有无约束工件(工件个数不定)。目标为极小化最大完工时间。优先约束为有m个优先约束集,其中一个"扩充链"上有n个工件,其余m-1条链上的工件数为常数,工件的加工不可中断。问题1chains,B=mCmax为多项式可解,同时给出了问题的一个多项式算法。
|
| 关 键 词： | 排序 批处理机 扩充链 多项式算法 |
| 文章编号： | 1000-7857(2008)06-0063-03 |
| 修稿时间： | 2007年10月10 |
Batching and Scheduling Jobs with Chain Precedence Constraints |
| |
| ZHANG Chuanlin,LIU Yong,WANG Chengfei.Batching and Scheduling Jobs with Chain Precedence Constraints[J].Science & Technology Review,2008,26(6):63-65. |
| |
| Authors: | ZHANG Chuanlin LIU Yong WANG Chengfei |
| |
| Abstract: | 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 1chains, B=mCmax 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. |
| |
| Keywords: | schedule batching machine generalized chain polynomial algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
