政策指派

政策指派（精选7篇）

政策指派 篇1

在经济学领域,宏观政策实施一直以来都是一个讨论的话题,政策调控应该对经济周期做出的反应吗?经济学界对这样的问题总是有不同的声音,一部分学者认为经济运行过程中的不均衡是常态,在各种不同需求和供给的冲击下,政策调控能起到稳定器的作用,这是凯恩斯及其追随者的主要观点,就是在这个观点下,也有不同见解。时至今日供给学派的拉弗仍对2008年的沃尔森(Paulson)7000亿的救助计划持否定意见,认为保尔森做出的是典型的恐慌型的决定,其影响是恶劣的。而另一部分研究者认为,宏观经济本来就是稳定的,政策调控不仅不能起到稳定作用,反而成为新的波动根源。无论如何,政策调控对宏观经济的影响力总是不容忽视的,而且政策调控本身也使市场能更加有效的进行资源配置。

一、浅析非均衡与政策搭配

从整个经济周期来看,经济体系一直处于均衡到非均衡再到初始均衡,或者均衡到非均衡再到新均衡的反复运动之中,非均衡在普遍意义上更是一种“常态”。在非均衡状态下,政策搭配是其重要推动力,这就使得政策搭配能够起到三个重要作用:一是让经济“非均衡”状态的偏离程度变小,趋于可接受范围。第二点是让经济体系从一个第二优的“均衡状态”迅速趋向于另一个相对较优的“新均衡状态”,如果没有宏观调控政策搭配,就算市场能够自发出现,在市场发现到识别的阶段也需要时间,市场能不能承受也是一个问题。三是让经济体系从一个维持的“均衡状态”趋向于另一个“新均衡状态”。

在非均衡的理念上寻求,如何进行政策搭配?是一个新的视角,以前的论文从均衡的角度出发,探究如搭配经济政策是经济体从非均衡走向均衡,该文则是从反面来思考问题。从理论发展脉络看,米德(1951),丁伯根(1952),蒙代尔(1968)都对这一问题做出自己的回答。米德的理论贡献在于研究了不同经济目标之间的关联性,并在“米德冲突”的基础上强调了政策搭配的重要作用。计量经济学家丁伯根通过构造“丁伯根决策”模型说明了政策目标和政策工具之间的数量关系,蒙代尔(1968)的研究也给出了一个答案,他提出“蒙代尔政策指派法则”,也被称为有效市场分类法则。蒙代尔根据比较优势原理指派各种政策工具,他认为政策制定者应该了解每种政策工具对每种政策目标的影响方向和效用大小,将每个政策工具指派给其最大效用的政策目标,合理搭配。但是市场中存在信息不对称,政策滞后,遵循“蒙代尔政策指法则”的政策制定者只能采取“走走停停的调整策略,逐步趋向最终均衡”,在具体政策指派规则上,用财政政策来达到内部均衡,用货币政策来达到外部均衡。米德、丁伯根和蒙代尔都开创和发展了传统凯恩斯主义政策搭配,对各国财政当局和货币当局的政策制定者,提供了理论依据。

二、我国非均衡的视角下的政策搭配分析

本节将就2005年~2015年中国政策搭配的整体动态演进进行简单概括,然后就四个阶段的宏观背景,政策搭配和阶段评价展开具体论述。在这10年中,中国政策搭配的波动性不断减小,稳健性不断增强,多样性不断丰富,宏观调控日趋成熟,随着人民币加入SDR,政策搭配对外部均衡的关注远远高于对的关注内部均衡,没有达到“双向指派法则”的现实要求。

1.2008年~2010年阶段分析

(1)宏观背景分析。中国经济正处在一个调整期,经济总体态势总体比较好,高增长、低通胀,就业增长。经济总量运行也是平稳的。目前,没有出现增速大幅回落的趋向。当前的宏观政策,既要注意投资反弹,也要关注回落过快,打击投资者信心,信心比黄金重要,从经济总体形势看,中国经济将继续保持高经济增长,CPI指数上升控制在2%以下,通胀压力也不是很大。同时实现的实际GDP以11%增长速度。

(2)政策搭配。这一阶段政策搭配的总体特征是“双向互补”,积极的财政政策为内需不足的市场经济输入了增长动力,加大了各方投资的力度,尤其调动积极性,为经济注入活力,再加上市场经济改革的步伐加快,相应的制度做配套。同时,稳健偏松的货币政策在刺激经济增长的同时为物价稳定和外部均衡提供保障,增加了流动性。

2.2008年~2010年的阶段分析

(1)宏观背景。2008年初,中国经济已连续多年以高于10%的速度增长,可谓是创造了世界增长奇迹,经济增长由偏快转为过热,通胀压力上升。国外次贷危机爆发,形势错综复杂。我国居民消费价格总水平同比上涨5.9%,比2007年高出0.9个百分点。2009年CPI同比累计下降0.7%,产能过剩矛盾加剧影响全年CPI。2009年国际、国内经济与市场环境对价格上涨形成较大的抑制作用。

(2)政策搭配。在该阶段实行适度宽松的货币政策,为银行体系注入了更多的流动性,保持信贷量的合理增长,加大了金融对实体经济的支持力度。随着经济形势的变化,我国的货币政策发生了由“从紧”到“灵活审慎”再到“适度宽松”的转变。年初“从紧”的货币政策对于抑制通货膨胀、防止经济过热发挥了重要作用,也为我国应对国际金融危机的冲击奠定了基础。

3.2010年~2013年的阶段分析

(1)宏观背景。2010年1月份以后我国物价再度出现持续上涨,2011年CPI涨幅达到5.1%。在该阶段物价上涨特点明显:一是食品与非食品价格同步,但幅度不是很大。在本轮物价上涨过程中,食品价格上涨有力的推升物价上涨的。二是食品价格季节性回调幅度已不是那么明显,重要原因是季节性的蔬菜、水果等农副产品季节回调幅度明显缩小,2013年GDP总额近25万亿元,同比增长7.6%;6月CPI同比增长2.7%,PPI同比下降2.7%,出口同比大降3.1%,经济有复苏的取向。

(2)政策搭配。在适度宽松货币政策和抑制通胀之间寻找新的平衡,一方面,实体经济需要增加更多的流动性和降息来减轻企业融资成本,鼓励企业投资,是实现复苏的重要一步,另一方面,在全球流动性加大,央行继续降息、继续加大市场中的流动性,这会加大未来通胀压力,中国货币政策面临严重挑战,既要保持增长,又要控制通胀。因此,一是要采取措施进一步加大货币政策的放松力度,寻求适当宽松货币政策与稳增长、控制通货膨胀之间的平衡。适度控制现金和短期贷款,可以制物价上涨幅度。首先需要控制交易性货币供给增长速度。但是降低短期贷款会给企业造成企业资金短缺的局面。

4.2014年~2015年的阶段分析

(1)宏观背景。GDP增速等宏观参数在外需疲软、内需持续回落、房地产周期性调整等力量的作用下持续回落;另一方面,经济结构在消费升级、不平衡逆转,以及政策调整的作用下出现较大幅度的调整,结构参数的良性调整、总体价格水平保持相对稳定以及就业状况的持续稳定,给2014年的宏观经济增加了亮色。

(2)政策搭配。中国整体性通货紧缩的压力加大,“强监管”+“定向宽松的货币政策”+“积极的财政政策”+“常态化的微刺激”在2015年进一步实施。

参考文献

[1]赵丽芬,李玉山.我国财政货币政策作用关系实证研究[J].财经研究,2006,(2).

[2]钱颖一.理解现代经济学[J].经济社会体制比较,2002,(2).

