工件可外包的单机准时排序问题

作者：李寒雪; 樊保强^*; 陈继文; 郭志佳; 杨燕英; 李欣

来源：重庆师范大学学报(自然科学版), 2019, 36(06): 15-21.

• 准时排序
• 动态规划
• 外包费用
• 算法

【目的】研究一类单机准时排序问题,其中工件有公共的交货期和交货截止期,允许工件外包加工,外包加工将产生外包费用,目标是极小化总提前时间,总延迟时间与总外包费用之和。【方法】首先给出该问题的若干最优性性质,然后对于交货期和交货截止期都待定,以及给定交货截止期两种情形分别讨论。【结果】对于第一种情形,设计了多项式时间算法,对于第二种情形,证明了它是NP-困难的并设计了伪多项式时间的动态规划算法。【结论】所讨论的单机准时排序问题所得到的结果为冷鲜食品生产管理者提供了有效决策支持。