School of Information Engineering and Automation
针对一类生产实际中广泛存在的绿色单机调度问题，即带释放时间的低碳单机调度问题，提出一种精确动态规划算法（exact dynamic programming algorithm, EDPA）进行求解，优化的主要和次要目标分别为最大延迟时间和总碳排放量。首先，建立问题的排序模型。该模型可用三元法表示为 ，属于NP-hard问题。其次，通过分析排序模型的性质，提出基于工件排序和机器状态选择的交货期最早优先规则（Earliest due date, EDD），可确保得到问题最优解。然后，根据所提规则构建状态递推方程，进而基于该方程设计可对问题解空间执行状态树搜索的EDPA。该算法为具有伪多项式时间的精确算法，可获取问题的最优解。最后，通过在测试问题和企业实例上的仿真实验，验证所提算法不仅可最小化最大延迟时间，也能有效地减少总碳排放量。
An exact dynamic programming algorithm (EDPA) is proposed for a kind of green single-machine scheduling problem, 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 permutation-based model of the considered problem is built. This model can be described by triplet , which is an NP-hard problem. Secondly, an earliest due date (EDD) rule based on both the job permutation and the 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, and it can obtain 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.