http://www.paper.edu.cn
- 1 -
用于一般指派问题的禁忌搜索算法
窦晖
兰州交通大学交通运输学院，甘肃兰州 (730070）
E-mail : huihui5027@163.com
摘 要：本文研究了日常生活中常遇到的指派问题，并针对其特点，建立指派问题的数学模
型。运用禁忌搜索算法来求解模型的最优解，通过对具体指派问题算例的仿真实现，说明禁
忌搜索算法是可行和有效的。
关键词：禁忌搜索；指派问题；禁忌表；全局优化
中图分类号：C93
1. 引 言
指派问题是将若干个体分配到若干位置，并求一个线性费用函数的最小值。在生产管理
中，决策者总是希望能够把人员进行最佳分配。由于任务的性质和每个人的知识、能力、经
验等各不相同，各人去完成各项不同任务的效益（所费时间或所花费用）就有差别。那么这
m 项任务究竟该如何分配给 n 个人去完成使最后的总花费最少，所有任务的总效益最大呢？
这就是标准的指派问题。这类问题的效率矩阵中的元素均为确定的量。针对这类组合优化问
题,解决方法可有许多种启发式方法。其中，禁忌搜索(tabu search)是局部领域搜索算法的推
广，是人工智能在组合最优化算法中的一个成功应用，其特点是采用了禁忌技术，能够避免
陷入局部最优，在短时间内找到全局最优解
[1]
。
2. 指派问题描述
在生活中，一般的指派问题是指，有 n 个人，m 项工作（m
≤
n），一个人最多只能干
一项工作，一项工作只能一个人干，找任务的最优分配方案，使总费用最小
[2]
。
一般指派问题可以表示为以下形式的 0-1 整数线性规划问题：
∑∑
==
n
i
m
j
ijij
xc
11
min
(1)
s.t.
mjx
n
i
ij
,,2,1,1
1
L==
∑
=
(2)
nix
m
j
ij
,,2,1,1
1
L=≤
∑
=
(3)
}{
mjnix
ij
,,2,1,,,2,1,1,0 LL ==∈
(4)
nm
≤
(5)
ij
c
——第 i 个人干第
j
项工作的费用
当且仅当
1=
ij
x
时，表示第i 个人被分配做第
j
项工作，否则，
0=
ij
x
。方程(1)即为
目标函数，求最小的费用；方程(2)表示的是每个人只能做一项工作；方程(3)表示的是每项
工作最多由一个人来完成；方程(4)、(5)则表示的是对决策变量的 0-1 整数约束，并说明人
weixin_38685600
- 粉丝: 5
- 资源: 906
我的内容管理
收起
- 我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助
会员权益专享
最新资源
- Xilinx SRIO详解.pptx
- Informatica PowerCenter 10.2 for Centos7.6安装配置说明.pdf
- 现代无线系统射频电路实用设计卷II 英文版.pdf
- 电子产品可靠性设计 自己讲课用的PPT，包括设计方案的可靠性选择，元器件的选择与使用，降额设计，热设计，余度设计，参数优化设计 和 失效分析等
- MPC5744P-DEV-KIT-REVE-QSG.pdf
- 通信原理课程设计报告（ASK FSK PSK Matlab仿真--数字调制技术的仿真实现及性能研究）
- ORIGIN7.0使用说明
- 在VMware Player 3.1.3下安装Redhat Linux详尽步骤
- python学生信息管理系统实现代码
- 西门子MES手册 13 OpcenterEXCR_PortalStudio1_81RB1.pdf
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0