论文研究-岗位存在占有者条件下人岗双边匹配I-ES算法.pdf

所需积分/C币:50 2019-09-20 21:02:35 643KB .PDF
收藏 收藏
举报

论文研究-岗位存在占有者条件下人岗双边匹配I-ES算法.pdf,  本文对岗位存在占有者条件下的人员与岗位一对多双边匹配问题进行了研究.首先,对岗位存在占有者条件下的人岗一对多双边匹配问题进行描述;然后,给出岗位存在占有者条件下的人岗双边匹配方案、岗位存在占有者条件下的个体理性匹配方案、岗位存在占有者条件下的稳定匹配方案和岗位存在占有者条件下的公平匹配方案的定义;进一步地,在考虑双方匹配主体
第5期 姜艳萍,等:岗位存在占有者条件下人岗双边匹配IES算法 1195 本文考虑如下两种形式的偏好关系:优于(“>”),无差异(“~”).并且1和h2越小,表明4k和 越偏好与P匹配rk和〃2越小,表明P越偏好与A2和A2匹配不失一般性,下面以4对其感兴趣 的岗位P和P给出的序值h和h为例进行说明 1)h1 表明Ak2认为P优于P,即 2)3=1表明Ak认为P和P是一样好的,即P~Pf 需要指出的是,由于位占有者相较外部申请者对原岗位P的工作熟悉程度更高,经验更丰富,因此,岗 位对原占有者最满意,令rM=r=…=7k=1,k=1,2,…,m;于岗位占有者能够获得更好的工作机 会时才会申请转岗,即对于其感兴趣的所有岗位而言,原岗位排在其感兴趣的所有岗位的最后一位.为方便 描述设O表示Ak2认为有O个新中请的岗位位于第d位上,则hk=1+∑=1O,=1,2,…,1k 本文要解决的叫题是:基于中请者和岗位给出的偏好序h1,2和k,12,确定一个具有稳定性和公 平性的人岗双边匹配方案 3概念界定 结合位存在占有者条件下的人岗双边匹配问题的自身特点,在文献[18]的基础上,给出岗位存在占有 者条件下的人_双边匹配的相关定义 定义1岗位存在占有者条件下的人岗双边匹配是一类特殊的一对多双边匹配,可以定义为映射u:A P→24,VA2,A2∈A,YP;∈P,满足下列条件:1)p(A2)P,|(A1)=1;2)(42)<P u(A2)≤1,特别地,若|(42)=0,则称A2没有匹配对象;3)μ(P)sA,|μ(P川≤Q,特别地,若 u(P)=0,则称P没有匹配对象;4)1(41;)=P,当且仅当Ak;∈以(P);5)山(43)=P,当且仅当 A2∈H(Pk).其中,以(Ak)=1表示Ak必须有一个岗位能与其实现匹配:(A2)≤1表示A2最多只能有 个岗位能与其实现匹配;(P)≤Q;表示P招收的员工数量不能超出它的招聘限额Q 31岗位存在占有者条件下的个体理性匹配方案 对于岗位占有者而言,为了能够得到更好的发展,通常会选择与现有岗位相比排序更靠前的新岗位,如 果没有匹配到排序更靠前的新岗位,占有者宁愿回到原岗位,这种现象称为岗位占有者个体理性;对于外部 申请者而言:宁没有工作也不崽意从事其不能接受的工作,这种现象称为外部申请者个体理性.如果岗位 占有者与外部申清者都是个体理性的,称申请者个体理性.若一个匹配方案中,所有的申请者都是个体理性 的,则称这个匹配方案是申请者个体理性匹配方案下面给出具体定义 定义2岗位存在占有者条件下的人岗双边匹配,若同时满足以下两个条件成立:1)V4k2∈A,不 妨设(A4k:)-P3,对于B∈P,kj,满足:h12<h;2)V42∈A2,不妨设(42)-P,均满足 h23<V+1.则称匹配方案为申请者个体理性匹配方案 注1由定义2可知,申请者个体理性匹配方案,对于岗位占有者而言,若其没有与原岗位形成匹配,则 一定是与其更偏好的岗位形成匹配;对于外部申请者而言.只能与其感兴趣的岗位形成匹配 对于岗位而言,企业在招聘员工时希望能够达到自己的最高限额,但是,会遇到申请者的条件不满足岗 位需求的情况,此时岗位宁愿有空缺职位也不愿招进不符合条件的申请者,这种现象称为岗位个体理性.若 个匹配方案中,所的岗位都是个体理性的,则称这个匹配方案是岗位个体理性匹配方案.下面给出具休 的定义 定义3岗位存在占有者条件下的人岗双边匹配μ,若满足下列条件之一:1)对vP∈P,若(P)=Q 且对A∈(P1),42∈p(P),均满r<U+1,72<U+1:2)对A∈41UA2,若(A)=P且 对VB∈P,b≠j,H(P)<Q,均满足:h<h:=U+1;3)对VAe∈AU2,若|(4)=0且对 VP∈P,1P川<Q均满足:h<v+1,m=U+1,则称p为岗位个体理性匹配方案 注2由定义3可知,岗位个体理性匹配方案,对于岗位而言,若招聘人数已达到其招聘限额,则与其形 成匹配的都是其感兴趣的中请者;若招聘人数未达到其招聘限额.说明对未与其形成匹配的中请者都不是其 感兴趣的 1196 系统工程理论与实践 第38卷 定义4对于岗位存在占有者条件下的人岗双边匹配p,若即是申请者个体理性匹配方案又是岗位个 体理性匹配方案,则称这个匹配方案是个体理性匹配方案 32岗位存在占有者条件下的稳定匹配方案 所谓稳定匹配方案是指符合个体理性且不存在阻寒对的匹配方案.由于岗位存在占有者条件下的人岗 双边匹配问题中存在两类申请者,是一类特殊的双边匹配间题,因此,根据申请者的种类将阻塞对分为两类 岗位占有者与岗位阻塞对和外部申请者与岗位阻塞对.下面给出具体描述 在匹配方案中,对于没有形成匹配的岗位占有者与岗位满足下列三个条件之一时:1)岗位占有者在σ 范围内认为未满额的岗位优于其当前匹配的岗位.且该未满额的岗位也认为该岗位占有者的排序值小于等于 σ;2)在σ范围内,岗位占有者认为满额的岗位优于其当前匹配的岗位,且该满额的岗位也认为该岗位占有 者优于与其形成匹配的一个岗位占有者或一个外部申请者.该岗位上有者与岗位会放弃已有匹配对象而私 下进行匹配由此造成原有匹配方案的不稳定和匹配失效的现象,称该岗位占有者与岗位为匹配方案的a 岗位占有者与岗位阻塞对.具体的数学定义如下 定义5对于岗位存在占有者条件下的人岗双边匹配:AUP→21012,对于vAk,A1∈A1.A2∈ A2,Pg,P1∈P,i≠,9≠j如果Ak2和P满足如下三个条件之一1)(P)<Q;,p(4k:)=P, 满足b<≤,m≤m;2)1(P)=Q3,(A)=Pg,1(A1)=P,满足b1<b≤m且 rk<n≤a;3)(P)=Q1,(A4)=P,H(4)=P,满足<h≤且k<72)≤0.则称匹配 对(42,P)是匹配的一个a岗位占有者与岗位阻塞对 在匹配方案中,对于没有形成匹配的外部申请者与岗位.满足下列六个条件之一时:1)外部申请者没有 匹配到任何岗位,存在岗位没有满额,且双方的排序值对于对方而言都小于等于σ;2)外部申请者认为未满 额的岗位优于其当前匹配的岗位,且该未满额的岗位也认为该外部申请者的排序值小于等于σ;3)外部申请 者没有匹配到任何岗位,存在一个对它而言排序值小于等于σ且已经满额的闵位认为该外部中请者在σ范 围内优于与其形成匹配的一个岗位占有者或一个外部中请者;4)在σ范围内外部中请者认为满额的岗位优 于其当前匹配的岗位,且该满额的岗位也认为该外部申请者优于与其形成匹配的一个岗位片有者或一个外部 申请者.该外部申请者与位会放弃已有匹配对象而私下进行匹配,由此造成原有匹配方案的不稳定和匹配 失效的现象,称该外部申请者与岗位为匹配方案的σ-外部申请者与闵位阻塞对.具体的数学定义如 定义6对于岗位存在占有者条件下的人岗双边匹配:A2UP→240P,对于4∈A1,V42,42∈A2 日Pg,P∈P,5≠e,9≠如果A2和P满足如下条件之一:1)p(P)<Q,(A42)=0,满足h23≤a, n2≤o;2)1(P)<Q1,(42)=P,满足h<h3≤0,m2≤a;3)(F,)=O,(42)=0, 1(A4)=P满是h≤0,72<≤0;4)|(P川=Q1,|p(A)=0,(42)=P,满足h2≤σ 2<m≤0;5)1(P川=Q1,H(A)=P,(4k)=P,满足h2<h2≤a且72<rk≤;6) (P)=Q3,(42)=P,(A)=P,满足h8<3≤a且7232<72≤则称匹配对(42,P)是匹配 1的一个a-外部申请者与岗位阻寒对 定义7对于岗位存在占有者条件下的人岗双边匹配:AUP→2A,如果〃即是个体理性匹配方案 又不存在a-岗位占有者与岗位阻塞对和σ-外部申请者与岗位阻塞对,则称八为关于A和P的σ-稳定匹 配方案否则称为σ-不稳定匹配方案.特别地,当a=max{U,V}时,称|为关于A和P的全稳定匹配方 案,否则称为不稳定匹配方案 由定义7可以看出,σ-稳定匹配方案一定是全稳定匹配方案,反之,未必成立 33岗位存在占有者条件下的a-公平匹配方案 在一个匹配方案中,对于已经形成匹配对的匹配主体而言,若双方匹配主体对对方而言都满足排序值小 于等于σ,1≤σ≤V,这种现象称为a-公平匹配方案.下面给出-公平匹配方案的定义 定义8对于岗位存在占有者的人岗双边匹配,对Ae∈A=41UA2,不妨设μ(A)=Pk,均满足 h≤a且r≤a,则称为a公平匹配方案 定义9对于岗位存在占有者条件下的人岗双边匹配μ,若μ即是a-稳定匹配方案又是a-公平匹配方 第5期 姜艳萍,等:岗位存在占有者条件下人岗双边匹配IES算法 1197 案,则称p为关于A和P的a公平稳定匹配方案 4存在占有者的改进的公平选择算法 针对岗位存在占有者条件下的人岗双边匹配问题.为了获得使双方尽可能公平的稳定匹配方案,借鉴解 决一对双边匹配问题的公平选择( equitable selection,ES)算法17的思想,本文提出了改进的公平选 择( improved- equitable selection,IES)算法.该算法的核心思想是:为岗位占有者赋予更高的优先权,即岗 位占有者先向岗位发出申请,之后,外部申请者发出申请.首先,按照匹配顺序,排在最前面的申请者向其偏 好列表中前a位的闵位依次发出申请;然后,收到申请的闵位进行反选,若该申请者也在其所申请的岗位的 前σ位且闵位还未满额,则暂时接受该申请者,若收到申请的岗位已达到最高限额则只有当该申请者优于该 岗位已暂时匹配的申请者中的仟意一个时,才能接受该申请者并且拒绝当前最差的一个已匹配的申请者;进 步地,被拒绝的申请者向其偏好列表中前σ+1位的岗位依次发出申请.收到申请的岗位再次进行筛选;重 复上述步骤,直到所有申请者都找到岗位与其匹配或再也无法找到符合其要求的岗位 首先对算法中的变量进行描述: 表示双方匹陀主体的接受水平;A10)=41,412,…,A1,41,42,…,42 表示在接受水平a下可以发出申请的位占有者集合;A2()={42,A2,…,A2}表示在接受水平a下可以 发出中清的外部请者集合;P2,P分别表示在接受水平a下Ak和A2认为符合其接受水平的其感兴超 的岗位集合.9P,表示在接受水平a下P持有的申请者集合 7∈10,1,2,P∈P为接受水平为时P的状态标记,其中,T,=0表示岗位P未满额,可接 受申请者的申请;邛吕=1表示岗位P已满额,但仍可再接受申请;T=2表示岗位P已满额,不再接受 申请T1∈{0,1},A∈A1为接受水平为a时4k2的状态标记,其中,T1=0表示4k2可以发出申 请,T-1表示4k不能再发出申请:2∈{0.1,2},42∈A2为接受水平为时A2的状态标记其中, T2=0表示A2可以发出中请,T42=1表示A2实现匹配不能再发出中请,T2=2表示A2未实现匹配 不能再发出申请 本文提出的IES算法可描述如下: step初始化迭代变量令=0,9=,7=0,71=0,T2=0,A1(=4h1,A2, A 2 A2(0 A2},P2=0,P=0,51=(51,51 S1l17S21 >m17>) n)和52=(52,52,…,5)分别为随机生成的岗位占者的匹配序 值向量和外鄙申请者的匹配序值向量,其中,5和52分别表示A2和43的匹配序值,当9≠k或者 g=k,t≠i时,k≠5lt;当s≠e时,≠2.当k<5时,Ak先于A向岗位发出申请,当s3<52 时,A2先于A2向岗位发出申请 Step1依据51,由匹配序值最小的能发出申请的岗位占有者向集合P中排序值最小岗位发出申请; 若有多个排序值最小的岗位时,则从中随机选取一个岗位即由Ak;= arg min{5k|Ak∈A1(o)向P arg mm{h|P∈P}发出申请; Step2收到申请的岗位P;对岗位占有者进行反选,存在如下情形: (1)1>0或者rk=U+1,Ah破拒绝确定A和P的状态值:T1=0,A1q)=A1(m-),T \{P},当 时,转Ste3,当P≠0时,转Step1; (2)rk≤0<U+1.考虑如下三种情形: (当T1=0时,P接受A,91=92u{4 确定P;的状态值TP (a)当22|=Q1,m<j≤V时,设A(或A2)- arg max{n,72|Ah,A42∈9},mn(或r2) 7=2r(或72)>Q,T (b)当P|=Q,1≤j≤m时,设 arg maxim ≠ (c)当|9p<Q;时,Tp=0 1198 系统工程理论与实践 第38卷 再确定Ak2的状态值T =1,A1()=A10-1){4k}.当A1()=时,转Step4;当A1()≠时,转Step1; i)当 设41(或4)=m4,4∈9号,列≠或者=k≠出2 rl(或>72)时,P拒绝A 确定A1和P的状态值Tx2,和T2:T1=0,A10)=A1(m1,=T,F=Pm乃} 当P=时,转Step3,当P≠时,转 )当mg1=1,设41/(或42)= arg max{ a r, A2 1 yfd|y∫ ,y≠k或者y=k,f≠,T< 好(或≤72)时,P接受A3,P2=922U{4{4(或4)} 确定P的状态值T a)对于位P,m<j≤V,有A(或A)= arg max{rl,2|4,A292,r减r2) 或2)>Q;,T (b)对于岗位P,1≤j≤m,有Ah= arg max{mAh∈P2},rn=1,TP=2;rm ≠1,T 再确定A和A(或A2)的状态值m和a(或T2) 1,1=0(或0<N时,24=0或丌≥2时,T42=2).A1()=41(a-1)u{4 {A}(或A1()=A(-1)\{41},A2()=42(-1)U{A2};或A1(q)=A(-1)\{Ak},A2) A20-1).当A1)=(时,转Step4;当A1()≠时,转Step1; step3a=a+1,若≡Ah∈A1(,有mx1=0转Step1;否则转Step4; 请:若有多个排广值最小的岗位时则从中随机选取一个岗位即A2=mm(e2A2∈A2)分 Stcp4依据2,由匹配序值最小的能发出申请的外部申请者向集合P中排序值最小岗位发出 arg mn{h2|∈P}发出申请; Step5收到中请的岗位P对外部中请者进行反选,存在如下两种情形: (1)2>a或者r2=U+1,或者T1=2,A2被拒绝.P=P\{P}确定A2和P的状态值 和T 当σ<N2时 0.A2( P2=1,当P=0时,转Step3.当P≠0时,转 Step 4 2时 A T-1,转Step4 (2)r2≤σ<U+1,考虑如下三种情形 (1)当1=0时,P接受42,922=92P1U{42} 确定P的状态值Tm2 (a)当|2P,=Qy当 ≤V时,设A(或A ∈9g},当r(或 r2)=Q,时,T2=2;当r(或n2少)>Q,时,T1=1 (b)当P1|=Q,1≤j≤m时,g=1; (c)当922<Q;时,T,=0 再确定A2的状态值x2 m42=1,A2)=A2(-1){42}.当A2()=时,转Sep6;当A0)≠的时,转Sep4 ()当m21=1,设4(或4)= argmax{,nA,42∈1),d≠s,满足3y2m(或>72) 时,P拒绝A3,P=P\{P} 确定A2和P的状态值T22和TP (a)当 2(a-1) 当P=0时,转Step3,当P≠0 时,转Step4; (b)当a>N2时,2=2,A0=Am43}.T 转Step4 第5期 姜艳萍,等:岗位存在占有者条件下人岗双边匹配IES算法 1199 1)当2-1设4成4)一m4,4∈!1.d≠,满足2y<m(或 1U{43N{4 (或A)} 确定P的状态值TP (a)对于岗位P,m<j≤V,设A(或A2)= arg max{rmn,2Ab,A42∈!2},m(或r2)=Q 时,T=2当r(或n2)>Q时,T=1; (b)对于岗位P,1≤j≤m,T 再确定A与4威4)的状态值4:和T4;(或T 4=1,T1=0(或0<N时,T2=0或0≥N时,2=2.A()=A1(-1u(4 A20)=A20-1)\{42}(或A1)=A1(-1,A2()=A2(-1u{A2{A3};或A1)=A1(-1, A2()-A20-1)\{42}).A()-0,A2()-0时,转Step6;当A()≠时,转Step1;当A =,A2()≠时,转Step5 step6算法终止,当接受水平为σ时,所有的外部申请者都被接受或未被接受的外部申请者已经向偏 好列表中的所有岗位发出了申请.所有的申请者与接受它的岗位形成匹配对,所有匹配对形成匹配方案.未 被岗位接受的申请者和未接受申请者的岗位均未实现匹配 下面对I-ES算法进行理论分析与证明 性质1岗位占有者均能实现匹配 证明设为所获得的匹配方案,采用反证法假设中存在412∈A1未实现匹配,根据LES算法的 Step3可知,若A没有实现匹配,则一直会向其最喜欢的并且没有拒绝过他的岗位发出申请,直到向其原 岗位Bk发出申请为止由于r=1且Qk≥lk,故根据IES算法的Step2可知,此时P接受Ak,并且 不会有其他申请者取代A2与BRk形成匹配.即岗位占有者A2最差也能与原岗位匹配故岗位占有者均能 实现匹配 性质2外部申请者A2未实现匹配时,只存在如下两种情形:(1)对A2而言排序值小于等于σ的岗 位都已满额,且与岗位匹配的申请者的排序值都小于A2的排序值:(2)对A2而言,排序值小于等于a的岗 位未满额,但是对未满额的位而言,A2的排序值大于σ 证明根据IES算法的Step4可知,由外部申请者A2向排序位于前a位的岗位依次发出申请,此时 收到申请的岗位P要么拒绝A2,要么接受A2.若P拒绝A2,此时只存在两种可能 ①P;对A2的排序值大于σ.根据IES算法的Sep5(1)可知,r23>σ时,无论P是否满额都会拒 绝A2.显然,A2的排序值大于σ并且大于任意一个与P暂时形成匹配的申请者的排序值性质2(2)成立 ②P}对A2的排序值小于等于σ.若P’拒绝A2,根据LES算法的Step5(2)i)可知,此时P满额 且对A2的排序值大于任意一个与P暂时形成匹配的申请者排序值.性质2(1)成立;若P接受A2,但最 终未与其实现匹配,即門暂时接受A2,但是在算法运行的过程中,P放弃了A32,根据IFS算法的Step 5(2)(i)可知,P已经满额并且选择了比A2排序值更小的其他申请者,而A2是暂时与P匹配的申请者中 排序值最大的,因此,最终与P匹配的申请者的排序值都小于A2的排序值.性质21)成立 定理1当申请者均为外鄙申请者,岗位的限额均为1,岗位与申请者均给出严格偏好序时,即当j≠f 时,2h,并且当kp时,k千mh,≠E时,31+2y,h+73y,⊥ES算法可以退化为 公平选择算法 证明当申请者均为外部申请者,即A1()=0,则IES算法直接运行Stp4,即选择匹配序值最小的外 鄧申请者由该申请者会向闵位发出申请,转Step5.由于岗位的限额均为1.岗位与申请者均给出严格偏好 序,则在Step5(2)(i)中只需考虑(a)、(c),Step5(2)(i)中只需考虑r2>n2),Step5(2)(i)只需考虑(a) 此时,IES算法退化为公平选择算法 由定理1可见,公平选择算法是IES算法的特例 定理2I-FS算法获得的匹配方案为个体理性匹配方案. 证明根据ⅠES算法流程可知,中请者只会向其感兴趣的岗位发出中请,因此IES算法获得的匹配方 1200 系统工程理论与实践 第38卷 案一定是申请者个体理性的根据IES算法的Step2(2)和Step5(2)中的r21≤a<U+1可知,收到申请 的岗位只会接受排序值小于U+1的申请者,即与其实现匹配的申请者都是其感兴趣的.因此,IES算法获 得的匹配方案一定是闵位个体理性的山定义4可知IES算法获得的匹配方案为个体理性匹配方案 定理3IES算法获得的匹配方案为σ-公平匹配方案 证明根据IES算法的Step1和Step4可知,申请者只会申请排在前σ位的其最喜欢的岗位,因此与申 请者形成匹配的岗位的排序值一定小于等于σ,根据IES算法的Step2(2)和Step5(2)中的r2<a<U+1 可知,收到申请的岗位只会接受排序值小于等于σ的申请者.由定义8可知,IES算法获得的匹配方案为a 公平匹配方案 定理4IES算法获得的匹配方案不存在σ-外部申请者与岗位阻塞对和σ-岗位占有者与岗位阻塞对 证明设u为所获得的匹配方案,采用反证法假设u中存在a-外部申请者与岗位阻塞对(A2,P3),根 据IFS算法,A2曾向满足23≤丌的岗位P发出过申请,并且(P)≠A2 在匹配过程中,当(P川<Q1,并且1(42)=0时,由性质2可知r23>7,显然,与定义6中的条件 1)2=0矛盾;当1(P川<Q并且(42)≠0时,不妨设1(42)=P,若23<h3≤0,A2先于P向 P发出申请,由H(P1)≠A2可知,P在未满额的情况下,拒丝了42,根据IES算法的Step5(1)可知,此 时n2>σ,显然,与定义6中的条件2)矛盾;当|(P)=Q;并且|(42)=0时,由性质2可知,A2的 排序值不小于与P匹配的申请者的排序值,这与定义6中的条件3)721<7和条件472<72矛盾;当 u(P)=Q,并且|(42)≠0时,P在满额的情况下,拒绝∫42,根据LES算法的Step5(2)(i)可知,对 V4∈p(P),有?≤73,与定义6中的条件5)>3或条件6)m>r3矛盾因此,匹配方案中不 含有σ-外部申请者与岗位阻塞对 同理可证定义5中的三个条件皆不成立,即匹配方案中不含有-岗位占有者与岗位阻塞对 定理5I-ES算法获得的匹配方苿中当岗位对岗位占有者与外部申请者的排序值相同时,岗位占有者与 外部申请者相比享有优先权 证明设彐4k∈A1,343∈A2,BP,P∈P,Tk=r!,b=123.采用反证法假设岗位占有者不享 有优先权.即存在如下情形:(P)=A2≠4k 根据IES算法,当b4=形2时,由Ah首先向岗位P发出申请 由(P)≠A,说明P拒绝了A不失一般性,不妨设P在接受水表1岗位占有者和外部申请者对 平为a时拒绝A选择了A4∈A=A1UA2,则说明<mk但是,最 岗位给出的偏好序列表 终由于(P)=A2≠A2,说明P拒绝了A选择了更偏好的A3,即 1f213P4576 A521347 12<r<rk2显然,与已知条件rk=7矛盾,故定理5成立 A12527314 5实例分析 A1154237 A2465132 某汽车制造公司拟在6个岗位{P1,P2,P3,P4,P5,P6}上进行招2172534 聘,人力资源部门根据收到的简历对岗位占有者和外部申请者进行了初42614253 步的筛选,通过笔试进行筛选后最终确定12个有效的申请者{41,A12 A3137542 41,42,4,42,4,43,43,41,4,43},其中,Ah1和42来自于岗位42 A2774231 742315 P,A1和Al2来自于岗位P2.该公司此次招聘计划招聘人数为10人,A3721374 Q1=2,Q2=3,Q3=1,Q4=1,Q5=2,Q6=1.岗位和申请者根据自1534271 身的要求和兴趣爱好等对另一匹配主体给出偏好序信息.申请者对岗位4217347 给出的序值和岗位对申请者给出的序值,分别如表1,表2所示 根据表1和表2,采用IES算法,得到最优匹配方案,具体的过程如表3所示 依据IES算法,获得的最终匹配方案为μ={(41,P3),(A2,P2),(41,P1),(2,P6),(A2,P),(A42, P4),(43,P2).(43,B),(A2,P2),(A,P}外部申请者Az和瑤未实现匹配 从表3可以看出,42与A2都向P发出了申请,并且r2=r,然而p(P6)=42,即岗位P6在面临 外部中请者与岗位占有者一样好时,选择了岗位占有者,这与定理5的结论是一致的 第5期 姜艳萍,等:岗位存在占有者条件下人岗双边匹配IES算法 1201 表2岗位对岗位占有者和外部申请者给出的偏好序列表 A2A 2 1 A P 1 276 P24 213810 135 19521 4438154 A88773 114217 627 21310 P 5463 3 4 13 8513 表3I-PS算法的迭代过程 接受水平申请者发出的请求 被拒绝的申请者 当前匹配结果 退出匹配的申请者 =141:P 3,4112 A (A11,P3) A1 P 4b1:P1.P a=2A2:P4,P6;A2:P1,P Ab (A1,P3),(A12P2),(A21,P) (2P),(A,P1) 42:P2,P4 A2: P, P, P6 (A1,P3),(A123P2),(A1,P) σ=343:B,P,P2 (42,P),(A,n1),(A2,P) A2:P6,P4 (43,P2) A4: P6, P4, P5, P3 A3:3,P3,P4,P2; 42:P2,P4,P6; (41,P3),(412,P2),(412,P) 4 A: P3, P2, PA A2:A2 (A2,P6),(A,P1),(A2,P4) A台:P3,P2,P4,F6 (43,P2),(A3,P5)、(A2,P2 A:P,P4,P2,P3; (4,B A:P2,P1,P4,P5 为了进一步地说明IES算法对申请者和岗位而言更公平,下面将匹配方案H1与运用经典HR算法2 获得的匹配方案进行对比分析.需要说明的是,μ1是由申请者向岗位发出申请得到的匹配方案,因此在与文 献凹2]的方法进行对比时,同样地由申请者向岗位发出请求.运用HR算法,所得的中请者占优的稳定匹配 方案为p2={(4H1,P3),(412,P5),(A2,P1),(A2,P4),(42,P,(42,P2),(A3,P0),(43,P3),(A,P2),(4, P2)}外部申请者4和4未实现匹配将1与2进行比较,比较结果如图1和图2所示 申请者4 与岗位4 给出的 丰请者 申请者 的平均 匹配的 排序值 岗位的 排序值 42442444AAA ●-匹配方案1 一匹配方案P2 匹配方案H1一暑一匹配方案P 图1申请者所匹配的岗位的排序值对比分析图 图2岗位所匹配的申请者的平均排序值对比分析图 由图1和图2可以看出,I-FS算法获得的匹配方案中,闵位与申请者的匹配对象都在对方偏好列表的前 四位,这与定理2的结论是一致的经典HR算法获得的匹配方案中,由图1可以看出,大部分的申请者都 匹配到了其最偏好的岗位,但由图2可以看出,匹配方案A2中有二分之一的岗位所匹配的申请者的平均排 序值都大于匹配方案p1.此外,匹配方案p2的折线图与匹配方案p1的折线图相比起伏更大,说明对某些 岗位而言与其匹配的申请者排序值是比较靠后的.由于不同岗位间的匹配对象相差较大,很容易使岗位认为 此次分配不公平,导致岗位放弃当前的匹配结果.而采用本文方法获得的匹配方案中,岗位与中请者的四配 对象在他们煸好列表中的排序值大小相近,而且在中所有形成匹配对的申请者和岗位的序值差的总和是 12的二分之一.显然,与p2相比μ1中申请者与岗位的匹配对象排序值差别更小,这使得双方更容易接受对 方,从而便得匹配双方更容易接受匹配方案p1 1202 系统工程理论与实践 第38卷 6结束语 本文针对部分闵位存在占有者的人岗双边匹配问题,给出个体理性匹配方案的定义,在此基础上给出了 岗位存在占有者的稳定匹配方案的定义,弥补了以往人岗双边匹配中只考虑外部中请者与岗位匹配的不足 进一步地.为了避免只考虑稳定性造成的匹配方案仅对一方匹配主体而言最优而对另一方匹配主体较差的情 况,增加了对双方匹配主体的公平性的考虑,提出了I-ES算法.与已有的研究成果相比,本文提出的方法考 虑了同时存在岗位占有者与外部申请者时的人员与岗位匹配,兼顾了“稳定性”和“公平性”两种要求,弥补 了以往研究成果单纯考虑稳定性的不足,使得关于人岗双边匹配问题的研究更贴近现实需求,进一步完善了 人岗双边匹配问题的理论与方法.值得指出的是,本文提出的I-FS算法,还为解决其他双边匹配问题,如: 手房交易匹配问题,大学生转专业的匹配问题等,提供了理论与方法上的借鉴下一步研究的重点是考动 态情形下的人岗双边匹配问题利考虑防操纵性的人岗双边匹配问题 叁考文献 1 Gale D, Shapley L S College admissions and the stability of marriage J. The American Mathematical Monthly, 1962,69(1):915 2 Roth A E. Common and conflicting interests in two-sided matching markets[J]. European Economic Review, 1985,27(1):7596 3 Argoneto P, Renna P Capacity sharing in a network of enterprises using the Gale-Shapley model[J. The Inter national Journal of Advanced Manufacturing Technology, 2013, 69 (5-8): 1907-1916 4 Cechlarova K, Fleiner T, Manlove D F, et al. Stable matchings of teachers to schools[J. Theoretical Computer Science,2016,653:15-25 5 Hamada K, Iwama K, Miyazaki S. The hospitals/residents problem with lower quotas[J. Algorithmica, 2016 74(1):440-465 6 Bando K. a modified deferred acceptance algorithm for many-to-one matching markets with externalties among firms[J. Journal of Mathematical Economics, 2014, 52(5): 173-181 7 Diamantoudi E, Miyagawa E, Xue L. Decentralized matching: 'The role of commitment[J]. Games economic Behavior,2015,92(4):117 P, Egesdal M, Pycia M, et aL. Manipulability of stable MechanismS J. AImericall EcOllOInic Journal Microeconomics, 2016, 8(2): 202-214 9 Eirinakis P, Magos D, Mourtos I Blockers and antiblockers of stable matchingsJ. Theoretical Computer Science 2014,524(C):126-133 10林杨,王应明.考虑直觉模糊偏好关系的双边稳定匹配及应用可J].控制与决策,2015,30(12):2212-2218 Lin Y, Wang Y M. Bilateral stable matching considering intuitionistic fuzzy preference relations and their appli- cationJ. Control and Decision, 2015, 30(12 ): 2212-2218 1]李铭洋,樊治平.考虑双方主体心理行为的稳定双边匹配方法[].系统工程理论与实践,2014,34(10):2591-2599 Li M Y, Fan Z P. Method for stable two-sided matching considering psychological behavior of agents on both sides[J. Systems Engineering- Theory Practice, 2014, 34(10): 2591-2599 12乐琦,樊治平.基于不完全序值信息的双边匹配决策方法J.管理科学学报,2015,18(2):22-35 Yue Q, Fan Z P. Decision method for two-sided matching based on incomplete ordinal number information[ Journal of management Sciences in China, 2015, 18(2): 22-35 13胡雅妮.浅谈民耆企业的员工招聘问题J经耆管理者,2017,2(5):172-173 Hu Y N. Discussion on the recruitment of employees in private enterprises[J. Manager Journal, 2017, 2(5) 172173 14 Lazarova E, Borm P, Estevez-Fernandez A. Transfers and exchange-stability in two-sided matching problems Theory and Decision, 2016, 81(1):53-71 [15 Tomas A P Weak stable matchings with tenants and ties[J]. Proceedings of CSCLP, 2006, 27(4): 255-264 16 Mcdermid E, IrvingR W. Sex-equal stable matchings: Complexity and exact algorithms[J. Algorithmica, 2011 68(3):545-570 [17 Romero-Medina A Sex-equal stable matching [J]. Theory and Decision, 2001, 50(3): 197-212 18]姜艳萍,梁海明.基于偏奷序的抗操作和抗自亏双边匹配方法[·系统工程理论与实践,2016,36(2):473-483. Jiang Y P, Liang H M. Strategy proof and self-deprecating proof two-sided matching method based on preference orderingJ. Systems Engineering Theory Practice, 2016, 36(2): 473-483

...展开详情
试读 10P 论文研究-岗位存在占有者条件下人岗双边匹配I-ES算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-岗位存在占有者条件下人岗双边匹配I-ES算法.pdf 50积分/C币 立即下载
    1/10
    论文研究-岗位存在占有者条件下人岗双边匹配I-ES算法.pdf第1页
    论文研究-岗位存在占有者条件下人岗双边匹配I-ES算法.pdf第2页
    论文研究-岗位存在占有者条件下人岗双边匹配I-ES算法.pdf第3页

    试读已结束,剩余7页未读...

    50积分/C币 立即下载 >