機械加工スケジューリング問題(単目的)

本問題は自動化が進んだ製造工場における機械加工スケジューリング問題です．
現在，産業界では，少子化や若者のものづくり離れなどの影響による人手不足が問題となっています．そのため，人手不足を補うために，デジタル技術を活用した生産工程の自動化が進められています．しかし，作業者と自動処理可能な機械が混在する実際の製造現場では，作業者の休憩時間や機械の稼働時間など様々な制約が存在します．そのため，多制約最適化問題のための効率的な最適化手法の開発が期待されています．
このような背景をもとに本問題では実際の製造現場で起こっている問題を取り上げ，良質なスケジュールの導出を目指してもらいます．

機械加工スケジューリング問題

問題の概要

今回の問題で想定する工場は下図に示すような自動パレットシステムを導入しています．

マシニングセンタと呼ばれる加工機械が加工対象物（ワーク）の加工を行い，作業者はワークを固定する台（パレット）にワークの取り付け/取り外しを行います．マシニングセンタの前にはパレットが12個設置されています．各パレットにはそれぞれワークを1つ取り付けることができます．

ワークは以下の手順で処理されます．

1. ワークをパレットに取り付ける（作業者）
2. ワークを加工する（マシニングセンタ）
3. ワークをパレットから取り外す（作業者）

ワークが取り付けられているパレットは自動パレットシステムによって，任意の順番でマシニングセンタに投入されます．作業者とマシニングセンタは独立して仕事を行うことができます．また作業者には作業ができない時間が存在し，夜間（17:00〜翌朝9:00）のほか，休憩時間（10:00〜10:10，12:00〜12:45，15:00〜15:15）が設定されています．また各日の作業は9:00を開始時刻とするため，9:00に日付が変わるものとします．したがって，1日目の9:00から2日目の9:00までを1日目とします．なお，作業者の作業は夜間と休憩時間を跨ぐことはできません．マシニングセンタの作業は日付の切り替え（翌朝9:00）を跨ぐことができません（0:00を跨ぐことはできます）．

ワークをパレットに取り付ける際，治具と呼ばれるワークを固定する器具が必要です．治具はワークごとに使えるものが決まっています．治具の交換はパレットにワークを取り付ける際に行い，45分余分にかかります．

ワークには品番が存在し，同一パレット上でワークを交換する際，ワークの品番が異なる場合は10分の段取り替え時間が発生します．治具を交換する場合は，この段取り替え時間は発生しません．

問題定義

本問題は作業者とマシニングセンタの2機械のジョブショップ・スケジューリング問題(Job-shop Scheduling Problem: JSP)として捉えることができます．本問題ではこちらの論文で提案する混合整数計画モデルを基に，納期に関する制約を緩和した問題を出題します．目的関数は第1項 ( $E_j-t_j^{\text{F}}E\_j\; -\; t^\{\backslash text\{F\}\}\_\{j\}$ ) が納期余裕の最大化，第2項 ( ${\psi }_j^{\text{P}}\backslash psi^\backslash text\{P\}\_j$ )が納期遅れによるペナルティです．納期遅れが発生した場合，第1項はマイナス値をとりますが，ペナルティとして第2項も追加しています．一方，納期遅れが発生しない場合は第2項は0になります．

$\text{minimize}-{\sum }_{j=1}^W(E_j-t_j^{\text{F}})+{\sum }_{j=1}^W{\psi }_j^{\text{P}}\backslash text\{minimize\}\; \backslash quad\; -\; \backslash sum^\{W\}\_\{j=1\}\; (E\_j\; -\; t^\{\backslash text\{F\}\}\_\{j\})\; +\; \backslash sum^\{W\}\_\{j=1\}\; \backslash psi^\backslash text\{P\}\_j$

元論文のモデルから追加した制約は以下の通りです．

$\text{subject to}\backslash text\{subject\; to\}$

• 納期遅れの定義
  ${\psi }_j^{\text{P}}\ge t_j^{\text{F}}-E_j(j=\{1,\mathrm{.}\mathrm{.}\mathrm{.},W\})\backslash psi^\{\backslash text\{P\}\}\_j\; \backslash ge\; t^\{\backslash text\{F\}\}\_j\; -\; E\_j\; \backslash qquad\; (j\; =\; \backslash \{1,...,W\backslash \})$

本問題で使用する混合整数計画モデルの全体はこちらをご確認ください．なお，表記の簡易化のため，本ページでは $t_j^{\text{F}}t^\{\backslash text\{F\}\}\_j$ の定義をワーク $jj$ の全ての作業の終了時刻としています．

各変数の定義は以下のとおりです．

設計変数

本問題には5種類の決定変数がありますが，実行可能解を見つけるのが難しい複雑な問題となっています．そのため，皆さまには決定変数のうち作業の日付割り当てのみを決定していただきます．残りの変数はサーバーでSCIPを使い導出し，評価値を返します．