| 极小化加权总完工时间的同时加工排序问题 |
| |
| 引用本文： | 田乐,赵传立.极小化加权总完工时间的同时加工排序问题[J].系统工程与电子技术,2007,29(11):1883-1885. |
| |
| 作者姓名： | 田乐 赵传立 |
| |
| 作者单位： | 沈阳师范大学数学与系统科学学院,辽宁,沈阳,110034 |
| |
| 基金项目： | 国家自然科学基金;辽宁省教育厅资助项目 |
| |
| 摘 要： | 讨论了平行机串联工件同时加工排序问题。目标函数是极小化加权总完工时间,并假设满足每批均含有k个工件,并且每批的加工时间为该批中所有工件的加工时间之和。对平行机的情况,该问题是强NP难的。本文主要针对该问题的两种特殊情况:(1)所有工件的权相等;(2)所有工件的加工时间相等,分别给出了最优算法,分析了算法的时间复杂性,同时用数值例子作了说明。
|
| 关 键 词： | 排序 分批 加权 算法 |
| 文章编号： | 1001-506X(2007)11-1883-03 |
| 修稿时间： | 2006年7月14日 |
Serial-batching scheduling problem to minimize total weighted completion time |
| |
| TIAN Le,ZHAO Chuan-li.Serial-batching scheduling problem to minimize total weighted completion time[J].System Engineering and Electronics,2007,29(11):1883-1885. |
| |
| Authors: | TIAN Le ZHAO Chuan-li |
| |
| Abstract: | The serial-batching scheduling problem on parallel machines is considered to minimize total weight completion time with the restriction that each batch contains exactly k jobs and the processing time is equal to the sum of the processing times of all the jobs in a batch.For parallel machines,the problem is strongly NP-hard.A algorithm is given for the following two special case of this problem:(1) All the jobs have the same weight;(2) All the jobs have the same processing time.The running time of the proposed algorithm is analyzed,at the same time,a numerical example is given. |
| |
| Keywords: | scheduling batching weighting algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
