Studies on Job Scheduling Problems using Buffers

利用缓冲区的作业调度问题研究

• 批准号: 18700015
• 负责人: ASAHIRO Yuichi
• 金额: $ 1.56万
• 依托单位: Kyushu Sangyo University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2008
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18700015/
• 关键词: アルゴリズム理論; 仕事計画; 緩衝帯; 計算複雑さ; アルゴリズム; 組み合わせ最適化; Jankovの定理

緩衝帯を利用できるような組み合わせ最適化問題のいくつかに対し、計算複雑さの解析とアルゴリズムの提案を行った。例えば、ペイントショップ問題に対して、他の問題への帰着を行うことで既知のアルゴリズムを利用した近似アルゴリズム、ならびに効率良く最適解を得られる入力構造の解析に基づいたアルゴリズムを提案した。また、ソーティングバッファー問題に対して、コストが一様メトリックで定義される場合の計算複雑さを示した。

提出了一些允许使用缓冲液带的组合优化问题的计算复杂性分析和算法。例如，我们提出了一种近似算法，该算法通过引起其他问题来利用已知算法，以及基于对输入结构的分析，该算法有效地获得了最佳解决方案。当成本以统一的指标定义为排序缓冲问题问题时，我们还证明了计算复杂性。

项目成果

Note on Approximation of 1-Regular 2-Color Paintshop Problem Proc

关于 1-Regular 2-Color Paintshop 问题过程近似的注释

• 发表时间: 2007
• 作者: Yuichi Asahiro;Eiji Miyano and Taku Nakamura
• 通讯作者: Eiji Miyano and Taku Nakamura

NP-hardness of the Sorting Buffer Problem on the Uniform Metric

统一度量上排序缓冲区问题的 NP 难度

• DOI: 10.1016/j.dam.2012.02.005
• 发表时间: 2012
• 期刊: Discrete Applied Mathematics
• 影响因子: 1.1
• 作者: Yuichi Asahiro;Kenichi Kawahara;and Eiji Miyano
• 通讯作者: and Eiji Miyano

On Approximation of Bookmark Assignments

关于书签分配的近似

• 发表时间: 2007
• 期刊: Proc. 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science Vol. 4708
• 作者: Y. Asahiro;E. Miyano;T. Murata;and H. Ono
• 通讯作者: and H. Ono

最大出次数最小化問題の各種グラフクラスに対する計算複雑さ

最大出度最小化问题的各种图类的计算复杂度

• 发表时间: 2008
• 作者: 朝廣;雄一
• 通讯作者: 雄一

ブックマーク問題の近似について

关于书签问题的近似

• 发表时间: 2007
• 作者: 柴田章博;中田尚;中西正樹;山下茂;中島康彦;朝廣雄一,宮野英次,小野廣隆,村田俊英
• 通讯作者: 朝廣雄一,宮野英次,小野廣隆,村田俊英