最小化总完工时间与分批费用之和的有界分批排序问题  

Minimizing the Sum of the Total Completion Time and Batching Costs on Batch Processing Machine

作　　者：张喆[1,2] 李文华[2] 

机构地区：[1]中原工学院理学院,河南郑州450007 [2]郑州大学数学系,河南郑州450001

出　　处：《数学的实践与认识》2011年第21期93-97,共5页Mathematics in Practice and Theory

基　　金：国家自然科学基金(11171313);河南省科技攻关计划(09210221014);河南省基础与前沿技术研究计划(082300410070)

摘　　要：考虑了当每分一批均产生固定费用、批容量有界且为固定值b、加工不允许中断抢先.所有工件在零时刻到达时的单机平行分批排序问题.目标是最小化总完工时间与分批费用之和.利用动态规划方法给出了多项式时间算法,时间界为O(n^(b(b-1))).In this paper, the single machine, bounded batch capacity b which is fixed, no preemption, jobs＇ arrival at time O, parallel-batch scheduling problem with batching costs is discussed. The objective is to minimize the sum of the total completion time and batching costs. It is showed that the problem can be solved by dynamic programming method inO（n^b（b-1）） time.

关 键 词：单机 平行分批 总完工时间 分批费用 动态规划 

分 类 号：O223[理学—运筹学与控制论]