按外包工件个数不同折扣率的单机排序问题

摘要

排序论是运筹学和管理科学中非常重要的一个分支. 在经典的排序问题中，所有的工件都必须在生产商内部机器上进行加工，即拒绝或者外包工件不被允许.然而，随着工件数量的增加，内部加工所有的工件可能会导致很多工件延误，从而降低顾客的满意程度.因此，最近 10多年来，很多学者开始研宄工件可拒绝或者工件可外包的排序问题.在工件可拒绝或者工件可外包的排序问题中，一个工件如果被拒绝或者被外包，生产商需要支付一个对应的拒绝费用或者外包费用. 显然，拒绝或者外包一部分工件，生产商可以把更多的资源提供给VIP顾客，从而提高顾客的满意程度.如果我们把一个工件的拒绝费用看成外包费用，其实工件可拒绝排序和工件可外包排序是等价的. 目前，在几乎所有的工件可拒绝排序和工件可外包排序文献中，工件的拒绝费用或者外包费用总是固定不变的. 目标都是在内部加工工件对应的一个目标函数和全部拒绝(或者外包)费用之间寻找一种均衡. 然而，在工件可外包排序中，从外包商的角度出发，为了鼓励生产商外包更多的工件，外包商往往会根据外包工件个数、全部外包费用以及外包工件在外部机器上生产的时间段提出一系列的折扣方案.也即，可以在初始的外包费用基础上进行打折.按个数折扣是市场上最普遍的一种折扣方式和促销手段. 在这篇论文中，我们主要考虑了按外包工件个数不同折扣率的单机排序问题.在该类问题中，每个工件J j有一个初始的外包费用ej. 工 件 J j或者在一台内部单机上进行加工，或者被外包给外包商进行加工.令 O 为所有外包工件构成的集合且O 为内部加工工件构成的集合.令 m=|O|为外包工件集合O 中的工件数量.我们假设有k 个不交的工件个数区间[0,Ni)，[N1,N 2) ,… ,[Nk-1,N k).每个区间[Ni-1,Ni) (1 ≤ i≤ k)对应着不同的折扣率D R” 这里我们假设1=D R > D R > … > D R k > 0 .如果 m ∈[Nt-i ，N t ),则每个外包工件Ji的实际外包费用为ej=DRt .ej. 显然，在该模型中，生产商为了享有更低的折扣，他不得不外包更多的工件.然而，外包更多的工件，虽然折扣更低，但是往往实际支付的外包费用也越多. 因此，生产商为了使一个给定的目标函数达到最小，需要确定有多少个工件被外包，哪些工件被外包以及内部加工工件如何加工. 在第二章中，我们考虑了具有相同到达时间的单机排序问题.我们研宄了四个不同的目标函数，即最大完工时间Cmax,最大延迟Lmax，完工时间和∑C j以及加权完工时间和∑ w Cj. 对目标函数为最大完工时间Cmax与完工时间和E C j的单机排序问题，本文分别给出了多项式时间的最优算法；对目标函数为最大延迟Lmax与加权完工时间和∑WjC j的单机排序问题，本文分别证明了这两个问题都是NP-困难的并给出了拟多项式时间的最优算法. 在第三章中，我们考虑了具有不同到达时间的单机排序问题.所研究的目标函数为最大完工时间Cmax.我们证明了该问题是N P-困难的并给出了两个拟多项式时间的最优算法.最后，对于该问题，我们也给出了一个2-近似算法和一个全多项式时间近似方案.

目录

第一个书签之前