极小化加权完工时间和的无界批量机器并行调度问题

摘要：

考虑无界批量机器并行调度中极小化加权完工时间和问题.设有n个工件和m台批加工同型机.每个工件具有一个正权因子、一个释放时间和一个加工时间.每台机器可以同时加工B≥n个工件.一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.给出了一个多项式时间近似方案(PTAS).

关键词：多项式时间近似方案、调度、无界批量并行机、加权完工时间和、释放时间

所属期刊栏目：17

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金10271065;60373025;天津市教委资助项目20051519

在线出版日期：2006-11-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：2063-2068