摘要
讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况.
We consider the problem of scheduling n simultaneously available jobs on m batcn processing machines. A batch processing machine is a machine that can process up to B jobs simultaneously as a batch. The processing time of a batch is equal to the largest processing time among all jobs in the batch. We focus on the extreme case of B 〉 n, ie, a batch can contain any number of jobs. The objective is to minimize the total completion time. We present an dynamic programming algorithm on identical parallel batch processing machines to solve this problem, the running time of our algorithm is O（mn ^n＋1 ）, and the conclusions will be further extended to situation of uniform parallel batch processing machines.
出处
《数学的实践与认识》
CSCD
北大核心
2009年第20期100-105,共6页
Mathematics in Practice and Theory
基金
辽宁省教育厅科学研究计划(05L417)
关键词
排序
批处理机
动态规划
scheduling
batch processing machines
dynamic programming