指派问题的EXCEL求解模板 篇2

在管理实践中经常会遇到这样一种问题:有n个人(P1,P2,……,Pn)需要完成m项任务(T1,T2,……,Tm),简单指派问题是m=n,即n项任务恰好有n个人可以分别去完成[1]。扩展指派问题可以是m=n,也可以是m≠n,即每项任务或交给一人,或由几人去完成;每人或完成一项任务,或完成几项任务[2]。为此在分配过程中要充分考虑个人的知识、能力、经验等因素,同时也要考虑任务的难度、重要性、风险等因素,如何分配才能使工作效率最高或消耗的资源最小?这类问题就属于指派问题。

指派问题是线性规划中的特殊形式,匈牙利数学家克尼格(Konig)提出了命名为匈牙利法手工计算方法,但计算量相当大。采用单纯法可以运用计算机的相关软件进行求解,相比之下,微软Office办公软件Excel内置的“规划求解”功能的操作更为简便,且应用广泛[3]。本文在Excel规划求解功能的基础上,通过对单元格函数程序的编制,形成指派问题的标准化求解模板,达到智能化求解指派任务的目的。

二、简单指派问题求解模板的编制和应用举例

简单指派问题是m=n,即n项任务恰好有n个人可以分别去完成,每个人只能完成一项任务,每项任务只能由一个人完成,不同人完成不同任务的效率是不同的,指派的目标是寻求效率最高的分配方案。一个n≤14的简单指派问题Excel求解模板如图1。

1、简单指派问题的求解模板单元格的函数公式[4]

指派问题求解模板的界面分为“工作效率表”和“任务安排解表”两部分。“工作效率表”处于模板的上半部,主要用于输入不同人员承担不同任务的效率,另输入每项任务安排的人数和每人安排任务的数量。“任务安排解表”位于模板的下半部,主要用于读出最优的任务指派方案和最优指派方案下的累计得分。

(1)求解模板中单元格名称的输入

人员单元格C3:C16的编号:依次输入序号P1~P14。任务单元格D2:Q2的编号:依次输入序号T1~T14。另在单元格R2内输入“任务量”,单元格C17内输入“安排人数”。

单元格C2内设置斜线,并输入“人员任务”。在单元格B2内输入“工作效率表”,然后选中B2:B17,点击菜单工具“合并及居中”,合并B2:B16。

在单元格B19内输入“任务安排解表”,然后选中B19:B30,点击菜单工具“合并及居中”,合并B19:B30。单元格B31内输入“得分累计”,并选中B31:B33,点击“合并及居中”,合并B31:B33。

单元格C19内输入引用函数公式:=C2。复制单元格C19,粘贴到单元格D19:R19和单元格C20:C34,引用人员任务编号。

选中单元格B2:R17和单元格B19:R34,设置单元格边框中所有边框,并适当调整单元格的大小和单元格格式,最终得到图1的简单指派问题求解模板的界面。

(2)任务安排表中各单元格函数公式的编制

在任务安排表中,单元格R20内输入人员P1任务量总和的计算公式:

将该单元格用复制粘贴的方法将公式粘贴到单元格R21:R33,得到所有人员任务量总和的计算公式。在单元格D34内输入任务T1安排人数总和的计算公式:

同样将该单元格用复制粘贴的方法粘贴到单元格E34:Q34,得到所有任务量总和的计算公式。任务安排表中累计得分是在单元格B34内输入函数公式:

该公式是任务安排表中单元格D20:Q33的值与各工作效率表中单元格D3:Q16的值的乘积之和,从而求得累计得分。

2、规划求解对话框设置

(1)“规划求解参数”对话框设置

通过菜单“工具”/“规划求解”,打开“规划求解参数”对话框如图2所示。设置目标

单元格的地址是:B34。等于选项组中选择是:最大值。可变单元格选项区域中设置的地址是;D20:Q33。约束选项区域中设置的地址是:

D17:Q17=D34:Q34

D20:Q33=整数

R3:R16=R20:R33。

(2)“规划求解选项”对话框设置

在“规划求解参数”对话框的右侧的一列按钮,单击“选项”按钮,打开“规划求解选项”对话框,可以选中“采用线性模型”、“假定非负”复选框并设置一系列计算精度的参数如图3。然后单击“确定”按钮,返回“规划求解参数”对话框;单击“关闭”按钮,退出规划求解对话框设置。并保存该Excel文件作为“简单任务指派”求解模板。

3、简单指派问题应用实例

例1,某办公室有4名员工可以被指派去完成4项任务,这4名员工以前都负责过这4项工作,并且得到了相应的评分。每名员工完成不同任务的评分见表1。

办公室主任希望找到累计评分为最大的任务指派方案。

求解过程:

(1)打开保存的任务指派求解模板,在求解模板上半部的工作效率表部分输入相关的工作评分,在各位员工对应的任务量栏内输入任务量为“1”,在各任务对应的安排人数行内输入安排人数为“1”,完成输入后的工作效率表如图4;

(2)点击“工具”菜单,选择“规划求解”,在图2所示的“规划求解参数”对话框内点击“求解”按钮,程序自动进行规划问题的求解,并显示“规划求解结果”对话框如图5;

(3)在图5所示的“规划求解结果”对话框内点击“确定”按钮,得到的最优解表如图6所示。即职员P1安排工作T1,职员P2安排工作T4,职员P3安排工作T3,职员P4安排工作T2。累计总得分为369分。

三、扩展指派问题的Excel求解

1、扩展指派问题求解模板函数公式的编制

扩展指派问题求解模板可以计算人员数量和任务数量相等或不相等指派问题。实际工作中往往会出现人员的数量和任务的数量可能会不一致,为此可以通过调整每个人员可安排任务的数量,或者调整每项任务可安排的人数,或者将不能安排的人员和不能安排的任务作为冗员和冗事暂时搁置,等待下次安排。在Excel求解模板上,为了达到智能调整的目的,扩展指派问题求解模板通过修改简单指派问题最后一个人员任务量的单元格为“冗事”单元格,修改最后一项任务安排人数单元格为“冗员”单元格,并编制这两个单元格的函数公式。为此可以对上一节简单指派问题的求解模板作一些修改,将工作效率表中Q2单元格的名称由“T14”改为“冗员”,将C16单元格的名称由“P14”改为“冗事”,修改后对应的引用单元格Q19和C33自动发生引用变化。修改后扩展指派问题求解模板的部分单元格如图7。调整发收不平衡的方式是在单元格Q17内输入函数公式;

用以计算多余人员作为冗员。在单元格R16内输入公式

用以计算多余任务作为冗事。保存该文件作为扩展指派问题求解模板。

由于设置了冗员和冗事,当人员数和任务量不一致时,冗员和冗事起到了调整作用;当人员数和任务量一致时,冗员和冗事的值均为零,因此扩展指派问题求解模板可用于求解任意任务指派问题。

2、应用实例

例2如果在例1中,员工P3准备去进修,而员工P1和P4能力较强,可以安排两项工作,在只有3位员工并且可以完成5项任务的情况下,这4项任务如何安排才能使累计评分最大。

求解过程:

在扩展指派问题求解模板的工作效率表中输入相关的工作评分,并输入每名员工可承担的任务量和每项任务需要安排的人数。由于可完成任务量超过任务需要安排人数,所以有员工可以安排的工作没有得到满足,因此在工作效率表中重新输入每名员工的任务量后,模板自动计算生成冗员数为“1”,然后按例1的步骤(2)、(3)完成规划求解的计算,得到全部的计算如图8。

