Study on efficient algorithms for the dynamic block relocation problem

动态块重定位问题的高效算法研究

• 批准号: 22K04577
• 负责人: 田中 俊二
• 金额: $ 2万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K04577/
• 关键词: 並列スタック積み込み問題; 動的ブロック積み替え問題; 多項式時間; 分枝限定法; 最適化; アルゴリズム

本研究は，ブロック積み替え問題に対する結果を，並列スタック積み込み問題，動的ブロック積み替え問題と段階的に拡張することで，動的ブロック積み替え問題に対する効率的な厳密解法を構成することを目的とする．２０２２年度の主成果は以下の２点である．（１）並列スタック積み替え問題の計算複雑さに関する結果．他のアイテムの取り出しをブロックしているアイテム（ブロッキングアイテム）の総数を最小化する並列スタック積み替え問題は，NP困難な組合せ最適化問題であることが知られている．しかし，スタックの容量制約がない問題の計算複雑さはこれまで知られていなかった．そこで本研究では，この問題が多項式時間で求解可能であることを，順序グラフの最大独立分割問題との等価性を示すことにより証明した．（２）動的ブロック積み替え問題に対する厳密解法に関する結果．ブロックの到着時刻から実際の積み込み時刻までの遅れ時間，および出発時刻から実際の取り出し時刻までの遅れ時間を考え，これら遅れ時間の重み和を最小化する動的ブロック積み替え問題を対象とした．また，本問題において，次に取り出すブロックの上に積まれたブロックのみ積み替え可能な制限問題と，積み替えに制限を設けない無制限問題の２通りの問題設定を考えた．そして，これらに対して分枝限定法に基づく基本的な厳密解法を構成した．そして数値実験によりその有効性を検討した．（１）の成果については２０２２年に国内学会で発表を行った．また，（２）の成果については，２０２３年に国内学会で発表予定である．

这项研究旨在通过逐渐扩大块转运问题的结果，并通过平行堆栈加载问题和动态块转移问题来构建一种有效而精确的解决方案，以解决动态块转移问题。 2022财政年度的主要结果是以下两点。 （1）结果是平行堆栈转运问题的计算复杂性。并行堆栈转运问题最小化了阻止其他项目检索的项目总数（阻止项目），已知是一个难以在NP中使用的组合优化问题。但是，直到现在，没有堆栈容量限制的问题的计算复杂性才尚不清楚。因此，在这项研究中，我们证明了可以在多项式时间内解决此问题，以表明等同于序数图的最大独立分配问题。 （2）最终解决动态块转运问题的确切解决方案的结果。考虑到从块的到达时间到实际加载时间的延迟时间，以及从出发时间到实际检索时间的延迟时间，我们针对动态块转移问题，这将这些延迟时间的重量总和最小化。在这个问题中，我们还考虑了两种问题设置：一个限制问题，仅允许堆叠在下一个块上的块，而无限的问题则不限制转移。然后，我们基于分支限制方法构建了一个基本的严格解决方案。然后通过数值实验检查了这种有效性。 （1）的结果在2022年的国内会议上提出。此外，（2）的结果将在2023年的国内会议上提出。

项目成果

Polynomial-time algorithm for the parallel stack loading problem with unlimited stack capacity

堆栈容量无限的并行堆栈加载问题的多项式时间算法

• 发表时间: 2022
• 作者: Shunji Tanaka;Sven Boge
• 通讯作者: Sven Boge

遅れ時間和最小化を目的とした動的ブロック積み替え問題に対する分枝限定法

旨在最小化延迟时间总和的动态块重加载问题的分支定界法

• 发表时间: 2023
• 作者: 西藤 俊暁;田中 俊二
• 通讯作者: 田中 俊二