范静(上海第二工业大学理学院,上海201209)



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

范静
(上海第二工业大学理学院,上海201209)

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

关键词:可用时间段;供应链排序;强NP-难;近似算法

0　引言

供应链排序是把生产、分批和发送三者集成在一起,研究集成优化的模型及其算法[1]。实际上,供应链排序就是在排序决策范畴内研究供应链管理,是排序论在供应链管理中的应用。供应链排序的第一篇论文是由Potts[2]于1980年发表的。2003年Hall和Potts[3]在论文中系统地提出了供应链排序模型。此后,学者们对于供应链排序问题的研究就越来越多了。本文研究的是两阶段供应链排序问题,即工件在机器上加工后由运输工具,如卡车、轮船等,从工厂出发运输给客户。由于运输任务往往是由第三方物流公司负责的,所以可以认为运输工具的数量无限制,但会产生一定的运输费用。……