机器带不可用时间限制的简单线性恶化供应链排序问题

作者：范静; 鲁习文

来源：运筹学学报, 2016, 20(04): 69-76.

DOI：10.15960/j.cnki.issn.1007-6093.2016.04.008

• 简单线性恶化
• 不可用时间限制
• 供应链排序
• 动态规划算法
• 完全多项式时间近似方案

研究的单机供应链排序问题中,机器有一个不可用时间限制,工件的加工时间与恶化率及其开工时间有关,且工件的加工不可恢复.一个或多个完工工件可组成一个发送批由车辆发送给客户,且在机器不可用时间限制之前完工的工件必须在限制开始之时或之前完成发送.问题的目标是最小化总发送时间与总发送费用之和.证明问题是NP-难的,提出了伪多项式时间的动态规划算法.进一步,在确定问题目标函数值的上界及下界之后,设计了一个完全多项式时间近似方案(FPTAS).

• 单位
  华东理工大学