一、ジョブショップスケジューリングの概要

ジョブショップスケジューリング問題（JSP）は、NP-hard問題の一つであり、航空母艦のスケジューリング、空港での飛行機のスケジューリング、港湾での貨物船のスケジューリング、自動車製造ラインなど、幅広い分野で応用されています。

JSP問題では、M台のマシンがN個のジョブを処理する必要があります。各ジョブにはL_i個の工程があり、全工程数をLとします。各工程の処理時間は既知で、各ジョブは工程の順序に従って処理されます。スケジューリングの目標は、制約条件を満たしつつ性能指標を最適化することです。

主な制約条件は以下の通りです：

• 各工程は指定されたマシンで処理され、前の工程が完了してから始まる。
• ある時刻において、1台のマシンは1つのジョブしか処理できない。
• 各ジョブは1台のマシンで一度だけ処理される。
• 各ジョブの工程順序と処理時間は既知であり、スケジューリングによって変更されない。

例として、以下のようなジョブがあります：

jop0 = [(0,3), (1,2), (2,2)]
jop1 = [(0,2), (2,1), (1,4)]
jop2 = [(1,4), (2,3)]
  

この例では、jop0は3つの工程を持ち、それぞれの工程は指定されたマシンで指定された時間で処理されます。

二、NSGA-IIアルゴリズムの概要

NSGA-II（Non-dominated Sorting Genetic Algorithm II）は、非支配ソートと遺伝的アルゴリズムを組み合わせた多目的最適化アルゴリズムです。

主要な特徴は以下の通りです：

• 非支配ソート：解の集合を非支配階層に分割する。
• 混雑度：解の密集度を評価し、解の多様性を保つ。
• エリート戦略：現在の世代の最良の解を次の世代に引き継ぐ。

NSGA-IIの主なステップは以下の通りです：

1. 初期種群の生成。
2. 非支配ソートによる階層分け。
3. 混雑度に基づいて解を選択。
4. 交叉と突然変異による新しい種群の生成。
5. エリート戦略による新しい種群の更新。

三、部分的なコード例

以下は、NSGA-IIアルゴリズムの一部のMATLABコードです。

function [p_matrix, m_matrix] = non_domination_sort_mod(pro_matrix, mac_matrix)
  N = size(pro_matrix, 1);
  M = 5; % 最適化目標数
  V = size(pro_matrix, 2) - M; % 決定変数数
  front = 1;
  F(front).f = [];
  individual = [];

  for i = 1:N
      individual(i).n = 0;
      individual(i).p = [];
      for j = 1:N
          dom_less = 0;
          dom_equal = 0;
          dom_more = 0;
          for k = 1:M
              if pro_matrix(i, V + k) < pro_matrix(j, V + k)
                  dom_less = dom_less + 1;
              elseif pro_matrix(i, V + k) == pro_matrix(j, V + k)
                  dom_equal = dom_equal + 1;
              else
                  dom_more = dom_more + 1;
              end
          end
          if dom_less == 0 && dom_equal ~= M
              individual(i).n = individual(i).n + 1;
          elseif dom_more == 0 && dom_equal ~= M
              individual(i).p = [individual(i).p j];
          end
      end
      if individual(i).n == 0
          pro_matrix(i, M + V + 1) = 1;
          F(front).f = [F(front).f i];
      end
  end

  while ~isempty(F(front).f)
      Q = [];
      for i = 1:length(F(front).f)
          if ~isempty(individual(F(front).f(i)).p)
              for j = 1:length(individual(F(front).f(i)).p)
                  individual(individual(F(front).f(i)).p(j)).n = ...
                      individual(individual(F(front).f(i)).p(j)).n - 1;
                  if individual(individual(F(front).f(i)).p(j)).n == 0
                      pro_matrix(individual(F(front).f(i)).p(j), M + V + 1) = ...
                          front + 1;
                      Q = [Q individual(F(front).f(i)).p(j)];
                  end
              end
          end
      end
      front = front + 1;
      F(front).f = Q;
  end

  [~, index_of_fronts] = sort(pro_matrix(:, M + V + 1));
  for i = 1:length(index_of_fronts)
      sorted_based_on_front(i, :) = pro_matrix(index_of_fronts(i), :);
      m_matrix(i, :) = mac_matrix(index_of_fronts(i), :);
  end

  current_index = 0;

  for front = 1:(length(F) - 1)
      distance = 0;
      y = [];
      previous_index = current_index + 1;
      for i = 1:length(F(front).f)
          y(i, :) = sorted_based_on_front(current_index + i, :);
      end
      current_index = current_index + i;
      sorted_based_on_objective = [];
      for i = 1:M
          [~, index_of_objectives] = sort(y(:, V + i));
          for j = 1:length(index_of_objectives)
              sorted_based_on_objective(j, :) = y(index_of_objectives(j), :);
          end
          f_max = sorted_based_on_objective(length(index_of_objectives), V + i);
          f_min = sorted_based_on_objective(1, V + i);
          y(index_of_objectives(length(index_of_objectives)), M + V + 1 + i) = inf;
          y(index_of_objectives(1), M + V + 1 + i) = inf;
          for j = 2:length(index_of_objectives) - 1
              next_obj = sorted_based_on_objective(j + 1, V + i);
              previous_obj = sorted_based_on_objective(j - 1, V + i);
              if f_max - f_min == 0
                  y(index_of_objectives(j), M + V + 1 + i) = inf;
              else
                  y(index_of_objectives(j), M + V + 1 + i) = ...
                      (next_obj - previous_obj) / (f_max - f_min);
              end
          end
      end
      distance(:, 1) = zeros(length(F(front).f), 1);
      for i = 1:M
          distance(:, 1) = distance(:, 1) + y(:, M + V + 1 + i);
      end
      y(:, M + V + 2) = distance;
      y = y(:, 1:M + V + 2);
      p_matrix(previous_index:current_index, :) = y;
  end
end