工件可拒绝的两个代理排序问题的全多项式时间近似方案

摘要：

本文研究单处理机上工件可拒绝的两个代理的排序问题.在此问题中,有两个代理A和B,分别有各自的工件集和费用函数.代理A的工件可以被接收,也可以被拒绝,但要支付一定的拒绝费用.代理B的工件要全部接收.代理A的费用函数是他的接收工件的最大完工时间与拒绝工件的拒绝费用之和,代理B的费用函数是他的工件的最大延迟.排序问题的目标是在满足代理B的费用函数不超过一定数量的前提下,使得代理A的费用函数达到最小.对于该问题给出了一个全多项式时间近似方案.

关键词：排序、代理、拒绝、近似方案

所属期刊栏目：38

分类号：O224(运筹学)

资助基金：国家自然科学基金;国家自然科学基金;河南省高等学校重点科研项目;青年骨干教师项目

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

页数：共8页

页码：369-376