変化に柔軟なスケジューリング手法の開発

开发灵活应对变化的调度方法

基本信息

批准号：
21K11772
负责人：
今堀慎治
金额：
$ 2.58万
依托单位：
Chuo University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2025-03-31
项目状态：
未结题

项目摘要

本研究課題「変化に柔軟なスケジューリング手法の開発」では，実社会のあらゆるところに現れる代表的な組合せ最適化問題の一つであるスケジューリング問題を研究対象としている．スケジューリング問題には多くの形式があるが，本研究では，表形式のスケジュールを作成する問題（タイムテーブリングとも呼ばれる），作業の処理順序を決定する形式のスケジューリング問題，および配送計画問題とその亜種に対して，柔軟性のある専用アルゴリズムを設計・実装する．近年多くの組合せ最適化問題に対して，汎用的な数理計画ソルバーを用いて解を得る研究が盛んに行われているため，そのような汎用的な最適化手法によって得られるスケジュールと比較することで，スケジューリング問題に対して専用解法を設計する価値を明らかにするとともに，それらの手法を実社会で役立てるための情報公開とプログラム提供を行うことが本研究の目的である．2022年度は，タイムテーブリング問題と配送計画問題に対する研究を行った．前者については，スポーツの総当たりリーグ戦対戦表を作成する問題（スポーツスケジューリング）に中心的に取り組んだ．後者については，各顧客ごとにサービスを提供できる時間帯が設定される，時間枠付きオリエンテーリング問題に対するメタ戦略アルゴリズムを設計し，ベンチマーク問題に対する既存の結果と比較を行った．これらの研究については，2023年3月に開催された「オペレーションズ・リサーチ学会春季研究発表会」において発表を行った．

本研究课题“开发一种灵活变化的调度方法”重点关注调度问题，这是现实世界中随处可见的典型组合优化问题之一。调度问题有很多种类型，但在本研究中，我们将重点关注以表格格式创建调度（也称为时间表）的问题、确定工作处理顺序形式的调度问题以及为每个物种设计和实施灵活的专用算法。近年来，人们对使用通用数学规划求解器寻找许多组合优化问题的解决方案进行了很多研究，因此比较通过此类通用优化方法获得的时间表非常重要。本研究的目的是阐明组合优化问题的解决方案。设计针对调度问题的专用解决方案的价值，并公开信息并提供程序以使这些方法在现实世界中有用。 2022年，我们对时间表问题和交付计划问题进行了研究。对于前者，我们重点关注创建循环赛体育联赛对阵表（体育调度）的问题。对于后者，我们设计了一种针对时间框架定向问题的元策略算法，其中设置了可以为每个客户提供服务的时间段，并将其与基准问题的现有结果进行比较。这些研究已在 2023 年 3 月举行的“运筹学学会春季会议”上发表。