最小化完成时间和加惩罚值和的批调度问题

摘要：

考虑如下单机并行批调度问题:给定一些工件,每个工件有给定的处理时间以及惩罚值(可以拒绝处理某些工件,惩罚值为拒绝处理工件所付出的代价).给定一个可同时处理多个工件的批处理器.同时处理的工件形成一个批.同一批处理的工件具有相同的开始时间和结束时间,即开始时间加上这一批中所有工件的最大给定处理时间.判断如何选择要处理的工件,给这些工件分批以及给批排序使得目标函数值最小.对目标函数是被处理工件的完成时间之和加上被拒绝工件的惩罚值之和的情况,通过给出一个动态规划算法,证明当批容量为常量时问题是多项式时间可解的.

关键词：批调度、拒绝、惩罚值、完成时间之和、动态规划

所属期刊栏目：50

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

资助基金：国家自然科学基金项目60603007;山东省优秀中青年科学家奖励基金项目BS2009DX009;山东大学自主创新基金项目2012TS068

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

页数：共10页

页码：1700-1709