| P与d一致时的分族分批排序误工个数问题 |
| |
| 引用本文： | 曹国梅.P与d一致时的分族分批排序误工个数问题[J].河南科学,2009,27(7):775-778. |
| |
| 作者姓名： | 曹国梅 |
| |
| 作者单位： | 郑州旅游职业学院,郑州,450009 |
| |
| 摘 要： | 研究了一类分族分批排序最小误工个数问题，给出并证明了最优排序的性质，证明了此问题是NP-困难的．对工件的到达时间和工期一致时的情形，给出了一个时间复杂性为O（mb（n/m）^2m）的动态规划算法．
|
| 关 键 词： | 平行批排序 分族分批 P与d相一致 误工个数 动态规划 |
Minimizing the Number of Tardy Jobs when p and d Is Agreeable on a Single Machine Parallel Batch Scheduling with Family Jobs |
| |
| Cao Guomei.Minimizing the Number of Tardy Jobs when p and d Is Agreeable on a Single Machine Parallel Batch Scheduling with Family Jobs[J].Henan Science,2009,27(7):775-778. |
| |
| Authors: | Cao Guomei |
| |
| Affiliation: | Zhengzhou Tourism College;Zhengzhou 450009;China |
| |
| Abstract: | This paper considers the problem of minimizing number of tardy jobs on a single machine parallel batch machine with family jobs. It gives the nature of the optimal scheduling and proves it. It also shows that this problem is NP_hard and presents a dynamic programming algorithm with the complexity of O(mb(n m)2m)when the processing time and due date of one job is agreeable. |
| |
| Keywords: | parallel batch scheduling parallel batch with family-jobs p and d is agreeable number of tardy jobs dynamic programming |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
