2024-03-29T14:17:10Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000318572023-04-27T10:00:04Z01164:02592:02620:02625
周期的なタイムスロット付きジャストインタイムスケジューリング問題のヒューリスティックアルゴリズムA Heuristic Method for Just -In- Time Scheduling Problem with Periodic Time Slotsjpnhttp://id.nii.ac.jp/1001/00031857/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=31857&item_no=1&attribute_id=1&file_no=1Copyright (c) 2004 by the Information Processing Society of Japan北陸先端科学技術大学院大学情報科学研究科北陸先端科学技術大学院大学情報科学研究科千葉, 英史平石, 邦彦与えられた納期ちょうどにジョブの処理を完了する様なスケジュールを求める問題をジャストインタイムスケジューリング問題と呼ぶ.我々は周期的なタイムスロットという現実的な仮定を設けたジャストインタイムスケジューリング問題を取り扱う.本稿ではまず,P≠NPの仮定の下で近似不可能であることを証明する.次に,機械数が1である場合のヒューリスティックアルゴリズムを提案する.アイデアは最小費用流問題への帰着であり,最小費用流を求める以外はフロー値の単純な更新をするだけなので,ヒューリスティックアルゴリズムは高速である.実際に計算機実験も行って確かめた.また,ある制約の下でヒューリスティックアルゴリズムが最適解を返すことを示す.さらに,ある制約の下でヒューリスティックアルゴリズムの近似比を与える.Just-in-time scheduling problem is the problem of finding an optimal scheduling such that each job processed by parallel identical machines finishes exactly at its due time. We study the problem under a realistic assumption called periodic time slots. In this paper, we prove that this problem cannot be approximated, assuming P≠NP. Next, we present a heuristic algorithm, assuming that the number of machines is only one. The key idea is to reduce the problem to a network flow problem. The heuristic algorithm is fast because it includes simple updations of some values of a flow over and above the minimum cost flow that dominates the total time. Next, we show some simulation results. Our heuristic algorithm returns an optimal solution under a constraint. For other cases, we give an approximation bound of our heuristic solution to the oprimal one.AN1009593X情報処理学会研究報告アルゴリズム(AL)200434(2003-AL-094)182004-03-192009-06-30