具有多个不可用时间段的单机供应链排序问题

在单机供应链排序问题中,机器会有多个长度确定的不可用时间段,它仅可以在可用时间段内加工工件,且每个可用时间段的长度不大于给定的常数.多个完工工件可组成一批由一个容量无限制的运输工具发送给客户.问题的目标是如何安排工件的加工、发送以及不可用时间段,以使总发送时间与总发送费用之和达到最小.对于工件加工可恢复的情况,可在多项式时间O(n^2)内得到最优序.对于工件加工不可恢复的情况,证明了问题是强NP-难的,并提出了2-近似算法.

具有多个受限制可用时间段的单机供应链排序问题

在文中所研究的单机供应链排序问题中,机器可用时间段的长度不大于给定常数,且每个不可用时间段长度确定。工件仅可以在机器的可用时间段内被加工,完工后可与其他完工工件组成一批,由一个容量无限制的运输工具发送给客户。运输工具在机器的每个可用时间段结束时间进行发送,且每次发送的费用固定。问题的目标是安排工件的加工、发送,以及机器的不可用时间段,以使总发送时间与总发送费用之和达到最小。对于工件允许中断的情况,可在多项式时间O(n log n)内得到最优序(n为工件的个数)。对于工件不允许中断的情况,证明了问题是强NP-难的,并提出了2-近似算法。

一维装箱问题的交叉算法分析

2004年孙春玲等研究了一维装箱问题,给出了一个近似程度最好的近似值为3/2的近似算法-交叉算法.遗憾的是他们的交叉算法的近似值分析是错误的,本文通过两个反例说明了他们的错误所在,并给出一个正确的近似值分析.