工件可拒绝的单机多任务排序问题研究

作者：徐晨; 徐寅峰; 郑斐峰; 刘明

来源：系统科学与数学, 2022, 42(08): 2198-2206.

• 多任务排序
• 单机
• 工件可拒绝
• 动态规划

文章研究了工件可拒绝的单机多任务排序问题.在多任务环境下,当某个工件(主工件)在加工时,会被其他未完成加工的工件(等待工件)所打扰,则主工件的实际加工时间由三部分组成:主工件剩余部分的加工长度,等待工件的打扰时间以及等待工件的切换时间.在经典的排序模型中,要求每个工件都被加工,然而在高负荷的定制化生产系统中,接受所有工件可能会导致订单交付延迟,进而导致高成本,故文章考虑了工件可拒绝的排序问题.为了保证一定的服务水平,要求拒绝工件的总惩罚不超过给定值,目标是选择哪些工件加工并给出其排序以使得最大完工时间、总完工时间和总加权完工目标最小.这三个问题都是NP-难问题,对此给出了伪多项式时间动态规划算法.

• 单位
  东华大学; 经济管理学院; 同济大学