摘要
考虑无界批量机器并行调度中极小化加权完工时间和问题.设有n个工件和m台批加工同型机.每个工件具有一个正权因子、一个释放时间和一个加工时间.每台机器可以同时加工B≥n个工件.一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.给出了一个多项式时间近似方案(PTAS).
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 （B〉n） jobs as a batch simultaneously. 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.
出处
《软件学报》
EI
CSCD
北大核心
2006年第10期2063-2068,共6页
Journal of Software
基金
Nos.10271065,60373025(国家自然科学基金)
No.20051519(天津市教委科技发展基金)~~
关键词
多项式时间近似方案
调度
无界批量并行机
加权完工时间和
释放时间
polynomial time approximation scheme
scheduling
parallel unbounded batch machines
total weighted completion time
release times