求解后得到的安排是:员工P1承担工作T1和工作T3的任务,员工P2承担工作T4的任务,员工P3准备去进修不承担任务,员工P4可承担的两项工作只能满足一项,仅承担工作T2的任务,另一工作任务的余量只能作为冗余暂时保留。

四、结语

很多决策过程都会产生指派问题;典型的指派问题有:将工作分配给机器或人,对代理分配任务。将销售人员分配给销售区域,将合同分配给投标人,等等。引入任务指派的求解模板,可有效帮助日常决策过程中的最优化问题,包括指派后达到目标最大化的问题,也包括指派后的目标最小化的问题。建立科学的指派方法,也促进了组织建立一些科学管理制度,如本文的最优人事安排,可以有效地促进组织在管理工作中,建立起对员工工作能力的培训、评价和考核制度,形成对员工工作能力管理的制度性文件。

参考文献

[1]杜红.应用运筹学[M].浙江:浙江大学出版社,2010:P86-92.

[2](美)安德森(Anderson,D.R.)等著;侯文华等译.数据、模型与决策:管理科学篇(原书第12版)[M].北京:机械工业出版社,2009:P167-170.

[3]孙爱萍,王瑞梅.如何利用EXCEL求解线性规划问题及其灵敏度分析[J].办公自动化:2009,11:44-46.

指派问题的一种特殊解法 篇3

指派问题是在日常生产或工作中经常遇到的问题。指派问题通常是指这样的问题:某单位需完成n项任务, 恰好有n个人可承担这项任务, 由于每个人的专长不同, 个人完成任务不同 (或所费时间) , 效率也不同, 于是产生应指派哪个人去完成哪项任务, 使完成n项任务的总效率最高 (或所需总时间最小) 。指派问题是0-1规划的特例, 也是运输问题的特例, 可用整数规划、0-1规划或运输问题的解法去求解, 但这就如同用单纯形法求解运输问题一样不合算。库恩 (w.w.kuhn) 于1955年提出了指派问题的经典解法———匈牙利法, 然而这种方法仍旧存在诸多弊端。1985年, 陈坚苏先生注意到国内几部著作介绍的匈牙利方法计算程序在计算某些特例时存在死循环, 而且在匈牙利法的步骤3变换系数矩阵时, 我们是在未被直线覆盖的元素中找出一个最小元, 对未被直线覆盖的元素所在行 (或列) 中各元素都减去这一最小元素。这样, 在未被直线覆盖的元素中必会出现零元素, 但同时却又使已被直线覆盖的元素中出现负元。为消除负元素, 再对它们所在列 (行) 中各元素都加上这一最小元素, 从而使所得新系数矩阵既把原矩阵中未被直线覆盖的元素中的最小元素变为零, 又保证了新系数矩阵没有负元素, 但每执行一次步骤3, 系数矩阵中虽至少增加一个新的0, 却不能保证变换后的新系数矩阵中独立零元素的个数也会增加, 从而导致迭代次数较多。而伏格尔法 (vogel) 则避免了这些缺陷, 以下给出了伏格尔法改进后解决最优指派的一种新方法[4,7]。

1 新算法

就我们通常遇到的求解指派问题时, 大多是求其最少或最小值, 而很少遇到如何分配, 才能获得最多或数量最多的问题, 这类问题用匈牙利法不易求出结果, 以下给出求解这类问题的一种特殊算法, 其基本步骤为:

步骤1:用伏格尔法确定一个初始可行解。在 (n×n) 人员任务平衡表上给出n个数字格。若求解的是最优指派问题的最小值, 则空格的检验数全为非负数时, 初始解已为最优解;当表中空格出现负检验数时, 则未达到最优解, 若有两个或两个以上的负检验数, 一般选其中最小的负检验数进行调整, 转步骤2, 若求解的是最优指派问题的最大值, 则空格的检验数全为非正数时, 初始解即为最优解;若空格中出现正的检验数, 则未达到最优解, 若有两个或两个以上正的检验数, 一般选其中最小的检验数进行调整, 转步骤2;

步骤2:在求解最优指派问题的最大 (小) 值时, 如果遇到步骤1的情况, 则采用闭矩阵调整法, 将选取的最小正 (负) 检验数所在空格与其数字格对调, 对调后再算出新的检验数, 若全为负 (正) , 则取最大 (小) 值, 否则重复步骤2;直到得出最优结果为止。

2 新算法应用

例1酋长嫁女儿问题

问题提出:非洲某酋长国的酋长想把自己的3个女儿嫁出去, 记他的3个女儿为A, B, C, 现设恰有3位求婚者, 记他们为X, Y, Z (这是标准形式, 在一般模型中女儿数与求婚人数可以不同) , 每位求婚者对为A, B, C愿意支付的财礼数视其喜欢程度的不同而不同, 设此问题所满足的关系矩阵为:

矩阵中的元素Cij为求婚者i娶j愿付的财礼数。

问:酋长应如何嫁女儿才能获得最多的财礼 (从总体上讲, 他的女婿最喜欢他的女儿) 。

解: (1) 方法一

我们用匈牙利法[3,5,6,8]来求解。写出系数矩阵Cij, i, j=1, 2, 3, 选取每行 (列) 元素的最大值, 用该行的每个元素减去该行的最大元素, 得到含零元素的新矩阵, 若每行或列都有零元素, 则标出独立零元素, 否则选取非零列 (行) 的最大值, 用每列 (行) 中的元素减去该列 (行) 的最大元, 得到一个每行 (列) 都含零元素的新矩阵, 确定独立零元素, 从而得出最优解。即:

从而最优指派为A→Y, B→Z, C→X, 酋长得到的财礼数为27+4+26=57。

(2) 方法二

借鉴模糊数学中隶属函数的思想[2], 先计算出Cij中每列元素的和, 记, 1≤j≤n;令隶属矩阵;从B中选取最大值可得到对应关系, 然后划去其所在的行 (列) , 得到矩阵B', 用同样的方法又可得到一个对应关系, 如此下去, 则可得出最优指派。即:

从而得到对应关系A→Y, 划去所在的行和列, 则有, 选出其中的最大元素, 得到对应关系C→X, 从而得到最优指派A→Y, B→Z, C→X, 酋长得到财礼数为27+4+26=57。

(3) 方法三

用上述介绍的伏格尔法的特殊方法来解。先确定初始可行解, 在系数矩阵中分别计算出各行和各列的最小值和次最小值之间的差额, 从行或列的差额中选出最大者, 选择它所在行列的最大元素, 则可得到一个对应关系;将选出的行和列的数字划去, 得到新的系数矩阵, 重复上述方式得到新的对应关系, 直到给出初始解为止。此题给出初始解如下:

用 (i, j) 表示在i行j列的格, Xij取数值1的格为数字格, Xij取数值0的格为空格。

检验数σij= (+1) ×Cij+ (-1) ×Cik+ (+1) ×Cik+ (-1) ×Cij;其中Cij, Cik, Cikj, Cij为效率, 空格的效率前乘以 (+1) , 数字格的效率前乘以 (-1) 。此题空格的检验数为:

此题求的是最优问题的最大值, 选取检验数中正数的最小值构成闭矩形回路, 然后调整数字格和空格的位置。即将 (1, 3) , (2, 1) 和 (1, 1) , (2, 3) 对调, 有:

经检验, 此解已为最优解, 从而最优指派为A→Y, B→Z, C→X;酋长得到的财礼数为27+4+26=57。

由上述例题可知, 改进后的伏格尔法和用匈牙利法与隶属矩阵法所求结果完全一样, 但我们知道, 对很多具体的指派问题, 匈牙利法进入死循环时无法求出其最优解, 而隶属矩阵法过程过于繁复, 且对信息重复问题, 隶属矩阵法无法找到最优解, 如该方法不能解决公路网规划评价指标间相互造成的重复问题, 此时我们考虑用伏格尔法求其最优解。

