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

冯 琪, 杨丽华, 狄 帅

(1- 中原工学院理学院，郑州 450007; 2- 京东数字科技，北京 100015)

1 引言

排序(调度)就是在一定的条件下对工件(产品)和机器按时间进行分配和安排加工次序，使一个或多个指标达到最优.机器制造业的发展是排序发展的主要推动力.后来，随着社会的进步和经济的快速发展，在人们的工作和生活中产生了越来越多的排序问题.例如：如何将原材料放在机器上加工成人们需要的各种产品，并且用料最省或利润最大？如何将生产出来的零件以一定的次序快速组装成产品？在大型工程的兴建中，如何对各类人员进行安排，对各种器材的供应进行调度？对于种类繁多的网购物品，快递公司如何调度，使得快递员以最快速度把大量物品送到客户手中？这些都是排序问题.因此，在现代化的生活中，服务业、制造业、运输业、计算机科学等领域都有它的大量应用.排序的好坏直接影响着费用的高低和利润的大小！大多数经典排序文献所考虑的工件仅属于一个代理(客户).而在实际问题中，被加工的工件往往属于不同的代理.例如，一个企业或生产厂家，需要同时面对不同的客户，并且这些客户要竞争着使用共同的资源，假如两个客户的订单需要在同一时间、同一台机器或者同一个流水线上加工，决策者如何调度才能使利润最大化，并且让不同的客户都达到满意.因此，为了满足不同代理的需要，决策者需要在多个代理的利益之间进行权衡.这就产生了多代理排序.同时，在多数排序文献中，都是基于以下假设：所有的工件都必须在机器上加工，不允许拒绝任何工件.然而，在现实中这些假设并非总是成立的.由于资源的有限性，生产决策者经常会拒绝一些耗费资源且利润较低的工件.如果一个工件被拒绝，有时候基于信用或其他因素，商家不得不对所拒绝的客户支付一定的赔偿，称这种赔偿为拒绝惩罚或拒绝费用，这就出现了带有拒绝费用的排序(调度)问题.本文研究的就是这样的一个问题.

Agnetis 等人[1]首先研究了多代理排序问题，在异顺序作业环境下，他们主要研究了一般拟凸函数的Pareto 最优问题.此外，还介绍了所研究问题在不同领域的实际应用.后来，Baker 和Smith[2]对具有两个代理的单机排序问题，考虑了工件的目标函数有最大完工时间，最大延迟等.Agnetis 等人[3]也考虑两个代理排序问题，目标函数是工件完工时间的非减函数，并且工件不允许中断抢先.Agnetis 等人[4]把问题推广到两个以上代理.Yuan 等人[5]更新了文献[2]的一些结果并给出相应的最优算法.后来，Cheng 等人[6,7]中也考虑了单机多代理排序问题.Ng 等人[8]研究了两个代理的排序问题.另外，Leung 等人[9]推广了文献[3]的结果.建立了两个代理的排序问题与重新排序和约束排序之间的关系.Nong 等人[10]研究了两个代理排序问题的近似算法.Feng 等人[11]研究了多个代理的Pareto 最优问题.Feng 等人[12]研究了带有拒绝费用的单机多代理排序问题.Feng 等人[13]研究了机器带有禁用区间的多代理排序问题.有关这方面的更多结果可参见文献[14].

在本文中，通过对问题的分析，将所研究的问题转化为一个具有可用区间的工件可拒绝排序问题.有关这方面的研究结果，在国内外文献中还不多.Zhong 等人[33]研究了机器具有禁用区间的工件可拒绝排序问题.他们考虑了模型的近似性和重要的特殊情形.Li 和Chen[34]研究了一台机器上具有退化维修活动的工件可拒绝排序问题，目标是确定维修活动的位置和接收工件的序列，使得接收工件的排序费用与拒绝惩罚之和达到最小.Zou 和Yuan[35]也考虑了机器具有维修活动的工件可拒绝排序问题，并对所研究问题给出一系列的结果.

为了叙述方便，引入一些简单描述排序问题的符号.本文所涉及的相关记号如下：

2 全多项式时间近似方案

首先，给出全多项式时间近似方案的定义.

定义1 给定一个带有非负权重的优化问题P，如果存在一系列的多项式时间算法Aϵ，使得对问题P的任意一个实例I和每一个固定的ϵ ＞0, Aϵ都是优化问题P的一个(1+ϵ)-因子的近似算法，并且当ϵ是一个常数时，算法的运行时间是输入的一个多项式，那么称Aϵ为P的一个多项式时间近似方案，简记为PTAS(Polynomial Time Approximation Scheme).特别地，当算法的运行时间也是关于1/ϵ的一个输入多项式时，我们称Aϵ是该问题的一个全多项式时间近似方案，简记为FPTAS.

存在一个最优的排序满足下列性质：

性质1 被接收的A-工件以任意序列连续加工.

性质2B-工件按照最早工期优先加工规则(简称EDD 规则)加工，并且B-工件被划分成两部分(如果存在)，每一部分仍然按照EDD 规则加工.其中一部分连续地在序列的开始加工(如果存在)，剩余的B-工件则在序列的最后连续加工.

记

对于本文所讨论的问题，在文献[12]中，已经证明该问题是一般意义下NP-困难的，并且给出了一个动态规划算法和一个2-近似算法，由于本文算法与这两个算法关系密切，因此，下面列出这两个算法.

动态规划算法[12]

如果JA=Ø，停止.否则，令i:=i+1，转步骤2；

步骤5 在步骤3 得到的排序中选择具有最小目标值的排序.

则定理成立.

3 结论

本文研究了排序问题(1)，但这只是代理B的工件全部被接收且是单机上的情形，我们希望能得出代理B的工件如果部分被拒绝，或者平行机情形下的一些结果，这还有待于进一步的研究.