带尺寸批排序问题的一个最优算法  

Optimal Algorithm for Batch Scheduling with Nonidentical Job Sizes

作　　者：张咸昭[1] 蔡增霞[1] 

机构地区：[1]临沂师范学院数学系,临沂276005

出　　处：《科学技术与工程》2008年第14期3898-3899,3904,共3页Science Technology and Engineering

摘　　要：首次对问题1┃B,sj,pj=1┃∑Cj的一种特殊情况——工作可拆分的情形进行了研究指出此时该问题是多项式可解的,并且给出了该问题的多项式时间的算法。A special case for problem 1｜B,sj,pj=1｜∑Cj when the jobs may be splitted is studied for the first time. This special case is polynomial-time solvable is pointd out. Furthermore, the polynomial-time algorithm for the problem under consideration is presented.

关 键 词：排序 尺寸 拆分 多项式时间 

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