S1401-1-3 記憶領域割当型並列機械スケジューリング問題に対する近似アルゴリズム([S1401-1]生産システムの新展開(基礎・理論))

概要

論文の詳細を見る
In this paper, we consider a combinatorial optimization problem of scheduling n jobs of block type on linearly aligned m identical machines. Each job J_j is characterized by four integers, an arrival time a_j, a processing time p_j, the number q_j of consecutive machines required, and a weight w_j. There is a choice for eachjob whether the aligned machines serve it or not. If the aligned machines choose a job J_j, they gain the weight w_j as their profit. However, they have to start the service of the chosen job promptly after it arrives, selecting q_j consecutive machines in the alignment. The objective is to find a feasible schedule that maximizes the weighted number of chosen jobs. It has already been known that the scheduling problem is NP-hard for an arbitrary m. In this paper, we propose a polynomial time heuristic algorithm based on a transformation into the minimum cost flow problem, and prove that the approximation ratio is ⌞w/q_<min>⌟/⌞m/q_<max>⌟, where q_<min>=min_<1≤j$le;>{q_j} and q_<max>=max_<1≤j$le;>{q_j}.
一般社団法人日本機械学会の論文
2010-09-04