###
DOI:
Journal of Software:2006.17(10):2063-2068

极小化加权完工时间和的无界批量机器并行调度问题
李曙光,李国君,王秀红
(山东大学,数学与系统科学学院,山东,济南,250100;烟台大学,数学与信息科学系,山东,烟台,264005;鲁东大学,数学与信息学院,山东,烟台,264025)
Minimizing Total Weighted Completion Time on Parallel Unbounded Batch Machines
LI Shu-Guang,LI Guo-Jun,WANG Xiu-Hong
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3141   Download 2812
Received:May 08, 2004    Revised:July 08, 2005
> 中文摘要: 考虑无界批量机器并行调度中极小化加权完工时间和问题.设有n个工件和m台批加工同型机.每个工件具有一个正权因子、一个释放时间和一个加工时间.每台机器可以同时加工Bn个工件.一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.给出了一个多项式时间近似方案(PTAS).
Abstract:This paper considers the problem of scheduling n jobs on m parallel unbounded batch machines to minimize the total weighted completion time. Each job is characterized by a positive weight, a release time and a processing time. Each unbounded batch machine can process up to B (Bn) jobs as a batch simultaneo usly. The processing time of a batch is the longest processing time among jobs in the batch. Jobs processed in the same batch have the same completion time, I.e., their common starting time plus the processing time of the batch. A polynomial time approximation scheme (PTAS) for this problem is presented.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.10271065,60373025(国家自然科学基金);the Science and Technology Development Foundation of Tianjin Municipal Education Commission of China under Grant No.20051519(天津市教委科技发展基金) Supported by the National Natural Science Foundation of China under Grant Nos.10271065,60373025(国家自然科学基金);the Science and Technology Development Foundation of Tianjin Municipal Education Commission of China under Grant No.20051519(天津市教委科技发展基金)
Foundation items:
Reference text:

李曙光,李国君,王秀红.极小化加权完工时间和的无界批量机器并行调度问题.软件学报,2006,17(10):2063-2068

LI Shu-Guang,LI Guo-Jun,WANG Xiu-Hong.Minimizing Total Weighted Completion Time on Parallel Unbounded Batch Machines.Journal of Software,2006,17(10):2063-2068