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

昆明理工大学信息工程与自动化学院

作者简介:

通讯作者:

中图分类号:

TP273

基金项目:

国家自然科学基金项目(面上项目,重点项目,重大项目)


Exact Dynamic Programming Algorithm for Green Single Machine Scheduling Problem
Author:
Affiliation:

School of Information Engineering and Automation

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2019-12-06
  • 最后修改日期:2021-03-22
  • 录用日期:2020-03-06
  • 在线发布日期:
  • 出版日期: