Research on the online scheduling problem with respect for respective tasks

スケジューリング問題(SCP)とは、有限個のマシンとそのマシンにおいて処理すべき多数のタスクとが与えられた際に、そのタスクをどの様に各マシンに割り当てて処理すべきか、という理論計算機科学分野の重要な問題である。例えば、計算機のCPUにおいて処理すべき命令や、コンビニのレジとそこに並ぶ買い物客による待ち行列などは、それぞれマシンとタスクとして見なすことが可能であり、SCPとして定式化し得る。我々の身の周りにおいて生じる事象（問題点）に対して理論的な解決策を与えるという動機から、SCPはオンライン問題と呼ばれる、タスクに関する情報が時間の経過と共に逐次的に与えられる問題設定(OSCP)において盛んに研究されている。ところが、従来のOSCPでは、1つのタスクがマシンを占有することを許す問題設定が多く、実用的な解決策を提供しているとは言い難い状況が発生している。本研究ではその様な問題点を解消する為の個々のタスクを尊重する様な、(a)OSCPの新しい問題設定を提案し、(b)幾つかの方式によって、その問題設定に対する効率的なアルゴリズムを設計することを目的としている。(a)については、令和元年度に問題設定の設計を終えている。 (b)については、決定性方式について既に成果を発表している為、それ以外の方式（制約条件・付加情報・乱択方式）についても研究に取り組んでいる。また、(a)と(b)に関して、令和元年度に完成した問題設定を修正した新たな問題設定の設計とそれに対する効率的なアルゴリズムの開発を進めている。加えて、これらの研究活動に付随して幾つかの研究成果が得られており、それらについては査読付き学術雑誌に投稿し査読中である。

スケジューリング問題(SCP)とは、有限個のマシンとそのマシンにおいて処理すべき多数のタスクとが与えられた際に、そのタスクをどの様に各マシンに割り当てて処理すべきか、という理論計算機科学分野の重要な問題である。例えば、計算機のCPUにおいて処理すべき命令や、コンビニのレジとそこに並ぶ買い物客による待ち行列などは、それぞれマシンとタスクとして見なすことが可能であり、SCPとして定式化し得る。我々の身の周りにおいて生じる事象（問題点）に対して理論的な解決策を与えるという動機から、SCPはオンライン問題と呼ばれる、タスクに関する情報が時間の経過と共に逐次的に与えられる問題設定(OSCP)において盛んに研究されている。ところが、従来のOSCPでは、1つのタスクがマシンを占有することを許す問題設定が多く、実用的な解決策を提供しているとは言い難い状況が発生している。本研究ではその様な問題点を解消する為の個々のタスクを尊重する様な、(a)OSCPの新しい問題設定を提案し、(b)幾つかの方式によって、その問題設定に対する効率的なアルゴリズムを設計することを目的としている。(a)については、令和元年度に問題設定の設計を終えている。 (b)については、決定性方式について既に成果を発表している為、それ以外の方式（制約条件・付加情報・乱択方式）についても研究に取り組んでいる。また、(a)と(b)に関して、令和元年度に完成した問題設定を修正した新たな問題設定の設計とそれに対する効率的なアルゴリズムの開発を進めている。加えて、これらの研究活動に付随して幾つかの研究成果が得られており、それらについては査読付き学術雑誌に投稿し査読中である。