智能电网中最小化成本高效调度任务

摘要

智能电网中的新兴应用对在一组具有不同成本的同型并行机之间的调度作业提出了挑战,旨在以最小的总成本完成作业.在离线环境中,有一组作业以及同型并行机.每个作业由元组(rj,dj,pj,hj)组成,其中rj,dj,pj和hj分别表示作业j的发布时间、截止时间、所需的处理时间以及作业在机器上运行时产生的负载.我们将时间间隔划分为一组时隙T.而且,对于每个时隙t∈T,每台机器i都有一个工作负载容量Sit和阈值Lit,其中每台机器的工作负载应该不大于Sit也不小于Lit.每台机器的电价可能不同.其目标是在所有机器上和时隙中找到所有作业的调度,从而使电力的总成本最小化.我们证明了我们提出的针对可抢占式作业的线性规划(LP)是整多面体,并且具有整基本解.