文献类型：期刊文章

作　　者：田乐[1] 赵传立[2]

机构地区：[1]烟台南山学院理学院,山东烟台265713 [2]沈阳师范大学数学与系统科学学院,辽宁沈阳110034

出　　处：《数学的实践与认识》

基　　金：辽宁省教育厅科学研究计划(05L417)

年　　份：2009

卷　　号：39

期　　号：20

起止页码：100-105

语　　种：中文

收录情况：BDHX、BDHX2008、CSCD、CSCD_E2011_2012、MR、RCCSE、ZGKJHX、ZMATH、核心刊

摘　　要：讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况.

关 键 词：排序 批处理机 动态规划

分 类 号：O223] TS194.4[数学类]