AN O(n^2 log^2 n) ALGORITHM FOR INPUT-OR-OUTPUT TEST IN DISJUNCTIVE SCHEDULING

スポンサーリンク

概要

• 論文の詳細を見る

• This paper is concerned with the input-or-output test that is a kind of interval capacity consistency tests. And an O(n^2 log^2 n) algorithm dealing with the test is proposed, where n denotes the number of jobs. In literature, an O(n^4) algorithm has been known. The tests can be effectively used to reduce the search space of time- and resource-constrained scheduling problems. Computational results show that our new algorithm is about 3 times faster for instances of 30 jobs than the existing algorithm.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Miyamoto Yuichiro

  Sophia University

• Uno Takeaki

  National Institute of Informatics

• Kubo Mikio

  Tokyo University Of Marine Science And Technology

• Uno Takeaki

  National Inst. Of Informatics

関連論文

• LINEAR TIME APPROXIMATION ALGORITHM FOR MULTICOLORING LATTICE GRAPHS WITH DIAGONALS
• A short note on the reducibility of the collapsing knapsack problem
• Practical Techniques for Speeding Up Enumeration Algorithms for Frequent Itemset Mining Problems
• A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
• AN O(n^2 log^2 n) ALGORITHM FOR INPUT-OR-OUTPUT TEST IN DISJUNCTIVE SCHEDULING
• Generating Chordal Graphs Included in Given Graphs
• The complexity of free flood filling games (コンピュテーション)
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem (コンピュテーション)
• Solving the Dynamic Lot-Sizing Problem with Safety Stocks and Limited Inventories based on New Properties〔含 質疑応答〕

スポンサーリンク