精确动态规划算法求解绿色单机调度问题

Exact dynamic programming algorithm for green single machine scheduling problem

针对一类生产实际中广泛存在的绿色单机调度问题,即带释放时间的低碳单机调度问题,提出一种精确动态规划算法(exact dynamic programming algorithm,EDPA)进行求解,优化的主要和次要目标分别为最小化最大延迟时间和总碳排放量.首先,建立问题的排序模型,该模型可用三元法表示为1|agr(rj,dj)|TCE/Tmax,属于NPhard问题;其次,通过分析排序模型的性质,提出基于工件排序和机器状态选择的交货期最早优先规则(earliest due date,EDD),可确保得到问题最优解;再次,根据所提出规则构建状态递推方程,进而基于该方程设计可对问题解空间执行状态树搜索的EDPA,该算法为具有伪多项式时间的精确算法,可以获取问题的最优解;最后,通过在测试问题和企业实例上的仿真实验,验证所提出算法不仅可以最小化最大延迟时间,而且还能有效地减少总碳排放量.

An exact dynamic programming algorithm(EDPA)is proposed for a kind of green single-machine scheduling problems,i.e.,the low-carbon single-machine scheduling problem with release times and due dates.The first and second optimization objectives are the maximum tardiness and the total carbon emissions,respectively.Firstly,the permutationbased model of the considered problem is built.This model can be described by triplet 1|agr(rj,dj)|TCE/Tmax,which is an NP-hard problem.Secondly,an earliest due date(EDD)rule based on job permutation and selection of machine state is presented by analysing the properties of the permutation-based model.Thirdly,the state recurrence equation is constructed via the presented rule,and then an EDPA is designed by using the constructed equation to execute the state-tree search in solution space.This algorithm is an exact algorithm with pseudo-polynomial time,which can obtain the optimal solution of the considered problem.Finally,the simulation experiments on the testing and real-world instances manifest that the proposed algorithm can not only minimize the maximum tardiness,but also reduce the total carbon emissions effectively.