| 极小化最大完工时间及拒绝费用的单机可拒绝分批排序 |
| |
| 引用本文： | 王珍,曹志刚,张玉忠.极小化最大完工时间及拒绝费用的单机可拒绝分批排序[J].曲阜师范大学学报,2007,33(2):35-38. |
| |
| 作者姓名： | 王珍 曹志刚 张玉忠 |
| |
| 作者单位： | 曲阜师范大学运筹与管理学院 276826日照市(王珍，张玉忠)，山东外国语职业学院基础部 250100山东省济南市(曹志刚) |
| |
| 摘 要： | 首次考虑了工件可拒绝的单机分批排序问题,目标函数是极小化最大完工时间加上被拒绝工件的拒绝费用之和.对于工件同时到达的情况,本文通过动态规划算法给出了多项式时间的精确算法,借助于数据结构中的堆排序,我们将算法复杂性降低为O(n2logB).
|
| 关 键 词： | 排序 分批 可拒绝 最大完工时间 动态规划 |
| 文章编号： | 1001-5337（2007）02-0035-04 |
| 修稿时间： | 2006-06-26 |
Single Machine Batch Scheduling with Rejection to Minimize Makespan |
| |
| WANG Zhen,CAO Zhi-gang,ZHANG Yu-zhong.Single Machine Batch Scheduling with Rejection to Minimize Makespan[J].Journal of Qufu Normal University(Natural Science),2007,33(2):35-38. |
| |
| Authors: | WANG Zhen CAO Zhi-gang ZHANG Yu-zhong |
| |
| Institution: | 1.College of Operations Research and Management Science, Qufu Normal University, 276826, Rizhao ;2. Shandong Foreign Language Vocational College, 25010, Jinan, Shandong, PRC |
| |
| Abstract: | In this paper,a variant single machine scheduling problem with both batching and rejection is addressed.The objective to minimize the makespan of the accepted jobs plus the summation of the rejected ones.A dynamic programming algorithm with time complexity O(n2 log B) is presented,where B is the batch size. |
| |
| Keywords: | scheduling batch rejection makespan dynamic programming |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
