多目标最短时限指派问题的算法论文

标准指派问题只要求使得总时间最少。但实际很多指派问题既要求总时间最少, 还要求在最短时间内完成。这类问题被称为最短时限指派问题, 如抢险 (抢修) 任务的指派问题等。目前, 对它的研究较少且主要是研究单目标问题, 常用算法有简算法[1]、最短时限逼近法[2]等。本文研究的是多目标问题, 给出了在简算法的基础上通过对匈牙利算法中寻找独立零元素的次序进行改进的新算法。

一、多目标最短时限指派问题的数学模型

多目标最短时限指派问题:设有n项工作指派给n个人去做, 要求一人一事且一事一个。已知第i人做第j项工作的时间为cij, 如何分配工作, 才能使在最短时间内完成任务的前提下使总时间最少。令决策变量xi j=1, 第i人去做工作j;否则xij=0。则其数学模型为:

二、多目标最短时限指派问题的求解

(一) 多目标最短时限指派问题的转化

首先考虑目标函数 (1) , 再考虑目标函数 (2) 。假设 (1) 的最优解为F, 则多目标规划模型 (1) ~ (3) 可以转化为如下的单目标模型:

(二) 算法思想及步骤

简算法是求解单目标最短时限的算法, 它可求出完成任务的最短时限, 但却不一定使时间总和达到最优。本算法的思想为:首先找到指派的最短时限, 即目标 (1) 的最优解F1, 则C中一定存在n个独立且不大于F1的元素, 故只要它们的和最小即可。步骤如下:

Step2将时间矩阵C中不大于F1的元素全部变为0, 并记为矩阵C (F1) 。

Step3若矩阵C (F1) 中某行 (列) 中的零元素既行独立, 又列独立, 则选中它, 并划掉它所在的行和列。若C (F1) 中某列 (行) 存在多个独立零, 则在它们的行 (列) 中找出各自的次小元素, 选中次小值最大的行 (列) 中的独立零, 划掉它所在的行和列。若上述情况不止一种, 则优先分配次小元素最大的行或列中的独立零。若C (F1) 中所有的行 (列) 都无独立零元素, 则任意选出零元素最少的行 (列) 中的一个零 (多数礼让少数) 。

Step4如选中n个独立零元素, 则令它们对应的变量为1, 其它变量为0, 即得最优指派解;否则, 转Step5。

三、算例

例已知某多目标最短时限指派问题的时间矩阵为:

解由Step1得, F1=18。将C中不大于F1的元素全部变为0, 得矩阵

可见只选中了3个独立零元素, 故转Step5。计算得F2=19, 同理得矩阵

显然, 已找到该指派问题的最优解, 相应的F=19, Z=70。通过比较发现, 本算法所用总时间比文献[1]要少个单位, 本算法的计算结果与文献[3]一致, 且计算要简单得多。

通过比较可知该算法操作简单, 对于小规模指派问题可以手工操作, 对于大规模指派问题可编程实现, 因此具有较强的可操作性和适用性。

摘要：针对最短时限指派问题, 给出了它的多目标线性不可微数学模型, 并给出一种在简算法的基础上通过对匈牙利算法中寻找独立零元素的次序进行改进的新算法。最后给出算例, 验证算法是有效的。

关键词：指派问题,最短时限,多目标

参考文献

[1] 白国仲.线性不可微规划—基于可持续发展的决策技术[M].北京:中国社会科学出版社, 2007.

[2] 夏少刚, 费威.基于最小调整法求解最短时限指派问题[J].数学的实践与认识, 2009, 39 (17) :179-187.

[3] 韩艳娜, 郭东威.多目标线性不可微指派问题的优化算法[J].内蒙古师范大学学报 (自然科学汉文版) , 2017, 46 (3) :325-328, 333.