带有分批费用的容量有界的单机平行分批排序问题  

The Problem of Bounded Batch Capacity with Batching Costs About Parallel Batching

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

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

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

基　　金：国家自然科学基金(11171317);河南省科技攻关项目(09210221014);河南省自然科学基金(11401605)

摘　　要：考虑的问题是在添加工资费用或包装费用等附加的分批费用下,如何使单机平行分批中总完工时间和分批费用之和达到最小.首先我们假定工件和批处理机都在零时刻到达,工件被成批地进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用.然后对具有m个不同的加工时间,批容量有界且为固定值b的情形下目标函数为∑C_j与分批费用之和这一排序问题,利用动态规划的方法给出了多项式时间算法,时间界为O(b^2m^22~m).The article is about how to minimizing the sum of the total completion time and batching costs about the single machine parallel batching problem considering adding salary costs or packaging costs to the batching costs. First we assume that the jobs and the machine are available from time zero onwards. The jobs that are processed together form a batch and once processed the job can＇t be interrupted. The processing time of a batch is equal to the maximum processing time of any job assigned to it. Moreover, we assume that there is a batching cost for each batch. Then if it is supposed that there are m different processing times and the batch capacity is bounded as a fixed value of b.For the problem of minimizing the sum of ∑Cj and batching costs, the article gives a polynomial time algorithm using dynamic programming method , and the time limit is O（b2m22m）.

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

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