Job Shop Scheduling (Painting)（ジョブ・ショップ・スケジューリング問題【塗装】）

ジョブ・ショップスケジューリング問題（Shortest Common Supersequence)、日本 (http://0-1integer.co.jp/)　0-1整数inc、提供

複数の色を使用する塗装工程において、Nシートは、一定の順序の複数色によって塗装する必要があります。
1台の塗装機を持っており、その機械における色の交換数を最小にしたい。すなわち、わたしたちはN作業を請け負っており、各作業は塗装作業の連続により生じます。（各々、その色により識別される）
各処理で、機械は同色の塗装作業を無制限に処理することが可能です。（しかし、0-1操作がまだ処理されていない場合、作業の操作0を処理することはできません）
ゴールは全作業の全操作を処理するために必要な、処理の総数を最小化することです。
ひと目で、取られた意思決定は時間処理への作業割当てであることが考えられます。

実際、より簡単なアプローチは各処理で機械により塗装された色のみに注目をおくことで、作業の実行はこの一連の色による結果として生じます。これら色の意思決定変数に基づき、処理kを開始する前に、作業jで実行される次の操作インデックスとして、'progress[j][k]'を導入します。処理kに対し、選択された色に応じて、'progress[j](k+1]'は'progress[j][k]'または'progress[j][k]+1'となります。
操作インデックスを希望色にすぐに変換することを目的とした、簡単な配列の使用法に注目してください。
最終的に、ゴールはただ単に、動的な処理の総数を最小化することです。データファイルは、1つの作業あたり、1行で、一連の作業に対する色を与えるための処理を含みます。
例えば、A,8,6,9,1,8,1,8,5,6,2,2,7,4は、13の連続的な色で構成されている作業名Aということを説明しています。文献では、この問題は最も短いコモン・スーパーシーケンス問題として、知られています。
与えられたワードNは、ワードNのどれでも、文章をWから削除することによって得られるように、ワードWが最も短いということがわかります。ここでは、わたしたちの日本のパートナーが、印刷産業の表現式でこの問題に取り組んでいるため、ジョブショップの定式化としています。
LocalSolverは、より短時間でより良い解を得ることで、このテストケースにおけるこの有効性を完全に証明することができました。例えば、大規模例題（data5.in）でベスト結果として知られている、WCSPテクニックを用いた約1時間のCPUの後に得られた236の結果です。LocalSolverでは、たった1分で210の値に到達すること可能です！

LSP ソースファイル

/********** jobshop_scs.lsp **********/

/* Reads instance data. */
function input() {

  usage = "\nUsage: localsolver multi_color.lsp "
    + "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]\n";

  if (inFileName == nil) error(usage);
  inFile = openRead(inFileName);

  local ii = 1;
  NOCOLOR = -1;
  maxColor=0;        
  while (not(eof(inFile))) {
    str = readln(inFile);    
    if (length(str) > 0) {
      mstr = split(str,",");      
      JobName[ii] = mstr[0];
      local jj = 1;
      Operation[ii][0] = NOCOLOR;
      for[j in 1..count(mstr)-1]{
        local color = toInt(trim(mstr[j]));
        if (color == 0) error("Please use positive integers for color codes");
        if (jj == 1 || color != Operation[ii][jj-1]) { // ignore duplicated colors
          Operation[ii][jj] = color;
          colorUsed[color]=true;          
          if (maxColor < color) maxColor = color;
          jj = jj + 1;
        }
        Operation[ii][jj] = NOCOLOR;
        NumOpe[ii] = count(Operation[ii]) - 2; // the first and last fake operations does not count
      }
      ii = ii + 1;
    }
  }
  
  NumJob = count(JobName);
  println("Number of jobs ="+NumJob);
  TotalNum = sum[i in 1..NumJob](NumOpe[i]);
  
  for[i in 1..NumJob]{
    print("JobName["+i+"]: "+JobName[i]+":"+count(Operation[i])+",");
    for[j in 1..NumOpe[i]] print(" "+Operation[i][j]);
    print("\n");
  }
 
}

/* Declares the optimization model. */
function model() {	
  // 0-1 decisions: 
  // y[k][c] = 1 if the resource paints color c at step k
  y[1..TotalNum][1..maxColor] <- bool();

  for [c in 1..maxColor : colorUsed[c] == nil][k in 1..TotalNum] constraint y[k][c] == 0;  
  for [k in 1..TotalNum] constraint sum[c in 1..maxColor](y[k][c]) == 1;

  // paintingColor[k] = the color painted by the shop at step k
  paintingColor[k in 1..TotalNum] <- sum[c in 1..maxColor](c * y[k][c]);
  
  // progress[j][k] = the index of the next operation to be performed for job j before starting step k
  // expectedColor[j][k] = the color of the next operation to be performed for job j before starting step k
  // match[j][k] = 1 if the painting color at step k is the one expected by the next operation of job j
  // somematch[j] = 1 if at least one job matches the selected painting color for step k    
  for[j in 1..NumJob][k in 1..TotalNum] {
    if (k == 1) progress[j][k] <- 1;
    else {
      // if the color at step k-1 matches the expected color for job j then its operation is performed 
      // (and the progress index is incremented)
      progress[j][k] <- match[j][k-1] ? progress[j][k-1]+1 : progress[j][k-1];
    }
    // a powerful feature of LocalSolver 2.1 & above: y <- a[x] with 'a' an array of integers
    expectedColor[j][k] <- Operation[j][progress[j][k]];
    match[j][k] <- expectedColor[j][k] == paintingColor[k];
  }
  
  // a step is an actual step if the resource finds something to do
  someMatch[k in 1..TotalNum] <- or[j in 1..NumJob](match[j][k]);
  
  // first criterion minimize the number of unfinished operations at the end
  unfinished[j in 1..NumJob] <- 1 + NumOpe[j] - progress[j][TotalNum];
  minimize sum[j in 1..NumJob](unfinished[j]);
  
  // second criteria minimize the number of painting steps
  obj <- sum[k in 1..TotalNum](someMatch[k]);  
  minimize obj;  
}

/* Parameterizes the solver. */
function param() {
  if (lsTimeLimit == nil) lsTimeLimit = 60;
  if (lsNbThreads == nil) lsNbThreads = 4;
}

/* Writes down the best solution found. */
function output() { 
  print("Best sequence found:");
  for[k in 1..TotalNum:getValue(someMatch[k])==1] print(getValue(paintingColor[k])+" ");
  println();	
  for[j in 1..NumJob:getValue(unfinished[j])>0] print("Job "+j+" unfinished ("+getValue(unfinished[j])+")");
}

例題コンテンツ

• jobshop_scs/
• jobshop_scs/README.txt
• jobshop_scs/instances/
• jobshop_scs/instances/data1.in
• jobshop_scs/instances/data2.in
• jobshop_scs/instances/data3.in
• jobshop_scs/instances/data4.in
• jobshop_scs/instances/data5.in
• jobshop_scs/instances/datafreetrial.in
• jobshop_scs/jobshop_scs.lsp

このページの先頭へ