带有单服务器的并行机调度问题

摘要：

研究了一类具有准备时间和移出时间约束的单服务器并行机调度问题.这个问题概括了工件仅需要准备操作的经典单服务器并行机调度问题.在该问题中,服务器不仅需要在每个工件加工之前将其装载到一台机器上,而且在工件加工结束后,将其从机器上卸载下来,装载和卸载操作需要一定的时间.目标函数为最小化最大完工时间.主要研究指定机器加工的情况,针对这种情况,构建了多项式时间内可解的启发式算法.该启发式的值与最优值的比值为2,且证明了该界为紧界.

关键词：调度、并行机、单服务器、NP-难、启发式

所属期刊栏目：24

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

资助基金：2011年辽宁省教育厅科学研究一般项目L2011207

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

页数：共4页

页码：66-69