计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2013年
8期
1700-1709
,共10页
批调度%拒绝%惩罚值%完成时间之和%动态规划
批調度%拒絕%懲罰值%完成時間之和%動態規劃
비조도%거절%징벌치%완성시간지화%동태규화
batch scheduling%rejection%penalty%total completion time%dynamic programming
考虑如下单机并行批调度问题:给定一些工件,每个工件有给定的处理时间以及惩罚值(可以拒绝处理某些工件,惩罚值为拒绝处理工件所付出的代价).给定一个可同时处理多个工件的批处理器.同时处理的工件形成一个批.同一批处理的工件具有相同的开始时间和结束时间,即开始时间加上这一批中所有工件的最大给定处理时间.判断如何选择要处理的工件,给这些工件分批以及给批排序使得目标函数值最小.对目标函数是被处理工件的完成时间之和加上被拒绝工件的惩罚值之和的情况,通过给出一个动态规划算法,证明当批容量为常量时问题是多项式时间可解的.
攷慮如下單機併行批調度問題:給定一些工件,每箇工件有給定的處理時間以及懲罰值(可以拒絕處理某些工件,懲罰值為拒絕處理工件所付齣的代價).給定一箇可同時處理多箇工件的批處理器.同時處理的工件形成一箇批.同一批處理的工件具有相同的開始時間和結束時間,即開始時間加上這一批中所有工件的最大給定處理時間.判斷如何選擇要處理的工件,給這些工件分批以及給批排序使得目標函數值最小.對目標函數是被處理工件的完成時間之和加上被拒絕工件的懲罰值之和的情況,通過給齣一箇動態規劃算法,證明噹批容量為常量時問題是多項式時間可解的.
고필여하단궤병행비조도문제:급정일사공건,매개공건유급정적처리시간이급징벌치(가이거절처리모사공건,징벌치위거절처리공건소부출적대개).급정일개가동시처리다개공건적비처리기.동시처리적공건형성일개비.동일비처리적공건구유상동적개시시간화결속시간,즉개시시간가상저일비중소유공건적최대급정처리시간.판단여하선택요처리적공건,급저사공건분비이급급비배서사득목표함수치최소.대목표함수시피처리공건적완성시간지화가상피거절공건적징벌치지화적정황,통과급출일개동태규화산법,증명당비용량위상량시문제시다항식시간가해적.
