当前位置：首页 > news >正文

【车间调度】基于GA/PSO/SA/ACO/TS优化算法的车间调度比较（Matlab代码实现）

news 来源：原创 2024/5/15 12:16:20

1 概述

2 FJSP 描述

3 运行结果

3.1 main1运行结果

3.2 main2运行结果

4 Matlab代码

5 参考文献

6 写在最后

1 概述

柔性作业车间调度问题(Flexible Job shop Sched-uling Problem , FJSP)是在离散制造业和流程工业中应用广泛的一类问题,已被证明是典型的 NP-上hard问题。

FJSP是作业车间调度问题(Job shop Scheduling Prob-lem,JSP)的扩展,FJSP中每个工件的每道工序均可以在可选择的有限台机器上加工,且在每台机器上的加工时间不一定相同,可灵活地进行资源选择,提高调度的敏捷性,更加贴近实际生产。目前元启发式算法是解决FJSP的常用方法,其主要可分为群体智能算法和局部搜索算法。陆家辉等人提出一种混合。
Jaya优化算法求解柔性作业车间调度问题,并设计一种离散化更新算子使Jaya 优化算法更适用于FJSP,混合2种新型邻域结构提高算法的同守儿→军等人[2将化学反应算法与禁忌搜索相结合,设计了4种操作来保证种群多样性,以实现最优的全局探索,加人禁忌搜索提高了混合算法的局部寻优能力。

2 FJSP 描述

FJSP可以按照以下形式进行描述:n个工件(记为J1,J2,…,Ji,…,Jn)在m台机器(记为M1,,M2. ,…,

Mm ）上加工;第 i 个工件 $J_{i}$ 包含 $H_{i}$ 比道工序（各工序依次为 $\left.O_{i, 1}, O_{i, 2}, \cdots, O_{i, h}, \cdots, O_{i, H_{i}}\right), h=1,2, \cdots, H_{i}$ ; 所有工序按照预先确定的顺序加工;每道工序有可选机器集合 $M_{i,h}$ , 加工时间由分配的机器决定。由此, FJSP 实际上是由2 个子问题组成的，即机器选择和工序排序。

此外,FJSP还需满足以下约束。

1 ）同一台机器在同一时刻只能加工一道工序。

2 ）同一工件在同一时刻只能在一台机器上加工。

3 ）所有工件在 0 时刻均可以被加工。

4 ）不同工件工序之间相互独立，同一工件工序之间有先后约束。

5 ）每个工件在加工过程中不能被中断。

6 ）忽略机器准备时间以及工件转运时间。

本文以最大完工时间久皿最小为优化目标 $C_{max}$ ，设 $C_{i}$ 为工件 $J_{i}$ 的完工时间，则目标函数为(公式比较重要，得纯手打）：

$\min C_{\max }=\min \left\{\max _{1 \leqslant i \leqslant n}\left(C_{i}\right)\right\}$

3 运行结果

本文包括五种优化算法进行比较，分别是：遗传算法、粒子群优化算法、模拟退火算法、蚂蚁算法、禁忌搜索算法

3.1 main1运行结果

下面看看运行结果比较：

3.2 main2运行结果

4 Matlab代码

本文仅展现部分代码，全部代码及文章讲解见：

【车间调度】基于GA/PSO/SA/ACO/TS优化算法的车间调度比较（Matlab代码实现）

function [costs, bestSol] = PSO(jobs, m, n, particals, iterations, costFunc)
  c1 = 1.4944;
  c2 = 1.4944;
  w = 0.79;
  gbests = ones(1, n);
  gbest = costFunc(gbests, jobs, m, n);
  lbests = randi(m, particals, n);
  lbest = ones(1, particals);
  costs = ones(iterations, 1);
  costsEnd = 0;
  for i = 1:particals
      lbest(i) = costFunc(lbests(i, :), jobs, m, n);
      if lbest(i) < gbest
          gbest = lbest(i);
          gbests = lbests(i, :);
      end
  end
  x = lbests;
  v = zeros(particals, n);
  
  for i = 1:iterations
      ibest = costFunc(ones(particals, n), jobs, m, n);
      r1 = rand(particals, 1);
      r2 = rand(particals, 1);
      v = w*v + c1 * bsxfun(@times, r1, lbests - x) + ...
        c2 * bsxfun(@times, r2, (bsxfun(@minus, gbests, x)));
      x = round(x + v);
      %x = bsxfun(@mod, x, m) + 1;
      x(x < 1) = 1;
      x(x > m) = m;
      for j = 1:particals
          c = costFunc(x(j, :), jobs, m, n);
          if c < ibest
              ibest = c;
          end
          if c < lbest(j)
              lbest(j) = c;
              lbests(j, :) = x(j, :);
          end
      end
      costsEnd = costsEnd + 1;
      costs(costsEnd) = ibest;
      [ilbest, idx] = min(lbest);
      %ibest
      ilbests = lbests(idx, :);
      if ilbest < gbest
          gbest = ilbest;
          gbests = ilbests;
      end
  end
  bestSol = gbests;
end