完成有顺序约束的任务指派问题–应用模拟退火算法求解

假设问题：

1、一个企业生产一件产品共有M项任务需要完成，依次记为A、B、C……，任务的完成需要遵循一定的顺序，A任务完成后才能去完成B，B完成后才能去完成C，以此类推。

2、此时有N(N>=M)名员工可以完成这些任务，员工编号依次为1、2、3….，且每个员工只能固定完成一项任务，由于工作能力不同，每名员工完成不同任务耗费的时间不一样，如表1所示。

3、现按任务的顺序为各任务安排合适的员工，各员工按编号从小到大的顺序进行排队，对每一个员工可以做出同意或拒绝的选择，且只有一次机会，当选择同意时，按任务的先后顺序为此员工安排一项任务，当选择拒绝时，此员工离开队伍，后续不能再向其安排任务。

例如：

当前最新任务为A，1号员工到来，拒绝1号完成任务A，1号离开，2号员工到来，接受2号员工完成任务A

当前最新任务变为B，3号员工到来，拒绝3号完成任务B，3号离开，4号员工到来，接受4号员工完成任务B

当前最新任务变为C，5号员工到来，接受5号员工完成任务C

任务已分配完毕

因为条件3的限制，导致表1发生了一些变化，

1号员工不可能分配到任务B、C、…，因为这样就没有员工完成A了，同理有以下限制

2号员工不可能分配到任务C…

4号员工不可能分配到任务A…

5号员工不可能分配到任务A、B…

对于不可能分配到的任务，此员工完成时间记为无穷大，如下表2所示

问如何为每一个任务分配一个员工去，能够达到生产一件产品耗费总时间最小/p>

分析：

理想情况下，应该为每一个任务安排耗时最短的员工完成，可以看到，3号员工完成任务A，4号员工完成任务B，5号员工完成任务C，刚好满足条件，而且完美错开，可以达到总耗时最短的要求，总耗时为16+26+11=53。但是如果错不开怎么办，即某一个员工在完成多件任务都是耗时最短的情况下，就不能这么简单处理了，所以要考虑一般的情况。

一般的，在这个问题中，任务的完成是固定顺序，员工的选择也是从前到后，那么组合的情况就是123、124、134、235等等。可以认为是从5个员工中选3个，然后按顺序排队，依次分配一个任务，可以选择的组合数为

Matlab程序如下：

求出结果如下：

求出结果为3号员工完成任务A，4号员工完成任务B，5号员工完成任务C，此时耗费时间最短，最短时间为53

但是这是数据量比较少的情况，一旦数据增大，就不能再使用遍历了，比如，任务数为27，员工数为35，组合方式就达两千三百万种之多，此时需要寻找一种更好的方法

更一般的，对于一个离散的组合优化问题，可以使用蒙特卡洛加模拟退火算法解决

算法步骤描述如下：

step1：使用蒙特卡洛方法生成随机选择一个最优的组合，作为初始解，并计算初始能量值（目标函数值）

step2：初始化模拟退火算法参数，初始温度T，终止温度e，温度衰减因子alf，马尔科夫链长度L，能量不再降低的次数上限cnt_limit

step3：马尔科夫链长度加1，判断是否达到上限，若是，算法结束，否则，开始step4

step4：当前温度下，在当前解的基础上进行扰动构造一个新解，本文中构造方法为：先将当前解的组合中随机去掉一个员工，再随机添加一个新员工。生成一个新解（一种组合），并计算能量值，即目标函数值（耗费总时间）

step5：计算与前一个解的能量之差

step6：根据能量差判断是否接受新解。若能量差小于0 ，说明新解的能量更低，接受新解；否则 ，说明新解的能量没有下降，以玻尔兹曼概率接受新解。同时记录最优解和对应的最低能量值（最小目标函数值）

step7：判断最低能量值是否保持不变，若是，计数器加1，否则，计数器清0。若计数器到达上限，算法结束。

step8：降低温度，判断温度是否达到下限，若是，算法结束，否则，转向step3

程序如下：

% 文件名：example2.m
% 时间：2020年9月29日
% 作者：乐观的lishan
% 功能：利用模拟退火算法计算有顺序约束的指派问题
clear,close,clc
warning off
tic
 
%数据的生成
M = 27;       %任务数 
N = 35;       %员工数,员工应数大于任务数
lb = 10;      %成本下限
ub = 35;      %成本上限
 
%利用随机数生成代价矩阵
d = unifrnd (lb, ub, M, N);  %生成一个服从均匀分布的矩阵，数值范围[lb,ub]，矩阵大小M×N
d = ceil(d); %朝正无穷大取整

for i = 2:M

    d(i,1:i-1) = inf;
    d(M-i+1,N-(i-1)+1:N) = inf;
end
 
% 保存数据，可用于下一次用相同的数据实验
save data 
 
%运行一次后可将此行上面的所有代码注释，再次运行即可使用相同的数据
load data.mat  
 
%初始化决策变量和函数值，即模拟退火中的状态和内能

S0 = sort(randperm(N,M));    %初始化分配策略，决策变量，即状态
Sum = inf;    %初始化能量，目标函数值
H = 20;       %蒙特卡洛生成组合数次数
%生成初始解，用蒙特卡洛方法随机生成H种组合，并选择其中一个较好的指派组合

for j = 1:H   
     S = sort(randperm(N,M));
     temp = 0; 
     for i = 1:M 
         temp=temp+d(i,S(i)); 
     end 
     if temp 

         S0 = S;
         Sum = temp; 
     end 

end 
%记录蒙特卡洛选优结果
sum = Sum;  
s0 = S0;
 
%模拟退火算法的参数设置
e = 0.1^30; %终止温度
L = 5000;    %Markov链长度
alf = 0.999; %温度衰减因子
T = 1;       %起始温度
cnt_limit = 300;        %最优值连续保持不变的次数上限
 
all_people = 1:N;       %所有元素构成的集合

S0 = s0;
cnt = 0;
 
record_solve(1,:) = S0;
record_value(1,:) = 0;

for i = 1:M

    record_value = record_value + d(i,S0(i));
end
 
%退火过程 

for k=2:L 
    %产生新解 
    original_solve = S0; %保留原解
    remain_people = setdiff(all_people,S0);    %求当前解在所有元素构成的集合中的补集
    index1 = randperm(N-M,1); 
    index2 = randperm(M,1);
    add_num = remain_people(index1);   %随机添加一个新元素
    S0(index2) = [];    %随机删除当前解的一个元素

来源：乐观的lishan
                                                        
声明：本站部分文章及图片转载于互联网，内容版权归原作者所有，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！