例2[1]采用C60火车运输压实的草捆, C60火车长×宽×高尺寸为12920×2820×3300mm3, 限高4800mm, 扣除车厢底高度1147mm, 可装货物极限高度4800-1147=3653mm, 预留大约353mm装货空间, 可装货物高度3300mm, 草捆尺寸为700×460×360mm3, 草捆在车厢中摆放方式不一样, 装载数量就不一样。

问:如何摆放能使车厢装载草捆数量最多? (图一为草捆装车摆放示意图, 不考虑混排情况)

解:这是讨论如何摆放货物能充分利用运输设备的装车空间, 使装载量达到最大, 以充分利用运载能力的工程实际问题, 不考虑混排情况下可归为0-1整数规划问题进行优化求解, 将火车各方向尺寸分别除以草捆各方向尺寸, 有:

由于装车时只能少装而不能多装, 草捆为整数, 所以余数舍去。

优化装车方案, 数据如下:

下用改进的伏格尔方法来求解, 在上述指派问题的效率矩阵上分别计算出各行和各列的最低效率和次最低效率的差额;从行 (列) 差额中选出最大者, 选择它所在行 (列) 中的最大元素, 划去该元素所在的行和列, 相应的决策变量的解Xij的值为1;在剩余的行和列的缩减效率矩阵中重复上述步骤, 直到全部的行和列划完而在表中添满n个1给出初始解为止。检验初始解是否为最优解, 若检验数全为非正数, 则为最优, 否则采用闭合矩阵调整法, 选取检验数中正值最小的一个进行对调, 重复上述步骤, 直到得出最优解为止。, 得到一个对应关系700→12920, 算出行和列最小值和次最小值的差额, 选出其中行 (列) 的最大值, 有, 又得到一个对应关系360→3300, 剩余460→2820, 则有:

σij为检验数,

选取其中检验数正值的最小值, 后用闭矩阵回路法调整, 即 (1, 2) , (2, 1) 与 (1, 1, ) , (2, 2, ) 对调, 有:

检验数中有正数, 再进行迭代, 有:

经检验, 检验数均为非正数, 从而迭代终止, 然而此目标函数与常规的整数规划形式有所不同, 该题中参变量为乘积形式, 从而我们选取初始解乘积和迭代过程中各可行解乘积的最大值作为其最优解, 故有:

从而最优解Z=28×9×4=1008, C360火车最多装载草捆1008捆。摆放方案为:草捆的宽度尺寸4600mm摆放在火车长度方向上, 草捆的长度尺寸700mm摆放在火车的宽度方向上, 草捆的高度尺寸叠放在火车装车的高度方向上。

3 结束语

本文给出了新的求解指派问题中最优解的新方法, 并将其应用到两个算例中, 由结果可以看出, 此方法解决了一般的伏格尔法未曾解决的一些问题, 针对求解指派问题中最大值的问题给出了特殊的解法, 为更好的求解指派问题提供了新的方向。

参考文献

[1]胡运权.运筹学教程[M].北京:清华大学出版社, 1998.

[2]赵洪刚, 杨竹君, 孟庆华, 等.指派问题新解法——目标值子矩阵法[J].浙江大学学报 (理学版) , 2010, 37 (05) :501-504.

[3]周素琴.指派问题的新算法[J].上海师范大学学报 (自然科学版) , 1997, 26 (02) :38-42.

[4]叶微, 申卯兴, 高歆, 等.求解指派问题的伏格尔方法[J].陕西师范大学学报 (自然科学版) , 2003, 31 (02) :25-28.

[5]原野, 王洪志, 王春华.关于指派问题的一种特殊解法[J].煤矿现代化, 2004, (06) :50-52.

[6]李月秋, 杨雅琴, 刘文奇.最优指派问题的一种新方法[J].高师理科学刊, 2008, 28 (02) :15-17.

[7]高兴佑, 张向辉.一种基于伏格尔法的指派问题新算法[J].曲靖师范学院学报, 2008, 27 (03) :12-14.

战损装备抢修任务指派模型研究 篇4

信息条件下的高技术局部战争装备保障具有全局性、分布性的特点。为了使整个装备维修保障系统能够高效、协调的运行，装备保障指挥控制系统必须能够灵活、快速、高效、合理地分配维修任务。尤其是在战时，战争进行激烈，装备损坏严重，维修任务大，而可用机动维修力量又十分有限的条件下，维修力量派遣的“优化”问题就显得更加重要，有必要对维修力量的指派问题建立一种模型。

传统的战场抢修任务指派模型：

其中，cij≥0表示第i个人完成第j项任务时的效率（所费时间或成本等），把目标函数的系数矩阵C=(cij)n×n称为指派问题的效率矩阵。匈牙利法是求解传统指派问题的有效方法之一。

1 战场抢修任务指派的数学模型描述

1.1 任务需求

战役级维修机动小组作用就是在一定的作战要求下，对所属战役军团中的部队维修进行加强支援，从而满足作战指挥部门的要求。某战役级维修机构有m个维修机动小组，现要完成n项紧急程度不同的任务，己知维修机动小组维修保障能力不尽相同，第i个小组完成第j项任务的效率为cij,cij≥0，当cij=∞时，表示第i个小组没有能力完成第j项任务，如何进行维修任务指派，才能使完成n项任务的总效率达到最高（维修总时间最少）。

设决策变量：

效率矩阵C,

式中：Ji表示第i项任务的紧急程度。

1.2 紧急程度

将紧急程度划分3个等级，具体的含义如表1所示。

1.3 指派策略

实战中，战损装备的抢修主要依赖于两个方面：一是战场情况、紧急程度、装备受损情况和维修器材保障等；一是应急机动保障力量、维修人员素质，以及指挥员的决心。一般来说，战损装备抢修任务指派策略是，应急机动装备维修小组根据紧急程度高低的任务进行抢修，只要有抢修任务，已完成任务的小组就应立刻接受新的任务。

1.4 模型描述

