首页 | 本学科首页   官方微博 | 高级检索  
     检索      

极小化总完工时间的同时加工排序
引用本文:田乐,赵传立.极小化总完工时间的同时加工排序[J].数学的实践与认识,2009,39(20).
作者姓名:田乐  赵传立
作者单位:1. 烟台南山学院,理学院,山东,烟台,265713
2. 沈阳师范大学,数学与系统科学学院,辽宁,沈阳,110034
基金项目:辽宁省教育厅科学研究计划 
摘    要:讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况.

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

Minimizing the Total Completion Time on Processing Batch Machines
TIAN Le,ZHAO Chuan-li.Minimizing the Total Completion Time on Processing Batch Machines[J].Mathematics in Practice and Theory,2009,39(20).
Authors:TIAN Le  ZHAO Chuan-li
Abstract:We consider the problem of scheduling n simultaneously available jobs on m batch 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~(m+1)), and the conclusions will be further extended to situation of uniform parallel batch processing machines.
Keywords:scheduling  batch processing machines  dynamic programming
本文献已被 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号