带有截止日期和拒绝的单机总加权误工量排序问题

摘要：

工件可拒绝排序问题是从实际问题中提炼出来、具有较强应用背景的问题.在实际生产中,制造商可能会选择拒绝加工一些成本高、耗时长或回报低的工件,并支付一定的费用.考虑在截止日期的约束下,工件可拒绝的单机排序问题的目标函数为总加权误工量与拒绝惩罚之和,其中工件的误工量是指这个工件误工时在工期之后的加工时间.在此排序问题中,每个工件都有一个截止日期.首先,说明了在截止日期的约束下,当工件的工期相同时,极小化总加权误工量与拒绝惩罚之和的单机排序问题是NP-难的;其次,利用依次列举关键工件的方法求解此问题,给出了时间复杂度为O(n3d)的拟多项式时间动态规划算法;最后,用数值例子进行了验证.

关键词：单机排序、拒绝、截止日期、误工量

所属期刊栏目：40

分类号：O223(运筹学)

资助基金：辽宁省教育厅科学研究经费项目LFW202001

在线出版日期：2022-07-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：168-173