对n项紧急程度不同的任务进行分类统计，非常紧急类（Ji=1）任务L1个，紧急类（Ji=2）任务L2个，一般类（Ji=3）任务n-(L1+L2）个；令C1,C2和C3分别为这三类任务的效率矩阵，对n项紧急程度不同任务的指派模型：

1.5 模型求解

1.5.1 非常紧急类（Ji=1）任务指派模型求解

将（3）式效率矩阵中紧急程度Ji=1的列提出来，若有L1个，分别记录项目编号，m个维修小组对这L1个紧急任务进行指派。这样构成一个非常紧急类任务的效率矩阵C1=(C1)(m×L1）。

指派模型：(7)

1.5.2 紧急类（Ji=2）任务指派模型求解

将（3）式效率矩阵中紧急程度Ji=1的列提出来，然后在m行中划去己经分配非常紧急任务的L1个维修小组，这样形成一个紧急类效率矩阵C2=(C2)(m-L1）×L2

指派模型：(9)

1.5.3 一般类（Ji=3）任务指派模型求解

将（3）式效率矩阵中紧急程度Ji=2的列提出来，然后在m行中划去己经分配非常紧急任务L1个维修小组和紧急任务的L2个维修小组，这样形成一个一般类效率矩阵C3=(C2)(m-L1-L2）×L3

指派模型：(11)

对f1,f2和f3模型求解。

2 结束语

战损装备的应急抢修应依据战场情况、紧急程度、装备受损情况、维修器材保障、应急机动保障力量和维修人员素质等因素，由指挥员决定应急机动装备维修小组的派遣。在实战中，经常会出现非常紧急的任务，针对这些不同紧急程度的抢修任务，指挥员要做出正确的决策。

参考文献

[1]何坚勇.运筹学基础[M].北京:清华人学出版社,2000.

[2]苏祥定,孙桐,马霖.不平衡指派问题的差额法求解及其应用[J].计算机工程,2005(11):178-179.

[3]张芳玉,高崎,何鹏等.战时装备维修任务指派模型及算法研究[J].运筹与管理,2006(2):62-66.

[4]自国仲,苏芳荔等.基于特殊需要的指派问题[J].华中师范大学学(自然科学版)2006(9):305-309.

政策指派 篇5

指派问题是一种特殊的0-1整数规划问题，目前对于小规模指派问题，匈牙利法是一种常用的简单有效的解决方式；而对于大规模指派问题，则因为计算量过大，因而运算较为困难。基于生物群体遗传进化操作的遗传算法，则很适合群体规模较大问题的优化处理。因此将规模较大的指派问题应用遗传算法进行求解，就会较为简便快捷。

1 遗传算法

1.1 遗传算法简介

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法[1], 它是一种多学科融合交叉的产物。遗传算法通过合理的编码机制和进化机制, 广泛应用于近似最优化、生产调度、图形分割及自动控制等领域。

1.2 遗传算法基本步骤[2]

(1) 初始化。设置初始种群、最大迭代次数及迭代计数器。

(2) 适应度评价。对当前种群计算其个体适应度。

(3) 进化操作。主要是通过选择、交叉、变异、倒位等算子作用产生下一代群体。

(4) 终止条件判断。如果已经求得最优解，则终止；否则重复以上两个步骤。

2 指派问题的遗传算法实现

2.1 指派问题模型描述

人们日常生活和工作中，经常会遇到这类问题：有n个任务需要n个人去完成，每个人完成每个任务的效率不尽相同，要求一个人只能完成其中一个任务，一个任务只能由一个人完成。要求合理分配之后，所达到的总体效率最好，这就是指派问题。

那么，根据优化模型理论，当目标为极大值时，指派问题的数学模型[3]如下：

其中，当指派第i个人去完成第j个任务时，xij=1；否则xij=0。cij表示第i个人去完成第j个任务的效率；约束条件（2）表示：第i个人只能完成一项任务；约束条件（3）表示：第j个任务只能由一个人完成。

2.2 指派问题的遗传算法设计

遗传算法[4]设计是完成遗传运算的具体方法，涵盖了决策变量的基因型与表现型之间的编码和解码，个体适应度函数构造，遗传算子构建，控制参数设置等过程。

2.2.1 指派问题适应度函数

针对指派问题在求解目标函数为极大值时的情况和考虑指派问题可行解的非负性前提下，其个体适应度与目标函数值是成正比。因此，指派问题的适应度函数构建为如下所示：

其中，xij表示第i个人是否去做第j个任务。cij表示第i个人完成第j个任务的效率。

F越大，表示个体适应度越好，其可行解越好，能够以较大概率遗传到下一代。当F取值最大时，则表示已经达到最优解。

2.2.2 指派问题染色体编码

染色体[5]编码质量是影响遗传算法计算效率和准确度的重要因素。考虑到指派问题的特殊约束性质：即每人只能完成其中一个任务且每个任务只能由一人完成。针对决策变量xij的取值，其基因型编码不采取通常的0-1二进制编码，而采用常用的十进制编码。并且，每个基因块只有两个基因位，分别表示决策变量的行下标取值和列下标取值。当问题规模为n时，则指派问题决策变量染色体编码表示为：

在这种染色体编码十进制表示方式下，对于每个个体，其染色体的n个基因块在处理时按照如下规则进行：

(1) 各代群体每个染色体中各基因块第一位分别赋予固定值：范围为0到n-1，即R11=0, R21=1，…Rn1=n-1。其目的是保证决策变量选取位于不同行。

(2) 各代群体每个染色体中各基因块第二位分别赋予无重复随机值：范围为0到n-1，即R12、R22…Rn2每次取0到n-1的随机全排列值。目的是保证决策变量选取位于不同列。

通过这种方式进行指派问题染色体编码，可以只对基因块中第二位编码进行随机产生，提高了搜索效率。同时，由于是十进制编码，各个基因块的值组合可以直接定位于效率矩阵中的对应元素位置，加快运算效率。

2.2.3 指派问题遗传算子改进策略

一般情况下，遗传算法遗传过程和进化过程主要是通过选择、交叉、变异及倒位等遗传算子组合运算完成群体迭代。考虑指派问题组合优化的特殊性：即可行解必须位于不同行不同列，已在决策变量染色体编码中进行了约束限制，那么，在遗传进化过程中，无需再对种群群体进行变异操作和倒位操作。

因此，通过优化染色体编码，在遗传进化过程中仅通过选择和交叉策略实现种群迭代，有效地提高了运算效率，加快了最优解的获得。

3 算法仿真

控制参数的设置是否合理对于遗传算法而言，关系到其优化效率。在此，我们设置种群规模为80；交叉概率为Pc=0.6，各基因块位置不变的情况随机配对基因块第二位（此时也就相当于包含了变异运算）；选择运算根据目标极大化特点，采用轮盘赌[6]策略进行优化选择。

仿真验证时，我们只需输入效率矩阵阶数和对应效率矩阵的各个元素值则可获得最优解。

假设效率矩阵阶数为5，对应的效率矩阵如下所示：

经过运算之后得到的最优解为[0:2------1:1------2:3------3:0------4:4]，其适应度为F=77。

4 结束语

在指派问题中，对于阶数越高的效率矩阵而言，运用此改进的遗传算法进行求解，效果越明显，效率也越高。如果目标函数是极小值情况，只要通过函数变换，转化为极大值则可。通过仿真验证，这种通过优化染色体编码和减少遗传算子作用相结合的改进策略，对于大规模指派问题求解十分有效。

参考文献

[1]周明, 孙树栋.遗传算法原理及应用, 北京:国防工业出版社, 1999, 6.

[2]张权, 修宏伟.遗传算法在指派问题中的应用, 沈阳建筑工程学院院报, 1997, 13 (1) .

[3]李德, 钱颂迪.运筹学, 北京:清华大学出版社, 1982, 4.

[4]Hplland J H.Adpation in Natural and Artifical systems.AnnArbor:University of Michigan Press, 1975.

[5]Davis L.Handbook of Genetic Algorithms, New York:VanNostrand Reinhold, 1991.

基于指派模型的人岗匹配问题研究 篇6

关键词：人岗匹配,效益最大化,指派模型

0前言

杰克·韦尔奇说：，“用人之道，其精髓就是将合适的人放在合适的位置上，使其长处得以发挥，短处得以克服。这样个人和组织都能得到持续的发展。”对人岗匹配问题进行研究，使得“用人所长”、“人尽其才”，将为企业吸引、发展和保留人才，增强企业核心能力发挥重要作用。而我国目前人力资源配置仍处在观念导入阶段，岗位设置主要是依靠管理者的经验与主观判断，缺乏科学合理的量化管理，不能将合适的人才安排到合适的岗位，结果导致人浮于事、效率低下等现象时有发生，严重影响了企业的生存和发展[1]。因此，建立一个科学透明，客观公正的评判方法保证企业员工与岗位合理适配，是人力资源管理亟待解决的问题。

目前国内外人与岗位匹配研究主要集中在概念、原理和实现方法等方面。对人与岗位匹配的测算方法，国内外学者也进行了相关研究。在国内，李耘涛和赵涛运用360度模糊综合评价模型对人力资源岗位匹配度进行定量研究：孔庆如和李小平以概率分析为基础，提出了基于概率分布特征的岗位配置与调度优化方法[2]。但大多数研究只是从理论和人工算法上对人岗匹配问题进行分析，缺乏科学的测评工具，从而导致匹配可操作性不强。因此，本文在以往研究基础上，结合计算机软件，为人岗匹配提供有效的决策依据。

1 人岗匹配的数学模型

在人力资源管理过程中经常会遇到这样的问题企业人力资源部门要指派不同员工到不同岗位工作，经考核这些员工在不同岗位上工作效率或成本有所不同，作为人力资源部门经理应如何根据企业需要，指派适当的员工到适当的岗位上工作,最大限度地利用企业现有人力资源,使企业以最小成本获得最大经济效益[3]。这就是基于指派问题的人岗匹配问题。

假定有n个员工Pi(i=1,2，…，n）,m个岗位Sj(j=1,2，…，m），并满足以下条件：(1)每个员工只能分配一个岗位；(2)xij=1时，表示指派第i个员工到第j个岗位，否则xij=0；(3)cij是第i个员工在第j个岗位上的效率（或成本）（cij≥0），对应的矩阵为[cij]；(4)k=max(n,m），当员工数目n大于岗位数m时，k=n，虚拟k-m个岗位，对应的效率为零，否则虚拟k-n个员工，对应的效率为零。当目标是求成本最小时，对应的成本取无穷大。则人岗匹配数学模型如下：

在进行人岗匹配的过程中，人力资源部门还可以考虑出勤率、工作差错率等其他单项指标，建立以上数学模型，归结为有m项工作安排n个人去做的最优指派问题。对于此类模型,求解的基本思想是将问题转化为能够用匈牙利算法求解的AP模型,然后用匈牙利算法求解。但是，匈牙利算法由于可操作性不强等缺点一直不被企业采用。事实上，采用Win QSB计算机软件同样可以求解此类模型。而且比匈牙利算法更科学、更具有可操作性。

2 人岗匹配数学模型的优化

以上模型只是在假设每个员工有且仅有一个岗位的基础上建立的岗位指派模型，但通常在分配岗位的过程中，经常会出现某些员工因为某些限制条件（例如没有取得职业资格证）而不能在某些岗位工作，这样就必须还要考虑员工的专业素质等限制性条件。这就是有限制条件的人岗匹配的优化模型[4]。

假设员工Pi由于限制条件不能在岗位Sj上工作，其他假设条件不变。此时需要令员工Pi的工作效率cij为零（或工作成本无穷大）。目标仍然是使企业总效率最高(或成本最小)。优化后数学模型可以归结为有限制条件下的最优指派问题,同样可以用“匈牙利算法”来求解。

在进行人岗匹配的过程中，人力资源部门通常需要考虑的并非是某一种指标，还需要综合考虑员工绩效、成本、工作差错率等多项指标，此时可以引入权重wi进行求解。假设有m个指标，有：

其数学模型如下：

其中：cij表示效益、效率等正相关指标时取正数，表示成本、耗时等负相关指标时取负数。该模型综合考虑了多种指标，各个指标权重wi大小可以通过专家经验来设置，也可以通过问卷调查的方式确定。

3 应用实例

某企业的人力资源部门经理根据企业需要，指派5位员工到5个不同的岗位上工作，经过考核得知，各员工对应各岗位的成本与绩效（百分制）如表1所示。问该企业人力资源部门经理如何配置这5位员工，使企业以最小的成本获得最大的经济效益。

由于该企业只考虑绩效和成本两个指标，并通过专家经验设置绩效权重为70%，则相应成本权重为30%。进行简单代数运算，用绩效权重的70%减去成本权重的30%后，得到表2所列的综合考核成绩。

目标函数为：

约束条件为：

其中xij=1或0;

通过WinQSB计算机软件求解，结果如表3所列。

由Win QSB求解结果可以看出，安排甲在E岗位工作，乙在C岗位工作，丙在A岗位工作，丁在D岗位工作，戊在B岗位工作，能实现最佳的人岗匹配。

4 结论

本文在单目标人岗指派模型基础上，建立的多指标人岗指派模型，具有公开、公正、科学等特点，可应用于指导企业各部门的人员配备，为公司创造更大的效益。同时，运用指派模型结合企业关键测评指标可以保证企业员工与岗位达到最佳动态匹配状态。但是，该模型要求企业对每个员工的多项指标进行考核，会耗费较多人力和物力。因此，对于这样的人员指派问题采用本方法会给科学的人岗匹配带来一定的困难，这些都有待于进一步的研究。

参考文献

[1]袁有明:《人力资源管理中的人岗匹配问题》[J];《市场周刊》2008(9):140-141。

[2]付继娟:《人与岗位匹配的国内外研究综述》[J];《武汉职业技术学院学报,2004,(2):41-43

[3]熊伟:《运筹学》[M];机械工业出版社,2005:112-116。

政策指派 篇7

Kozan[1]运用启发式算法研究集装箱码头集卡运输问题,并讨论影响集装箱码头作业效率的因素。集卡路径规划问题类似于VRP问题[2,3,4],杨静蕾[5]以集卡行走路径最短为目标建立集装箱码头物流路径优化模型,但没有考虑船舶装卸顺序约束等条件。计明军与靳志宏[6]提出了时间最短的集卡线路优化模型,并采用进化规划算法进行求解。针对同样的问题,李磊[7]采用免疫禁忌搜索算法求解,并比较分析了不同调度模式对集卡行走路径的影响。王军等[8]在不同船舶装船作业和卸船作业同时进行的前提下进行集卡调度,考虑岸桥与场桥作业时间,建立了以完工时间最短为目标的模型,并进行了数值仿真。魏宏磊与朱瑾[9]建立了基于船舶装卸协同作业的集卡路径优化模型,应用分支定界法得到了进口集装箱在堆场的分配方案及集卡的最优路径。为了进一步提高效率,集卡调度向更加动态的方向发展。Nishimura等[10]在对比集卡静态调度与动态调度的基础上建立了集卡动态路径优化模型,并采用遗传算法求解。严政等[11]对集卡的传统调度模式和集卡动态优化组合调度模式进行对比,采用基于模糊决策的算法求解该问题。曾庆成等[12]提出了基于装卸动态作业的集卡混合调度模型,设计两阶段禁忌搜索算法求解模型。李广儒等[13]分析了整个码头作业面的动态调度方案,运用码头GPRS系统,提出了一种集卡动态调度路径的自适应蚁群算法。

纵观国内外有关集装箱码头水平运输设备的研究,均未考虑岸桥装卸作业模式对集卡配置与调度问题的影响,且在研究中预先设定了装/卸船的集装箱提取/堆存箱区,与码头实务稍有不符。本文则从码头实务作业出发,在船舶靠泊进行装卸作业时,依照不同的装卸作业模式,对比不同的箱区提取/堆存原则,针对往返岸边与堆场间的集卡予以装卸任务的指派,通过降低岸桥装卸完工时间,达到缩短船舶在港时间的目的。

1 问题描述与建模

1.1 问题描述与假设

集装箱码头装卸作业系统包括岸桥装卸、集卡载运、堆场内集装箱存取三个子过程,因此,排定岸桥的装卸顺序、合理配置集卡的数量并优化其运输路径,以及科学调度场桥的存取移动作业是提高码头装卸作业系统效率的关键。

目前码头实务中普遍采用“全卸全装”“依舱位先卸后装”“同步装卸”三种装卸作业模式。“全卸全装”是最常见的装卸作业模式,此方式是指先将船上所有进口或转运集装箱卸载,再装载欲上船的出口或转运集装箱。“依舱位先卸后装”是指岸桥将船上同一舱位的装卸作业完成后,方可移至下一邻近舱位继续进行装卸作业,直至该岸桥负责的所有舱位作业完毕为止。一般枢纽港的大型集装箱船舶因装卸量较大,通常都采用此种作业方式。以上两种装卸作业模式,在岸桥的运作上,必有一趟为空载状态,“同步装卸”则是利用岸桥完成一次卸箱后,随即进行一次装箱动作,之后在一卸一装、一装一卸动作的工作循环中不断反复。就集卡而言,在“同步装卸”下,必须配合装卸作业的需求,调度将更加复杂,目前只有少数欧洲码头采取此种作业模式。

集卡的主要任务是进行岸桥与堆场之间的集装箱载运。集卡对于岸边集装箱的装卸操作,不外乎是空车或装载两种状态,因此根据两个连续作业可能的基本模式,可分为四种衔接模式:卸箱与卸箱衔接,卸箱与装箱衔接,装箱与卸箱衔接,及装箱与装箱衔接。以一辆集卡为例,上述三种装卸作业模式对应的集卡运作特点如图1所示。

以国内北方某集装箱港口为例,在已知岸桥装卸作业顺序及堆场箱区容量的前提下,针对不同的装卸作业模式,对衔接岸桥与堆场箱区的集卡予以装卸任务的指派,探讨集卡的最优配置数量与路径规划问题。

本文数学模型的建立基于以下假设条件:

1岸桥在船边贝位间的移动速度已知。

(2)岸桥由船上待卸船的集装箱所在位置,将其吊起并移动,直至放置在集卡上的时间,与由集卡上吊运待装船的集装箱,直至放置在船上所需的时间,相等且为已知的定值。

(3)仅考虑一台岸桥的装卸作业情况。

(4)集卡载运进口箱至箱区堆放,或至箱区提取出口箱时场桥作业时间随机产生,但其最快与最慢作业时间为已知。

(5)为避免场内交通混乱,集卡在堆场内遵循统一的绕行方向。

6计划期开始时,所有集卡均处于空载状态。

7为不失一般性,所有集卡行驶速度相同。

1.2 数学模型

以最小化集装箱装卸作业完工时间为目标,考虑了以下两种问题的特性,建立非线性整数规划模型。

集合:

C:待装卸的集装箱的集合,c∈{1,2,…,|C|},C =D ∪L.

D:待卸船的集装箱的集合。

L:待装船的集装箱的集合。

K:集卡的集合,k∈{1,2,…,|K|}。

S:堆存待装船集装箱及可堆存卸船集装箱的箱区的集合,s∈{1,2,…,|S|}。

Cs:箱区s堆存待作业集装箱的集合。

Sc:可堆存第c个集装箱的箱区的集合。

其他参数:

Us:箱区s可堆存集装箱的数量。

TGs:集卡由岸边行驶至箱区s所需的时间。

TRs:集卡由箱区s行驶至岸边所需的时间。

TSs′s:集卡由箱区s′ 行驶至箱区s所需的时间。

TEc′c:第c′ 个集装箱作业完毕后,紧接着作业第c个集装箱的集卡空驶时间。

TFc:第c个集装箱在集卡上的运输时间。

TCc:岸桥处理第c个集装箱时产生的集卡等待时间。

TSc:场桥处理第c个集装箱时产生的集卡等待时间。

Tkc:集卡k完成第c个集装箱所需时间。

决策变量:

xkc:若第c个集装箱指派给集卡k,则为1;否则为0。

ysc:若第c个集装箱堆存在箱区s,则为1;否则为0。

zkc′c:若集卡k完成第c′个集装箱作业后,继续完成第c个集装箱作业,则为1;否则为0。

目标函数:

约束条件:

将所有集装箱的装卸任务指派给集卡后,求解每辆集卡完成任务的时间,由于集卡完成最后装卸任务的最大时间为所有任务的完工时间,故目标函数式(1)是最小化最大完工时间。式(2)约束每一个集装箱只能指派给一辆集卡。式(3)约束每一个集装箱只能存在于一个箱区。式(4)为箱区容量限制,也即堆放到某箱区集装箱的总数不能超过该箱区可存放集装箱的数量。式(5)为集卡执行任务的顺序限制。若第c个集装箱指派给集卡k ,则对于集卡k而言,必定负责执行过第0个至第c-1个集装箱中的某一装卸任务。式(6)表示执行集装箱装卸任务时,集装箱在集卡上的运输时间。式(6-1)表示对进口箱而言,运输时间为集卡由岸边行驶至堆存箱区的时间;式(6-2)表示对出口箱而言,运输时间为集卡由堆存箱区行驶至岸边的时间。式(7)表示执行集装箱装卸任务时,集卡的空驶时间。式(7-1)表示若先后作业两个出口箱,则空驶时间为集卡由岸边行驶至后一个出口箱所在箱区的时间;式(7-2)表示若先后作业两个进口箱,则空驶时间为集卡由前一个进口箱所在箱区行驶至岸边的时间;式(7-3)表示若先作业一个出口箱,后作业一个进口箱,则空驶时间为0;式(7-4)表示若先作业一个进口箱,后作业一个出口箱,则空驶时间为由进口箱所在箱区至出口箱所在箱区的行驶时间。式(8)为求解集卡任务完成时间的递推关系式。各项含义分别为:集卡完成前一项任务的时间、为执行此任务空车的行驶时间、集装箱在集卡上的运输时间、执行此任务时集卡在箱区的等待时间、执行此任务时集卡在岸边的等待时间。式(9)、式(10)、式(11)为决策变量取值约束。式(12)、式(13)、式(14)为参数取值约束。

2 算法设计

2.1 启发式规则概述

上述数学模型为非线性整数规划问题,属于典型的NP-hard问题,求解理论最优解是无法实现的。而运用传统优化算法很难顺利求解,因此设计了启发式算法进行求解。

本文研究的问题可分解为以下两个子问题:首先,确定进口箱卸船堆存或出口箱装船提取的箱区位置,其次,分配集卡进行集装箱的载运,并对集卡进行任务排序及运输路径规划。

本文采用以下四种原则进行集装箱任务的箱区指派,并分别进行求解与比较。在这些不同的指派原则下,其“距离”包括两种含义:一种指该集装箱由船边卸下至堆存区域的距离,一种指该集装箱由原堆放箱区至岸边装船的距离。

(1)“由近至远”:由该箱次可能堆存或提取的箱区中,选择距离最近,且符合箱区容量限制的区域予以指派。

(2)“由远至近”:由该箱次可能堆存或提取的箱区中,选择距离最远,且符合箱区容量限制的区域予以指派。

(3)“一远一近”:就所有集装箱可能堆存或提取的箱区中,依次以最远与最近的距离进行交叉混合指派。

(4)“随机选取”:就所有集装箱可能堆存或提取的箱区中,以随机选取的方式依次进行指派。

然而,无论采取何种分配原则,均应满足箱区容量限制。若某箱区容量已达上限,即使该箱区为某规则下最优的存取位置,也仅能舍弃该箱区而在尚可存取的其他次优箱区中进行选择。

当箱区分配确定后,即可根据集装箱作业先后顺序,对集卡进行集装箱及运输任务指派。由于集卡载运过程中时间与空间的差异性,需进一步确定指派原则:

(1)先到先指派原则

针对某一装卸任务,以最快完成前项任务返回至起始位置的集卡为指派对象。对于进口箱而言,起始位置指岸边;对于出口箱而言,起始位置则是提箱箱区。若在同一时间点,有多辆集卡抵达起始位置,则选择累计服务时间较短的为指派对象,以均衡车次作业量。

(2)岸桥作业顺序优先原则

虽然岸桥以“先到先服务”的原则服务于集卡,但仍需按预先排定的装卸顺序执行作业。也即若前项任务尚未完成,即使负责此项任务的集卡已到达岸边,该集卡仍需等待。

2.2 算法描述

为清晰地表述本文设计的启发式算法,现引入以下符号:

n:待装卸集装箱的数量。

i:岸桥作业集装箱的顺序编号,i∈{1,2,…,n}。

j:堆场箱区编号。

k:集卡编号。

q:集卡由当前任务的完成位置行驶至i的起始位置所需的时间,也即前述模型中的TEc′c.

p:集卡服务于i的时间,也即前述模型中TFc、TCc与TSc三者之和。

r:由作业开始至集卡完成当前任务时的总耗时,也即前述模型中的Tck.

算法步骤如下:

Step 1:输入岸桥作业顺序、岸边与箱区的距离等信息,i←1,j←1,转至Step 2。

Step 2:为i分配箱区,转至Step 3。

Step 3:判断i是否等于n,若相等,则执行Step 4;否则,i←i+1,返回Step 2。

Step 4:i←1,转至Step 5。

Step 5:为i指派集卡,转至Step 6。

Step 6:判断i是否等于n,若相等,则算法终止输出分配与指派结果;否则,执行Step 6-1。

Step 6-1:k←1,转至Step 6-2。

Step 6-2:判断q+r是否最小,若是,执行Step 6-4;否泽,执行Step 6-3.

Step 6-3:k←k+1,返回Step 6-2。

Step 6-4:取r最小的指派给i,转至Step 6-5。

Step 6-5:r←r+q+p,转至Step 7。

Step 7:i←i+1,返回Step 6。

算法流程如下图所示。

3 数值实验

运用C++进行算法编写,以Microsoft Visual Studio2008 进行编译,在PC (Intel○R Pentium ○R processor T4200,2.0GHz)上运行。以我国北方某港口集装箱码头堆场为参考,相关参数设置如表1所示。鉴于待求解的为非线性整数规划问题,属于典型的NP-hard问题,加之理论界尚无针对此问题的研究,目前为止并无理论最优解可供对比,故为了验证模型与算法的可行性及实用性,本节设置了4种不同性质的说验,如表2所示,分别针对每一种性质的实验收集码头10个不同的实例运用本文算法进行求解,并与该码头现有操作系统的调度结果进行了对比与分析。

3.1 实验1求解与分析

由码头现有操作系统对实验1的10个实例的处理资料可知,装卸作业模式近乎“全卸全装”,如图3(a)所示,系统自动分配6 辆集卡服务单一岸桥进行装卸作业时,实际平均总完工时间为279分钟。由图3(b)、图3(c)、图3(d)所示可知,采取“由近至远”原则可获得最优的装卸效率,且在此原则下,完工时间对集卡数量的变化最为敏感。

表3显示了码头作业系统及三种装卸作业模式下,岸桥单位时间平均可作业箱量的最大值。综合图3与表3,可知本例中岸桥的平均最大作业效率均在“由近至远”下获得。

3.2 实验2求解与分析

码头资料显示,实验2中的10个实例亦近乎“全卸全装”,由于卸船箱量比重很小,故箱区指派原则并不影响总装卸时间,即使增加集卡数量,效率改善空间仍旧很小。

由图4与表4可知,与实验1类似,本例中卸船箱中无空箱,无需堆存在远离岸边的箱区,故岸桥的最大作业效率亦是在“由近至远”下获得。另外,当集卡配置数量为6辆时,岸桥作业效率基本上达到最大值并趋于稳定,故在码头实务中,若处理类似的作业情形,可将集卡数量控制在5~6辆。

3.3 实验3求解与分析

该实验中,由于卸船集装箱箱量占整个作业箱量的三分之二,且全部为空箱,须运送至远离岸边的空箱区堆存。码头作业系统自动分配6辆集卡进行装卸作业时,实际平均总完工时间为850分钟,如图5(a)所示。在前两种装卸模式下,采用“由近至远”所得的结果明显逊于其他三种原则,如图5(b)、图5(c)所示。由图5(d)可以看出,在“同步装卸”下,完工时间随着集卡数量的增加而大幅度降低。

综合分析图5与表5可知,在前两种作业模式下,采用“由远至近”“一远一近”与“随机选取”的岸桥的平均作业效率基本相同,“由近至远”下的岸桥作业效率最低,而在“同步装卸”下,采用“由近至远”原则时岸桥作业效率却是最高的。

3.4 实验4求解与分析

在码头实务中,约20% 的箱量由于岸边等候而延误的时间为3~10分钟,还出现了10个集装箱等候时间超过10分钟的情况,其中延误最久的长达1个小时,总平均完工时间为1351分钟。

本实验中集装箱装卸数量基本平衡,但由于卸船箱中一部分为空箱,故求解“先卸后装”下的完工时间曲线具有与实验3相似的特征,如图6(b)、6(c)所示。在“同步装卸”下,平均完工时间随着集卡数量的增加而明显降低,当集卡数量由3辆增加至4辆时,时间降低幅度最大,优化效果最明显,如图6(d)所示。

由表6可知,相比于其他两种装卸模式,当集卡资源充足时,“同步装卸”下岸桥作业效率较高。所以,当岸桥的作业量较大时,码头可考虑采用“同步装卸”的方法以提升机械效率与港口经营效果。

3.5 综合分析

(1)箱区指派原则与集卡数量相关性分析

在实验1与实验2中,由于卸船箱均为重箱,使得箱区间有“卸船—装船”的任务衔接时,集卡绕行同一方向即可完成载运任务,采用“由近至远”原则,平均装卸效率较高。而对于实验3与实验4,折线图反映出完全不同的结果。由于卸船箱中包含大量的空箱,需堆放在远离岸边的空箱区,若采用“由近至远”原则,则集卡绕行时间增长,降低整体作业效率。

(2)装卸作业模式与集卡数量相关性分析

实验1中,在“实际作业”与“全卸全装”模式下,即使集卡数量增加,装卸效率却几乎没有变化;而若采用“同步装卸”模式,则可获得装卸效率较优的结果。实验2 中,“同步装卸”下,随着加快数量的增加,装卸效率提升显著;而“实际作业”与“全卸全装”时,增加集卡数量,装卸效率的提升并不明显。实验3与实验4中,由于箱量较多,导致岸桥于船边等候集卡执行完前项任务返回的时间间隔拉长,故装卸效率相对较低;且在集卡数量较少时,采取“同步装卸”模式的装卸效率较差。

为提升作业效率、缩短船舶在港时间,实务中应考虑采取“同步装卸”作业模式,并在作业开始前,详细规划集卡与箱区的路径衔接以避免集卡行驶路线的紊乱。对于箱区分配原则选择问题,岸桥作业集装箱数量或属性的差异都可能影响其平均效率的表现。一般地,除进口空箱数量较多的情形外,通常采用“由近至远”可以取得较优的作业效率;而当进口空箱较多时,集卡行驶时间将大幅度增加,需根据问题中涉及的集装箱数量而确定采用何种分配原则。对于集卡配置数量问题,码头应慎重权衡运营成本与作业效率的权重,通常以一台岸桥配置4~5辆集卡为宜。

(3)求解时间与集卡、集装箱数量相关性分析

由表7可知,计算机求解时间会随着指派集装箱数量的增加而增加,且当岸桥装卸工作量较大时,平均求解时间也将更长。而在装卸箱量相当的情形下,无关乎其中装、卸箱数量,计算机求解时间并没有太大差异。

4 结语