(57)【特許請求の範囲】
【請求項１】
複数のデバイスを備える関連のマルチデバイスシステムにおいてエネルギー消費を減少させるための制御システムであって、前記エネルギー制御システムは、
実行されるジョブを受信することと、
前記ジョブを実行する前記複数のデバイスのうちの１つの選択と、前記複数のデバイスのそれぞれに前記選択されたデバイスから前記ジョブを転送するための転送費用とを受信することと、
第１の費用関数の最適化を介して、前記複数のデバイスから前記ジョブを実行するための１つのデバイスを決定することであって、前記第１の費用関数は、前記デバイスの選択と前記受信された転送費用とに基づく、決定することと、
前記決定されたデバイスに前記ジョブを割り振ることと、
第２の費用関数の最適化を介して前記マルチデバイスシステムにおける各デバイスに対するタイムアウトを決定することであって、前記第２の費用関数は、前記マルチデバイスシステムによる見込みのエネルギー消費に基づく、決定することと、
前記決定されたタイムアウトを前記デバイスに提供することと、
を行うようにプログラミングされた少なくとも１つのプロセッサを備え、
前記デバイスと前記タイムアウトのうちの少なくとも一方が、マルコフ決定過程（ＭＤＰ）として制御問題をモデリングすることによって決定され、前記ＭＤＰは、前記第１の費用関数および前記第２の費用関数を含み、
ａ）最適領域における前記第１の費用関数は、式
【数１】
0005918106.tif 000107
に従ってコンピュータ計算され、ここで、ｋは前記複数のデバイスのうちの１つであり、ｈは前記複数のデバイスのうちの選択されたデバイスであり、Ｒｈｋはデバイスｋに対する転送費用であり、
【数２】
0005918106.tif 000108
は、第１のモードから第２のモードにデバイスｋを遷移させる費用であり、前記第２のモードは、前記第１のモードよりも多くの電力を消費し、σは、前記マルチデバイスシステムの制御状態ベクトルであり、各ｋ番目の成分はデバイスｋに関する状態を示し、０の値が、前記第１のモードに対応し、１の値が前記第２のモードに対応し、ｚは前記マルチデバイスシステムの要求状態であり、＜σ，ｚ＞はマルチデバイスシステムの状態であり、ｅｋは、１であるｋ番目の成分を除いた各成分に対する０のベクトルであり、Ｖは第２の費用関数であることと、
ｂ）最適領域における前記第２の費用関数は、式
【数３】
0005918106.tif 000109
に従ってコンピュータ計算され、ここで、ｋは前記複数のデバイスのうちの１つであり、ｇｋは、タイムアウトτが与えられた場合に、ジョブ間の時間ｘの一部または全部の間に第２のモードにおいてデバイスｋを維持する費用であり、γは割引係数であり、ｌは選択されたデバイスであり、σは前記マルチデバイスシステムの制御状態ベクトルであり、各ｋ番目の成分はデバイスｋに対する状態を示し、０の値が前記第１のモードに対応し、１の値が前記第２のモードに対応し、前記第２のモードは前記第１のモードよりも多くの電力を消費し、ｚは前記マルチデバイスシステムの要求状態であり、＜σ，ｚ＞は前記マルチデバイスシステムの状態であり、ｅｋは、１であるｋ番目の成分を除いた各成分に対する０のベクトルであり、Ｖｌは第１の費用関数であり、ＩＩ［条件］は、条件が満たされた場合には１を戻し、そうでなければ０であり、Ｐは、要求状態が与えられた場合の、次のジョブの時間と、そのデバイスとの確率分布であり、Ｑは、先の要求状態と先のジョブ以来の時間と前記選択されたデバイスとが与えられた場合の、次の要求状態の確率分布であることと、
のうちの少なくとも一方である、制御システム。
【請求項２】
デバイスに対する前記転送費用は、ユーザが、印刷品質の低下を考慮して、前記デバイス上で前記ジョブを実行する費用である、請求項１に記載の制御システム。
【請求項３】
デバイスに対する前記タイムアウトは、別のジョブが到着しない場合に、ジョブが完了した後で、エネルギー消費の少ない第２のモードに移動する前に、前記デバイスが第１のモードに留まる時間である、請求項１に記載の制御システム。
【請求項４】
デバイスに対するタイムアウトは、前記デバイスに対する要求の判断と前記デバイス間の転送費用とに基づく、請求項１に記載の制御システム。
【請求項５】
前記見込みのエネルギー消費は、デバイス選択に対する確率分布と、前記複数のデバイスによって受信されたジョブ間の時間とに基づく、請求項１に記載の制御システム。
【請求項６】
前記確率分布は、前記マルチデバイスシステムの異なる要求状態に関してコンピュータ計算される、請求項５に記載の制御システム。
【請求項７】
前記ＭＤＰが価値反復法を使用して解かれる、請求項１に記載の制御システム。
【請求項８】
前記第２の費用関数の前記最適化は、一次元最適化の有界数列に換算される、請求項１に記載の制御システム。
【請求項９】
前記第１の費用関数と前記第２の費用関数とが、選択された関数空間において少なくとも部分的に最小化される、請求項１に記載の制御システム。
【請求項１０】
請求項１の前記制御システムと複数のデバイスとを備え、前記複数のデバイスが、印刷デバイスである、マルチデバイス印刷システム。
【請求項１１】
前記少なくとも１つのプロセッサがさらに、
前記ジョブと前記選択と前記転送費用とを遠隔デバイスから通信ネットワークを介して受信すること、
を行うようにプログラミングされている、請求項１に記載の制御システム。
【請求項１２】
前記見込みのエネルギー消費が、前記複数のデバイスの全てで見込まれるエネルギー消費の総量である、請求項１に記載の制御システム。
【請求項１３】
前記少なくとも１つのプロセッサがさらに、
前記第１の費用関数の最適化を介して、前記複数のデバイスから前記ジョブを実行するための大域的最適デバイスを決定することと、
前記第２の費用関数の最適化を介して、前記マルチデバイスシステムにおける各デバイスに対する大域的最適タイムアウトを決定することであって、前記各デバイスに対する前記タイムアウトが、別のジョブが到着しない場合に、ジョブが完了した後で、エネルギー消費の少ない第２のモードに移動する前に、前記デバイスが第１のモードに留まる時間である、決定することと、
のうちの少なくとも１つを行うようプログラミングされている、請求項１に記載の制御システム。
【請求項１４】
複数のデバイスを備えるマルチデバイスシステムにおいてエネルギー消費を減少させるための方法であって、前記方法は、
実行されるジョブを受信することと、
前記ジョブを実行するための前記複数のデバイスのうちの１つの選択と、前記複数のデバイスのそれぞれに前記選択されたデバイスから前記ジョブを転送するための転送費用とを受信することと、
第１の費用関数の最適化を介して前記複数のデバイスから前記ジョブを実行するための１つのデバイスを決定することであって、前記第１の費用関数は、前記デバイスの選択と、前記受信された転送費用と、前記複数のデバイスのうちのデバイスを異なるエネルギー消費モード間に遷移させるための電力消費費用と、に基づく、決定することと、
前記決定されたデバイスに前記ジョブを割り振ることと、
第２の費用関数の最適化を介して前記マルチデバイスシステムにおける各デバイスに対する大域的最適タイムアウトを決定することであって、各デバイスに対する前記タイムアウトは、別のジョブが到着しない場合に、ジョブが完了した後で、エネルギー消費の少ない第２のエネルギー消費モードに移動する前に、前記デバイスが第１のエネルギー消費モードに留まる時間であり、前記第２の費用関数は、前記マルチデバイスシステムによる見込みのエネルギー消費に基づく、決定することと、
前記決定されたタイムアウトを前記デバイスに提供することと、
を包含し、
前記見込みのエネルギー消費は、デバイス選択に対する確率分布と、ジョブ間の時間とに基づき、
前記デバイスを決定することと、前記タイムアウトを決定することと、のうちの少なくとも一方が、マルコフ決定過程（ＭＤＰ）として制御問題をモデリングすることであって、前記ＭＤＰは、前記第１の費用関数および前記第２の費用関数を含む、モデリングすることを含み、
ａ）最適領域における前記第１の費用関数は、式
【数４】
0005918106.tif 000110
に従ってコンピュータ計算され、ここで、ｋは前記複数のデバイスのうちの１つであり、ｈは前記複数のデバイスのうちの選択されたデバイスであり、Ｒｈｋはデバイスｋに対する転送費用であり、
【数５】
0005918106.tif 000111
は、第１のモードから第２のモードにデバイスｋを遷移させる費用であり、前記第２のモードは、前記第１のモードよりも多くの電力を消費し、σは、前記マルチデバイスシステムの制御状態ベクトルであり、各ｋ番目の成分はデバイスｋに関する状態を示し、０の値が、前記第１のモードに対応し、１の値が前記第２のモードに対応し、ｚは前記マルチデバイスシステムの要求状態であり、＜σ，ｚ＞はマルチデバイスシステムの状態であり、ｅｋは、１であるｋ番目の成分を除いた各成分に対する０のベクトルであり、Ｖは第２の費用関数であることと、
ｂ）最適領域における前記第２の費用関数は、式
【数６】
0005918106.tif 000112
に従ってコンピュータ計算され、ここで、ｇｋは、タイムアウトτが与えられた場合に、ジョブ間の時間ｘの一部または全部の間に第２のモードにおいてデバイスｋを維持する費用であり、γは割引係数であり、ｌは選択されたデバイスであり、σは前記マルチデバイスシステムの制御状態ベクトルであり、各ｋ番目の成分はデバイスｋに対する状態を示し、０の値が前記第１のモードに対応し、１の値が前記第２のモードに対応し、前記第２のモードは前記第１のモードよりも多くの電力を消費し、Ｖｌは第１の費用関数であり、ＩＩ［条件］は、条件が満たされた場合には１を戻し、そうでなければ０であり、Ｐは、要求状態が与えられた場合の、次のジョブの時間と、そのデバイスとの確率分布であり、Ｑは、先の要求状態と先のジョブ以来の時間と前記選択されたデバイスとが与えられた場合の、次の要求状態の確率分布であることと、
のうちの少なくとも一方である、方法。
【請求項１５】
デバイスに対するタイムアウトは、前記デバイスに対する要求の判断と前記デバイスへの転送とに基づく、請求項１４に記載の方法。
【請求項１６】
前記第２の費用関数の最小化は、前記第２の費用関数の前記最適化を一次元最適化の有界数列に換算することを含む、請求項１４に記載の方法。
【請求項１７】
前記第１の費用関数と前記第２の費用関数との最小化が、関数空間において少なくとも部分的に行われる、請求項１４に記載の方法。
【請求項１８】
コンピュータによって実行されたときに、請求項１４の方法を実行する、コンピュータプログラム。
【請求項１９】
前記見込みのエネルギー消費が、前記複数のデバイスの全てで見込まれるエネルギー消費の総量である、請求項１４に記載の方法。
【請求項２０】
印刷システムであって、
複数の印刷デバイスと、
エネルギー消費を減少させるための制御システムと、
を含み、
前記制御システムは、
実行される印刷ジョブを受信することと、
ユーザによって提出された印刷ジョブチケットを受信することであって、前記提出された印刷ジョブチケットが、前記印刷ジョブを実行するための前記複数の印刷デバイスのうちの１つの選択と、前記複数の印刷デバイスのそれぞれに前記選択された印刷デバイスから前記印刷ジョブを転送するための転送費用と、を含む、受信することと、
第１の費用関数の最適化を介して前記複数の印刷デバイスから前記印刷ジョブを実行するための１つの印刷デバイスを決定することであって、前記第１の費用関数は、前記印刷デバイスの選択と、前記受信された転送費用と、前記複数の印刷デバイスのうちの印刷デバイスを異なるエネルギー消費モード間に遷移させるための電力消費費用と、に基づく、決定することと、
前記決定された印刷デバイスに前記印刷ジョブを割り振ることと、
第２の費用関数の最適化を介して前記複数の印刷デバイスのそれぞれに対する大域的最適タイムアウトを決定することであって、各印刷デバイスに対する前記タイムアウトは、別の印刷ジョブが到着しない場合に、印刷ジョブが完了した後で、エネルギー消費の少ない第２のエネルギー消費モードに移動する前に、前記印刷デバイスが第１のエネルギー消費モードに留まる時間であり、前記第２の費用関数は、前記印刷システムによる見込みのエネルギー消費に基づき、前記見込みのエネルギー消費が、前記複数の印刷デバイスの全てで見込まれるエネルギー消費の総量である、決定することと、
前記決定されたタイムアウトを前記印刷デバイスに提供することと、
を行うようにプログラミングされた少なくとも１つのプロセッサを備え、
前記印刷デバイスを決定することと、前記タイムアウトを決定することと、のうちの少なくとも一方が、マルコフ決定過程（ＭＤＰ）として制御問題をモデリングすることであって、前記ＭＤＰは、前記第１の費用関数および前記第２の費用関数を含む、モデリングすることを含み、
ａ）最適領域における前記第１の費用関数は、式
【数７】
0005918106.tif 000113
に従ってコンピュータ計算され、ここで、ｋは前記複数の印刷デバイスのうちの１つであり、ｈは前記複数の印刷デバイスのうちの選択された印刷デバイスであり、Ｒｈｋは印刷デバイスｋに対する転送費用であり、
【数８】
0005918106.tif 000114
は、第１のモードから第２のモードに印刷デバイスｋを遷移させる費用であり、前記第２のモードは、前記第１のモードよりも多くの電力を消費し、σは、前記印刷システムの制御状態ベクトルであり、各ｋ番目の成分は印刷デバイスｋに関する状態を示し、０の値が、前記第１のモードに対応し、１の値が前記第２のモードに対応し、ｚは前記印刷システムの要求状態であり、＜σ，ｚ＞は印刷システムの状態であり、ｅｋは、１であるｋ番目の成分を除いた各成分に対する０のベクトルであり、Ｖは第２の費用関数であることと、
ｂ）最適領域における前記第２の費用関数は、式
【数９】
0005918106.tif 000115
に従ってコンピュータ計算され、ここで、ｇｋは、タイムアウトτが与えられた場合に、印刷ジョブ間の時間ｘの一部または全部の間に第２のモードにおいて印刷デバイスｋを維持する費用であり、γは割引係数であり、ｌは選択された印刷デバイスであり、σは前記印刷システムの制御状態ベクトルであり、各ｋ番目の成分は印刷デバイスｋに対する状態を示し、０の値が前記第１のモードに対応し、１の値が前記第２のモードに対応し、前記第２のモードは前記第１のモードよりも多くの電力を消費し、Ｖｌは第１の費用関数であり、ＩＩ［条件］は、条件が満たされた場合には１を戻し、そうでなければ０であり、Ｐは、要求状態が与えられた場合の、次の印刷ジョブの時間と、その印刷デバイスとの確率分布であり、Ｑは、先の要求状態と先の印刷ジョブ以来の時間と前記選択された印刷デバイスとが与えられた場合の、次の要求状態の確率分布であることと、
のうちの少なくとも一方である、印刷システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本例示的な実施形態は、一般的に、電力管理に関する。本例示的な実施形態は、複数の印刷デバイスを備えるマルチデバイス印刷システムに関する用途を特に見出し、マルチデバイス印刷システムを特に参照して記載される。しかしながら、本例示的な実施形態は、他の使用計画においても用途を見出し、上記の用途には必ずしも限定されないことを理解されたい。
【背景技術】
【０００２】
印刷デバイスは、典型的には、異なる電力消費レベルに対応する異なる動作モードを含む。そのような動作モードは、典型的には、アイドルモードと省電力化モードとを含む。アイドルモードにおいて、印刷デバイスは、典型的には最大電力を必要とする印刷のために使用される準備が完了する。使用されていない時には、印刷デバイスは、スタンバイモード、低電力モード、またはスリープモードとしても知られる省電力モードへ回帰する。省電力モードにおいて、印刷デバイスは、印刷デバイスのある機能を支援するために充分な電力を取るが、印刷デバイスが再び完全に動作することが出来るようになる前にはウォームアップ期間を必要とする。
【０００３】
印刷デバイスに対するウォームアップ期間は、例えば、印刷ジョブが印刷のために受信された時、またはユーザが印刷デバイスを作動させた時に作動させられる。印刷デバイス制御システムは、次に、印刷デバイスの使用に備えてさらなる電力を取る構成要素を駆動する。例えば、プリンタは、フューザロールを加熱して、マーキング材料が使用の準備をされてもよい。レーザプリンタの場合において、これは、概して、現像剤の筐体中でトナー粒子を循環させることを含む。固体インクプリンタに関して、固体インクは、融点よりも高い温度まで加熱される。
【０００４】
印刷デバイスが使用されると、印刷デバイスは、動作温度範囲内または動作状態内で１つ以上の構成要素を維持するために、何らかの所定の期間（タイムアウト）の間、高電力消費レベルのアイドルモードのままであり得る。タイムアウトは、構成要素が経験するサイクル数を減少させ、これが、印刷デバイスの動作寿命を保つのを助けると共に、顧客の待ち時間を減少または排除する。印刷デバイスが、事前設定されたタイムアウトによって再度使用されない場合には、印刷デバイスは、省電力モードに回帰し始める。
【０００５】
現在、大部分の印刷デバイスにおいて、スリープモードに入る前に待つ無活動期間は、Ｅｎｅｒｇｙ  Ｓｔａｒなどの環境基準に従って、管理者によって設定されるか、または印刷デバイスの製造業者によって事前に定められるかのいずれかである。２００６年まで、印刷デバイスは、製造業者がＥｎｖｉｒｏｎｍｅｎｔａｌ  Ｐｒｏｔｅｃｔｉｏｎ  Ａｇｅｎｃｙ（ＥＰＡ）の推奨タイムアウトを尊重したか否かに基づいてＥｎｅｒｇｙ  Ｓｔａｒ準拠と評価された。印刷デバイスの種類（例えば、スキャナ、コピー機、多機能デバイス）と、その速度性能とよって推奨が決定された。さらに、推奨は、任意であり、印刷デバイスに内蔵されたどのような論理または知能によっても自己適応されなかった。
【０００６】
今日、Ｅｎｅｒｇｙ  Ｓｔａｒ基準は、印刷デバイスが所定の基準使用パターンでリクエストを受信する、一週間のうちの一定の期間の間の電力消費の評価に基づく。評価方法の結果が、ｋＷｈで測定されたＴｙｐｉｃａｌ  Ｅｎｅｒｇｙ  Ｃｏｎｓｕｍｐｔｉｏｎ（ＴＥＣ）値であり、その結果は、Ｅｎｅｒｇｙ  Ｓｔａｒの認可を得るためには一定のレベルよりも下になければならない。例えば、毎分２４画像（２４ＩＰＭ）を生成するカラー多機能デバイスに関して、その電力消費は、（０．２ｋＷｈ＊２４）＋５ｋＷｈよりも下になければならない。現在の評価方法は、使用パターンを考慮に入れるが、使用パターンの推計学的性質を考慮に入れない。
【０００７】
ＴＥＣの最大レベルを守るために、製造業者は、タイムアウトを減少させ電力消費を改善するタイムアウト戦略を利用する。これを達成するための１つの戦略は、スリープ状態から活動状態への切り替えの間に印刷デバイスが利用できない時間に従って、タイムアウトを調節することである。別の戦略は、アイドル期間とウェークアップ遅延との間の関係（すなわち、省電力モードから出る時間）に従って、タイムアウトを設定することである。この関係が小さい場合には、タイムアウトは増加し、そうでなければ、タイムアウトは減少する。しかしながら、ほとんどの場合、タイムアウト値は、変化がなく、および／またはデバイスの実際の使用に適応されない。
【０００８】
さらに、印刷デバイスは、典型的には、複数の印刷デバイスを備えるマルチデバイス印刷システムに配備され、各印刷デバイスは、典型的には、入来印刷ジョブを実行することが出来る。そのようなシステムにおいて、ユーザは、典型的には、ユーザが印刷ジョブを実行して欲しい印刷デバイスを特定する。そうする際に、ユーザは、通常、ユーザにとって最も便利であるか、最も良い印刷デバイスを選択する。しかしながら、ユーザは、多くの場合に、電力コストを考慮しない。例えば、ユーザは一定の印刷デバイスを好むかもしれないが、印刷デバイスが省電力モードにある場合には、印刷デバイスを起動する費用は、ユーザが別の印刷デバイスに印刷する「費用」を上回るかもしれない。
【発明の概要】
【課題を解決するための手段】
【０００９】
本明細書は、上記の課題や他の課題を克服する新たな改善されたシステムおよび方法を提供する。
【００１０】
本明細書の一実施形態によって、複数のデバイスを含む関連のマルチデバイスシステムにおけるエネルギー消費を減少させるための制御システムが提供される。制御システムは、少なくとも１つのプロセッサを含む。プロセッサは、実行されるジョブだけでなく、そのジョブを実行するための、複数のデバイスのうちの１つの選択と、選択されたデバイスから複数のデバイスのうちの残りのもののそれぞれにジョブを転送するための転送費用とを受信するようにプログラミングされる。ジョブを実行するための複数のデバイスから１つのデバイスが、第１の費用関数の最適化を介して決定される。第１の費用関数は、デバイスの選択と、受信された転送費用とに基づく。ジョブは決定されたデバイスに割り振られ、マルチデバイスシステムにおける各デバイスに対するタイムアウトが、第２の費用関数の最適化を介して決定される。第２の費用関数は、マルチデバイスシステムによる見込みのエネルギー消費に基づく。デバイスは決定されたタイムアウトを提供される。
【００１１】
制御システムの様々な態様において、
複数のデバイスは、複数の印刷デバイスを含む。
【００１２】
デバイスの選択は、ジョブに対するジョブチケットで特定される。
【００１３】
デバイスに対する転送費用は、生産性の損失または品質の低下を考慮した、ユーザがデバイス上でジョブを実行する費用である。
【００１４】
デバイスに対するタイムアウトは、別のジョブが到達しない場合に、ジョブが完了した後で、あまりエネルギーを消費しない第２のモードに移る前に、デバイスが第１のモードのままである時間である。
【００１５】
デバイスに対するタイムアウトは、デバイスに対する要求の見積額と、デバイス間の転送費用とに基づく。
【００１６】
見込みエネルギー消費は、デバイスの選択に関する確率分布と、複数のデバイスによって受信されるジョブ間の時間と基づく。
【００１７】
確率分布は、マルチデバイスシステムの異なる要求状態に関してコンピュータ計算される。
【００１８】
デバイスとタイムアウトとのうちの少なくとも一方が、マルコフ決定過程（ＭＤＰ）として制御問題をモデリングすることによって決定され、ＭＤＰは、第１の費用関数と第２の費用関数とを含む。
【００１９】
ＭＤＰは価値反復法を使用して解かれる。
【００２０】
第２の費用関数の最適化は、一次元最適化の有界数列に換算される。
【００２１】
第１の費用関数と第２の費用関数とは、少なくとも部分的には、選択された関数空間において最小化される。
【００２２】
最適領域における第１の費用関数は、式
【数１】
0005918106.tif 000002
に従ってコンピュータ計算され、ここで、ｋは、複数のデバイスのうちの１つであり、ｈは、複数のデバイスのうちの選択されたデバイスのであり、Ｒｈｋは、デバイスｋに対する転送費用であり、
【数２】
0005918106.tif 000003
は、第１のモードから第２のモードにデバイスｋを遷移させる費用であり、第２のモードは、第１のモードよりも多くの電力を消費し、σは、マルチデバイスシステムの制御状態ベクトルであり、各ｋ番目の成分は、デバイスｋに関する状態を示し、０の値は第１のモードに対応し、１は第２のモードに対応し、ｚは、マルチデバイスシステムの要求状態であり、＜σ，ｚ＞は、マルチデバイスシステムの状態であり、ｅｋは、１であるｋ番目の成分を除いた、各成分に対する０のベクトルであり、ｖは、第２の費用関数である。
【００２３】
最適領域における第２の費用関数は、式
【数３】
0005918106.tif 000004
に従ってコンピュータ計算され、ここで、ｋは、複数のデバイスのうちの１つであり、ｇｋは、タイムアウトτが与えられると、ジョブ間の時間ｘの一部または全部の間に第２のモードにおいてデバイスｋを維持する費用であり、γは、割引係数であり、ｌは、選択されたデバイスであり、σは、マルチデバイスシステムの制御状態ベクトルであり、各ｋ番目の成分は、デバイスｋに関する状態を示し、０の値は、第１のモードに対応し、１は、第２のモードに対応し、第２のモードは、第１のモードよりも大きい電力を消費し、ｚは、マルチデバイスシステムの要求状態であり、＜σ，ｚ＞は、マルチデバイスシステムの状態であり、ｅｋは、１であるｋ番目の成分を除いた、各成分に対する０のベクトルであり、Ｖｌは、第１の費用関数であり、ＩＩ［条件］は、条件が満たされた場合には１に戻り、そうでなければ０であり、Ｐは、要求状態が与えられると、次のジョブとそのデバイスとの確率時間分布であり、Ｑは、先の要求状態と、先のジョブからの時間と、選択されたデバイスとが与えられると、次の要求状態の確率分布である。
【００２４】
マルチデバイス印刷システムは、制御システムと複数のプリンタとを含む。
【００２５】
本開示の別の実施形態によって、複数のデバイスを備えるマルチデバイスシステムにおいてエネルギー消費を減少させるための方法が提供される。実行されるジョブだけでなく、そのジョブを実行するための複数のデバイスのうちの１つの選択、および選択されたデバイスから複数のデバイスのそれぞれにジョブを転送するための転送費用とが受信される。ジョブを実行するための複数のデバイスから１つのデバイスが、第１の費用関数の最適化を介して決定される。第１の費用関数は、デバイスの選択と、受信された転送費用とに基づく。ジョブは、決定されたデバイスに割り振られ、マルチデバイスシステムにおける各デバイスに対するタイムアウトが、第２の費用関数の最適化を介して決定される。第２の費用関数は、マルチデバイスシステムによる見込みのエネルギー消費に基づく。デバイスは、決定されたタイムアウトを提供される。
【００２６】
方法の様々な態様において、
デバイスに対するタイムアウトは、デバイスに対する要求の判断と、デバイスに対する転送費用とに基づく。
【００２７】
見込みのエネルギー消費は、デバイス選択に関する確率分布とジョブ間の時間とに基づく。
【００２８】
デバイスの決定と、タイムアウトの決定とのうちの少なくとも一方が、マルコフ決定過程（ＭＤＰ）として制御問題をモデリングすることを含み、ＭＤＰは、第１の費用関数と第２の費用関数とを含む。
【００２９】
第２の費用関数の最小化は、一次元最適化の有界数列に第２の費用関数の最適化を換算することを含む。
【００３０】
第１の費用関数および第２の費用関数の最小化は、少なくとも部分的には、関数空間において行われる。
【００３１】
コンピュータプログラム製品は、コンピュータによって実行された時には本方法を行う命令を格納する非一時的記録媒体を含む。
【００３２】
本明細書の別の実施形態に従って、印刷システムが提供される。印刷システムは、複数の印刷デバイスと、エネルギー消費を減少させるように構成された制御システムとを含む。コントロールシステムは、実行される印刷ジョブだけでなく、印刷ジョブを実行するための複数のデバイスのうちの１つの選択と、および選択された印刷デバイスから複数のデバイスのそれぞれに印刷ジョブを転送する転送費用とを受信するようにプログラミングされた少なくとも１つのプロセッサを含む。印刷ジョブを実行するための複数の印刷デバイスから１つのデバイスが、第１の費用関数の最適化を介して決定される。第１の費用関数は、印刷デバイスの選択と受信された転送費用とに基づく。印刷ジョブは、決定された印刷デバイスに割り振られ、複数の印刷デバイスのそれぞれに対するタイムアウトは、第２の費用関数の最適化を介して決定される。第２の費用関数は、印刷システムによる見込みのエネルギー消費に基づく。印刷デバイスは、決定されたタイムアウトを提供される。
【図面の簡単な説明】
【００３３】
【図１】図１は、本開示の態様に従った、マルチデバイス印刷システムの構成図である。
【図２】図２は、マルチデバイス印刷システムにおいて電力消費を減少させるための方法の構成図である。
【図３】図３は、演算子の計算に関するグラフ図である。
【図４】図４は、演算子の計算に関するグラフ図である。
【図５】図５は、関数空間の関数に関する異なる形状のグラフ図である。
【図６】図６は、模擬の指数関数的要求と低転送費用とに対する２方策の累積費用のグラフ図である。
【図７】図７は、模擬の指数関数的要求と高転送費用とに対する２方策の累積費用のグラフ図である。
【図８】図８は、模擬の指数関数的要求と低転送費用とに対する２方策の割り振り費用とタイムアウト費用との間の費用の違いのグラフ図である。
【図９】図９は、模擬の指数関数的要求と高転送費用とに対する２方策の割り振り費用とタイムアウト費用との間の費用の乖離のグラフ図である。
【図１０】図１０は、実際の要求と低転送費用とに対する２方策の割り振り費用とタイムアウト費用との間の費用の乖離のグラフ図である。
【図１１】図１１は、実際の要求と高転送費用とに対する２方策の割り振り費用とタイムアウト費用との間の費用の違いのグラフ図である。
【図１２】図１２は、両方の係数に対して対数尺度を用いて転送費用係数と消費費用係数とに従った、利得の変化のグラフ図である。
【発明を実施するための形態】
【００３４】
例示的な実施形態は、同じジョブを行うことが出来る複数のデバイスを含むマルチデバイスシステム、例えば、ネットワーク印刷システムにおいて電力消費を減少させるための方法を提供する。一例示的な実施形態においては、デバイスのうちの１つによって実行されるジョブ、例えば、印刷ジョブが、選択されたデバイスから別のデバイスに選択的に転送され、そうした時には、システムの電力消費を減少させ、その減少は、転送費用を上回る。電力消費をさらに最小化するために、デバイスに対するタイムアウトが、システムに対する見込みの費用を最小化するように最適化される。
【００３５】
本明細書において使用されるように、「最適化」、「最小化」などの用語と、同様な表現とは、当業者がこれらの用語を理解するように広く理解される。例えば、これらの用語は、大域的最適絶対値、大域的絶対最小値などに限定されると解釈されるべきではない。例えば、関数の最小化は、絶対最小値に到達する前に停止基準で終わる反復最小化アルゴリズムを利用してもよい。最適値または最小値が局所的最適値または局所的最小値であることも企図される。
【００３６】
「タイムアウト」は、ジョブがデバイスによって受信（または完了）された後の期間であり、その期間の間には、（タイムアウトをリセットする）さらなるジョブが一時的な期間に受信されないと想定すると、デバイスは、低エネルギー消費状態（例えば、印刷デバイスが印刷をする準備が完了しておらず、印刷が始まる前にはアイドルモードまで温められなければならないスタンバイモード）に移行する前に、高エネルギー消費状態（例えば、印刷する準備が整った印刷デバイスの場合におけるアイドルモード）のままである。
【００３７】
以下の考察において、マルチデバイスシステムは、印刷システムと、プリンタとしてのデバイスとに関して記載されるが、システムは、他のデバイス、特に電気機械デバイスを含んでもよいことが理解されるべきである。
【００３８】
図１を参照すると、マルチデバイス印刷システム１０は、１つ以上の印刷ジョブ１６を実行するための複数の印刷デバイス（プリンタ）１２、１４を含む。「印刷ジョブ」は、印刷ジョブがどのように実行されるかに関する命令を含むジョブチケットを伴った１つ以上の関連の電子文書ページ画像の組である。やはり、印刷デバイス１２、１４は、互いに対して比較的に近くにあり、同じエリアのユーザの組によって自由にアクセスすることが出来る。いくつかの実施形態において、印刷デバイス１２、１４の数は、１０台を超えない。印刷デバイス１２、１４のそれぞれが、印刷ジョブ１６を実行するための印刷エンジン１８、２０を含む。印刷デバイス１２、１４は、同じものであっても異なるものであってもよく、スタンドアロンの印刷システム、または印刷することに加えて、コピーすること、ファックスすること、スキャンすること、およびそれらの組み合わせなどの他の能力を有する多機能デバイスを含んでもよい。通常のタイプの印刷エンジンは、ゼログラフィ印刷エンジン、インクジェット印刷エンジン、レーザ印刷エンジン、および熱印刷エンジンを含む。
【００３９】
一般的に、印刷ジョブ１６を実行する時には、印刷エンジン１８、２０は、ハードコピー印刷物２２を生み出すために、インクまたはトナーなどのマーキング材料を使用して、紙などの印刷媒体に画像を適用する。ゼログラフィ印刷エンジンの場合、印刷エンジンは、ベルトまたはドラムの形態の感光体を均一な電位まで帯電させ、潜像を作成するように選択的に感光体を放つ。それから、印刷エンジンは、選択された色のトナー粒子を現像剤筐体から感光体に適用し、潜像を印刷媒体に転送することによって潜像を現像する。次に、転送された画像は、熱および／圧力を使用してフューザで印刷媒体に融合されることにより、ハードコピー印刷をもたらす。
【００４０】
印刷デバイス１２、１４の通信ユニット２４、２６、例えば、モデムは、典型的には、ローカル・エリア・ネットワークなどの通信ネットワーク２８を介して印刷ジョブ１６を受信し、様々な時に印刷ジョブ１６を受信する。例えば、いくつかの印刷ジョブは、１分〜２分の間隔で到着してもよいが、他の印刷ジョブは、何分も離れて、または何時間も離れてもよい。印刷ジョブ１６を受診する際、印刷デバイス１２、１４のコントローラ３０、３２は、印刷エンジン１８、２０のローカル印刷キューに印刷ジョブ１６を追加し、例えば、先入れ先出し（ＦＩＦＯ）スケジューリングアルゴリズムを使用して、実行する印刷ジョブ１６のスケジュールを決める。いくつかの実施形態において、印刷ジョブ１６のうちの１つを受信する印刷デバイスはさらに、省電力モードから呼び起こされ、および／または印刷ジョブの実行の準備が行われる。コントローラ３０、３２はそれぞれ、関連のメモリ上でコンピュータ実行可能な命令を実行するプロセッサを含む。コンピュータ実行可能な命令は、スケジューリングアルゴリズムなどの上記の機能を適切に体現する。さらに、コントローラ３０、３２は、１つ以上のシステムバス３４、３６を介して、通信ユニット２４、２６および印刷エンジン１８、２０などの、印刷デバイス１２、１４の構成要素とデータを交換する。
【００４１】
電力消費を減少させるために、印刷デバイス１２、１４のそれぞれが、異なる電力消費レベルに対応する複数の異なる動作モードを含む。考察を容易にするために、各印刷デバイスは、アイドルモードと省電力モードとを含むことが仮定される。しかしながら、追加の動作モードが同様に受け入れ可能であることが理解されるべきである。アイドルモードにおいて、印刷デバイスは、印刷するために使用される準備が完了し、典型的には最大電力を必要とする。省電力モードにおいて、印刷デバイスは、印刷デバイスの一定の機能を支援するために充分な電力を取るが、印刷デバイスが再び完全に動作可能になる前にウォームアップ期間を必要とする。
【００４２】
印刷デバイス１２、１４のコントローラ３０、３２は、電力制御システム３８によって印刷デバイス１２、１４に割り振られたタイムアウトに従ってアイドルモードから省電力モードに印刷デバイス１２、１４を切り替える。典型的には、印刷デバイス１２、１４の通信ユニット２４、２６は、通信ネットワーク２８を介して電力管理システム３８からタイムアウトを受信する。さらに、以下で考察されるように、タイムアウトは、デバイス単位というよりも全体的に、マルチデバイス印刷システム１０に対する見込みの費用を最小化するように最適化される。印刷デバイスがアイドルモードにあり、印刷ジョブが実行されて以来の時間の長さが、割り振られたタイムアウトを超えた時には、印刷デバイスのコントローラは、省電力モードに印刷デバイスを切り替える。
【００４３】
１つ以上の印刷ジョブ生成器４０が印刷ジョブ１６を生成する。印刷ジョブ生成器４０は、手動入力に基づいて、および／または自動的に印刷ジョブを生成してもよい。前者に関しては、印刷ジョブ生成器は、印刷ジョブの生成を制御するユーザと関連付けられる。ユーザが印刷ジョブを生成するのを容易にするために、これらの印刷ジョブ生成器はそれぞれ、典型的には、キーボード、カーソル、制御デバイス、タッチスクリーンなどの１つ以上のユーザ入力デバイス４２、および／またはディスプレイなどの１つ以上のユーザ出力デバイス４４を含むか、またはそれらと関連付けられる。後者に関しては、印刷ジョブ生成器は、メモリ４６に格納されると共にプロセッサ４８によって実行されるソフトウェア構成要素を含み、プロセッサ４８は、一組の基準に応答して印刷ジョブを生成するように事前にプログラミングされる。例えば、ソフトウェアエージェントは、受信トレイで受信された全電子メールを印刷するように事前にプログラミングされてもよい。
【００４４】
印刷ジョブ生成器４０によって生成された印刷ジョブ１６のそれぞれは、印刷ジョブを実行するための印刷デバイス１２、１４のうちの一方の選択を含む。さらに、１つ以上の規則の組で事前にプログラミングされたソフトウェアエージェントが、典型的には選択を行う。例えば、そのような規則は、全てのカラー印刷ジョブが第１の印刷デバイスを使用し、他の全ての印刷ジョブが、第２の印刷デバイスまたは同じデバイスの異なる印刷エンジンを使用することを規定してもよい。しかしながら、印刷ジョブが手動で生成された時には、選択は、例えば、ユーザ入力デバイス４２を使用した手動入力に基づいて行われてもよい。上記のように、ユーザは、典型的には、電力消費を考慮することなく、ユーザにとって個人的に最も良い印刷デバイスを選択する。
【００４５】
印刷デバイスが選択された時には、他の印刷デバイス上で印刷ジョブを実行するための転送費用もまた規定される。例えば、２つの印刷デバイスシステムの第１の印刷デバイスが選択された場合には、第２の印刷デバイス上で印刷ジョブを実行するための転送費用もまた規定される。選択された印刷デバイスに対する「転送費用」はゼロであると想定する。他のデバイスに対する転送費用は、典型的には、ユーザに対する生産性の損失と、他の印刷デバイスを使用した結果としての印刷品質とのうちの１つ以上に対応する。典型的には、メモリ４６に格納されると共にプロセッサ４８によって実行されるソフトウェア構成要素は、転送費用を完成させるための１つ以上の規則の組で事前にプログラミングされる。しかしながら、印刷ジョブが手動で生成された時には、転送費用は、例えば、ユーザ入力デバイス４２を使用して手動で規定されてもよい。
【００４６】
印刷ジョブ生成器４０は、メモリ４６に格納されたコンピュータ実行可能な命令を実行するプロセッサ４８を含む。コンピュータ実行可能な命令は、ソフトウェアエージェントの機能などの上記の機能を適切に体現する。いくつかの実施形態において、印刷ジョブ生成器４０は、ラップトップコンピュータ、ワークステーションコンピュータ、デスクトップコンピュータ、スマートフォン、携帯端末などの１つ以上のコンピュータ、または例示的な方法を実装することが出来る任意のコンピュータデバイスを含む。印刷ジョブ生成器４０はさらに、通信ネットワーク２８に接続された他のデバイスと通信するための通信ユニット５０を含む。プロセッサ４８、メモリ４６、ユーザ入力デバイス４２、ユーザ出力デバイス４４、および通信ユニット５０などの、印刷ジョブ生成器４０の構成要素は、１つ以上のシステムバス５２を介して通信する。
【００４７】
電力制御システム３８は、印刷ジョブによって課された制約の下で大域的に最適な印刷デバイスに印刷ジョブ１６のそれぞれを割り振ることによってマルチデバイス印刷システム１０の電力消費を減少させることを目的とする。印刷ジョブにとって大域的に最適な印刷デバイスは、マルチデバイス印刷システム１０に対して最も安価で、印刷ジョブの制約下で印刷ジョブを実行することが出来る印刷デバイスである。考慮する費用は、電力消費費用（現在および／または将来）と転送費用とを含む。転送費用が規定されていない時には、転送費用はゼロであると想定される。さらに、無限大の転送費用が規定された時には、転送は無効にされることが出来る。印刷ジョブに対する割り振りは、典型的には、電力制御システム３８において印刷ジョブを受信することに応答して決定される。
【００４８】
印刷ジョブに対する大局的に最適な印刷デバイスを決定するために、多数の手法が利用され得る。いくつかの実施形態において、全体的なシステムの費用は、印刷デバイスが省電力モードである場合に、選択された印刷デバイスを起動することと関連付けられる費用と、選択されたデバイス以外のデバイスに印刷ジョブを転送する転送費用と、印刷ジョブが転送されることが出来たデバイスのそれぞれに関する、転送デバイスで印刷する費用とを含む、選択されたデバイスで印刷する費用のうちの少なくとも１つに関する関数としてモデリングされる。次に、費用関数が最適化される（例えば、適切な最適化方法を使用して最小化される）。いくつかの実施形態において、各印刷デバイスに関するシステムの費用が決定され、それから、最低費用の印刷デバイスが印刷ジョブの割り振りのために選択されることが出来る。他の実施形態において、割り振りの決定は、以下で考察されるように、同様に費用関数の最小化を利用するマルコフ決定過程（ＭＤＰ）を使用してモデリングされる。最適な印刷デバイスを決定した後で、印刷ジョブが印刷デバイスに割り振られる。
【００４９】
例示的な電力制御システム３８はさらに、各印刷デバイスに対するタイムアウトを最適化することによって、マルチデバイス印刷システム１０の電力消費を減少させる。印刷デバイスに対する最適なタイムアウトは、アイドルモードで印刷デバイスを維持することにより見込みの電力消費を最小化するタイムアウトとしてコンピュータ計算されることが出来、次に、次の印刷ジョブが印刷デバイスに割り振られるまで、印刷デバイスを省電力モードにして、再びアイドルモードに戻る可能性がある。注目すべきことに、印刷デバイスに対する最適なタイムアウトは、デバイスが転送を介して印刷ジョブを受信し得るので、要求の確率的挙動だけに基づいているのではない。典型的には、タイムアウトは印刷ジョブの割り振りの後に決定される。
【００５０】
各印刷デバイスに対する最適なタイムアウトを決定するために、多数の手法が利用され得る。いくつかの実施形態において、マルチデバイス印刷システム１０の見込みの電力費用は、２つ以上のタイムアウトに関する少なくとも１つの組み合わせの関数としてモデリングされ、各タイムアウトは、印刷デバイス１２、１４のそれぞれのデバイス（または、少なくとも、アイドルモードの印刷デバイス）に対応する。タイムアウト費用の関数は、少なくとも、印刷デバイスの要求と、印刷デバイスに対する見込みの転送とをを与えて、アイドルモードと省電力モードとの間で印刷デバイスを遷移させる費用を含む。見込みの要求は、印刷デバイスの印刷ジョブに関する到着間隔に対する既知の確率分布から決定されてもよい。見込みの転送は、デバイスの選択に対する既知の確率分布、最適には、ユーザに対する予測転送費用から決定されてもよい。次に、タイムアウトの費用関数が、適切な最適化方法を使用して最小化される。他の実施形態において、タイムアウトの決定は、以下で考察されるように、同様に費用関数の最適化を利用するＭＤＰを使用してモデリングされる。
【００５１】
確率分布は多数の異なる方法で生成することが出来る。１つの方法においては、必須データ（例えば、到着間隔データ、デバイスの選択、および／または転送費用）が、印刷デバイス１２、１４から直接的に取得される。あるいは、必須データは、印刷デバイス１２、１４上での検索のために格納されると共に利用可能なデータを追跡するジョブから引き出されてもよい。または、データは、印刷活動をモニタリングするソフトウェアが存在する印刷ジョブ生成器をホストする印刷サーバまたはクライアントワークステーションから取得されてもよい。いくつかの実施形態において、これらの確率分布は、時刻などの異なる要求状態で変化してもよい。例えば、要求は正午と深夜とでは非常に異なっている可能性が高い。要求状態の変化は、上で記載されたように決定された確率分布から決定されてもよい。
【００５２】
電力制御システム３８は、ハードウェアで、またはソフトウェアとハードウェアとの組み合わせで実施されてもよい。例示的な実施形態において、電力制御システム３８は、メモリ５４と、メモリ５４と通信するプロセッサ５６とを含む。メモリ５４は、マルチデバイス印刷システム１０の電力消費を最適化することを含む、以下でさらに詳細に記載される例示的な方法を行うための命令を格納し、その命令はプロセッサ５６によって実行される。電力制御システム３８はさらに、通信ネットワーク２８に接続されたデバイスと通信するための通信ユニット５８を含む。１つ以上のシステムバス６０が、プロセッサ５６、メモリ５４、および通信ユニット５８などの、電力制御システム３８の構成要素を連結する。通信制御システム３８は、例えば、通信ネットワーク２８を介して印刷デバイス１２、１４に連結されたサーバ上にあってもよい。しかしながら、いくつかの実施形態において、電力制御システム３８は、印刷デバイス１２、１４のうちの一方と統合され、および／または印刷デバイス１２、１４にわたって分散される。
【００５３】
「ソフトウェア」という用語は、本明細書において使用されるように、ソフトウェアの目的であるタスクを行うようにコンピュータまたは他のデジタルシステムを構成するための、コンピュータまたは他のデジタルシステムによって実行可能な命令の任意の集合または組を含むことが意図される。「ソフトウェア」という用語は、本明細書において使用されるように、ＲＡＭ、ハードディスク、光ディスクなどの格納媒体に格納されたそのような命令を含むことが意図され、ＲＯＭなどに格納されたソフトウェアである所謂「ファームウェア」を含むことも意図される。そのようなソフトウェアは、様々な方法で組織されてもよく、ライブラリとして組織されたソフトウェア構成要素、遠隔のサーバなどに格納されたインターネットベースのプログラム、ソースコード、解釈コード、オブジェクトコード、直接実行可能なコードなどを含んでもよい。ソフトウェアは、システム・レベル・コード、または一定の機能を行うためにサーバまたは他の場所にある他のソフトウェアに対する呼び出しを起動してもよいことが企図される。
【００５４】
「コントローラ」という用語は、本明細書において使用されるように、プロセッサとメモリとを含むことが意図される。「ユーザ入力デバイス」という用語は、本明細書において使用されるように、マウス、キーボード、タッチ・スクリーン・ディスプレイ、１つ以上のボタン、１つ以上のスイッチ、１つ以上のトグルスイッチなどのうちの１つ以上を含むことが意図される。「ユーザ出力デバイス」という用語は、本明細書において使用されるように、ＬＣＤディスプレイ、ＬＥＤディスプレイ、プラズマディスプレイ、投影ディスプレイ、タッチ・スクリーン・ディスプレイなどのうちの１つ以上を含むことが意図される。「通信ネットワーク」という用語は、本明細書において使用されるように、インターネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、ワイヤレスネットワーク、有線ネットワーク、セル方式ネットワーク、ＵＳＢおよびＩ２Ｃなどのデータバスなどのうちの１つ以上を含むことが意図される。「通信ユニット」という用語は、本明細書において使用されるように、モデム、イーサネット（登録商標）アダプタ、ＷｉＦｉアダプタ、３Ｇモデム、ケーブルモデム、ＤＳＬモデム、およびネットワークとの通信を容易にするその他任意のアダプタまたはモデムのうちの１つ以上を含むことが意図される。
【００５５】
「プロセッサ」という用語は、本明細書において使用されるように、マイクロプロセッサ、マイクロコントローラ、グラフィック・プロセシング・ユニット（ＧＰＵ）、特定用途向け集積回路（ＡＳＩＣ）、フィールド・プログラマブルゲート・アレイ（ＦＰＧＡ）などのうちの１つ以上を含むことが意図される。さらに、印刷ジョブ生成器４０のプロセッサ４８および電力制御システム３８のプロセッサ５６などの上記のプロセッサはそれぞれ、例えば、シングル・コア・プロセッサ、デュアル・コア・プロセッサ（または、さらに一般的には、多重コアプロセッサ）、デジタルプロセッサおよび協働する数値演算コプロセッサ、デジタルコントローラなどによって様々に体現されることが出来る。電力制御システム３８のプロセッサ５６に関して、図２に示された流れ図を実装することが出来る有限状態機械を実装することが出来る任意のデバイスが使用されることが出来る。
【００５６】
「メモリ」という用語は、本明細書において使用されるように、非一時的コンピュータ読取り可能な媒体、磁気ディスクもしくは他の磁気格納媒体、光ディスクもしくは光格納媒体、フラッシュメモリ、ホログラフィックメモリ、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、もしくは他の電子メモリデバイスもしくはチップもしくは動作可能に相互接続されたチップの組、格納された命令がインターネット／イントラネットもしくはローカル・エリア・ネットワークを介して検索され得るインターネットサーバ／イントラネットサーバなどのうちの１つ以上を含むことが意図される。一実施形態において、印刷ジョブ生成器４０のメモリ４６および電力制御システム３８のメモリ５４などの上記のメモリのそれぞれが、ランダム・アクセス・メモリと読み取り専用メモリとの組み合わせを備える。例示的なメモリは、例示的な方法を行うための命令と、例示的な方法において使用され生成されるデータとを格納し、また、それぞれのコンピュータを動作させるための命令を動作させる。
【００５７】
図２を参照して、マルチデバイス印刷システム１０における電力消費を減少させるために上記の手法を実装するために使用されることが出来るマルチデバイスシステムにおいて電力消費を減少させる方法が説明される。方法は１００で開始する。１０２において、システムのモデルが生成される。実行されるジョブが１０４において受信される。さらに、ジョブを実行するための印刷デバイス１２、１４のうちの一方の選択と、印刷デバイス１２、１４のうちの他の１つ以上のデバイスにジョブ１０を転送するための転送費用とが１０６において受信される。プロセッサを使用して、ジョブを実行するデバイスが、第１の費用関数の最適化（例えば、最小化）を介して１０８で決定される。第１の費用関数は、選択と転送費用とに基づく。ジョブは、１１０において、決定されたデバイスに割り振られ、プロセッサを使用して、マルチデバイスシステム１０における各デバイスに対するタイムアウトが、１１２において、第２の費用関数の最適化（例えば、最小化）を介して決定される。第２の費用関数は、システム１０に関する見込みの電力消費に基づく。デバイスは、１１４において、決定されたタイムアウトを提供される。方法は、受信された新たなジョブ毎に、１０４に戻ることが出来ると理解されるべきであるが、方法は、１６において終了する。
【００５８】
図２に説明された方法は、コンピュータ上で実行されてもよいコンピュータプログラム製品に実装されてもよい。コンピュータプログラム製品は、制御プログラムが記録（格納）される非一時的コンピュータ読取り可能な記録媒体、例えば、ディスク、ハードドライブなどを備えてもよい。非一時的コンピュータ読取可能な媒体の通常の形態は、例えば、フロッピー（登録商標）ディスク、フレキシブルディスク、ハードディスク、磁気テープ、もしくはその他任意の磁気格納媒体、ＣＤ−ＲＯＭ、ＤＶＤ、もしくはその他任意の光媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＦＬＡＳＨ‐ＥＰＲＯＭ、もしくは他のメモリチップまたはメモリカートリッジ、もしくは、その他任意のコンピュータが読み取ったり使用したりすることが出来る有形媒体を含む。
【００５９】
あるいは、方法は、伝送可能な搬送波などの一時的媒体に実装されてもよく、伝送可能な搬送波においては、制御プログラムは、無線波通信や赤外線データ通信の間に生成される伝送媒体などの音波または光波などの伝送媒体などを使用してデータ信号として体現される。
【００６０】
あるいは、方法は、１つ以上の汎用コンピュータ、専用コンピュータ、プログラミングされたマイクロプロセッサもしくはマイクロコントローラ、および周辺集積回路素子、ＡＳＣＩもしくは他の集積回路、デジタル信号プロセッサ、離散素子回路などのハードワイヤード電子回路もしくは論理回路、ＰＬＤ、ＰＬＡ、ＦＰＧＡ、グラフィカルカードＣＰＵ（ＧＰＵ）、もしくはＰＡＬなどのプログラマブル論理デバイスなどに実装されてもよい。概して、図２に示された流れ図を実装することが出来る有限状態機械を実装することが出来る任意のデバイスが、本方法を実装するために使用されることが出来る。
【００６１】
例示的なマルチデバイス印刷システム１０と方法とのさらなる詳細がここで記載される。
【００６２】
システムのモデル
例示的な印刷システム１０は、一組のデバイスとしてモデリングされ、それぞれのデバイスが、割り振られた費用、例えば、スリープモードや準備完了モードなどの様々な状態における電力消費費用や、デバイス間でジョブを転送するための（事前に決定された、および／またはユーザが割り振り可能な）転送費用を有する。システムモデル６２は、メモリ５４に格納されてもよく、またはシステムに格納されてもよい。モデル６４は、実行される新たなジョブに関するパラメータを入力された時には、デバイスの現在の状態と、それらの見込みの将来の状態とに基づいて（実行されるジョブに対する見込みの将来の要求に基づいて）、システム１０における全デバイスにわたって（すなわち、ジョブを行うことが出来る複数のデバイスに対して）、価値関数（エネルギー費用関数）に対する最適解を識別する。その解は、ジョブがシステム内の別のデバイスに転送されるべきか（そうである場合には、どのデバイスに転送されるべきか）、またはジョブが、ジョブチケットによってジョブが割り振られるデバイス上で実行されるべきかを示す。例示的なモデル６４はまた、ジョブの割り振り決定に従って、デバイスに対するタイムアウトをコンピュータ計算する。
【００６３】
電力消費を減少させる１つの手法は、制約された費用構造を有するマルコフ決定過程（ＭＤＰ）としてマルチデバイス印刷システム１０をモデリングすることである。ＭＤＰは、典型的には、最小費用を有する決定を識別することによって意思決定を容易にするために利用される。上記のように、電力消費は、印刷デバイスに対する印刷ジョブの割り振りとタイムアウトとを決定することによって最小化される。可能な決定のそれぞれが、マルチデバイス印刷システム１０を異なるシステム状態にし、異なるシステム状態への遷移のそれぞれは費用を含む。
【００６４】
マルチデバイス印刷システム１０の状態は、要求状態と制御状態とによって与えられる。要求状態は、マルチデバイス印刷システム１０に関して影響を与える少なくとも１つの可変の要求または負荷、例えば、時刻に対応する。その要求または負荷は、既知であると想定され、２つの確率変数の確率的挙動、次のジョブまでの時間（すなわち、到着間隔）、およびそのジョブに対するユーザのデバイス選択を決定する。これらの２つの確率変数に対する確率分布は、上で考察されたように決定される。制御状態は、システムにおける各印刷デバイスの動作モード、例えば、アイドルモードと省電力モードとのうちの一方に対応する。上記のように、各動作モードは、異なる電力消費レベルを有する。
【００６５】
各印刷ジョブに対して、２つの決定（または決断）が行われる。第１の決定は、受信された印刷ジョブをどの印刷デバイスに割り振るべきかであり、その決定は、印刷ジョブが電力制御システム３８によって受信された時に、電力制御システム３８によって特定のデバイスに割り振る前に行われる。そのような決定は、印刷ジョブチケットにおいて特定されたものとして選択された印刷デバイスを考慮する。第２の決定は、どのタイムアウトが印刷デバイス１２、１４に割り振られるべきであるかである。この決断は、印刷ジョブを割り振った後に、電力制御システム３８によって行われる。第１の決定とは対照的に、選択された印刷デバイスは、いつ決断を行うかを考慮に入れていない。
【００６６】
決断によって負わされる費用は、２種類のものであり得る。第１の種類の費用は、ジョブが割り振られた時に負わされ、（必要とされる場合には）割り振られた印刷デバイスをアイドルモードに遷移させる費用に加えて、見込みの転送費用が存在する場合には、それを含む。上で考察されたように、見込みの転送費用は、典型的には、印刷ジョブが作成された時に設定され、印刷ジョブチケットに含まれることが出来る。第２の種類の費用は、タイムアウトが設定された時に負わされ、アイドルモードにおける各デバイスでのタイムアウトによって誘発される累積費用を含む。デバイスの個々の費用は、タイムアウトまたは次のジョブまでアイドルモードにおいてデバイスを維持する諸経費に加えて、タイムアウトに実際に到達した場合にはデバイスを省電力モードにする費用を含む。スリープモードにおいてデバイスを維持する費用、または実際にジョブを行うための費用は、それらがいかなる決断によって負わされたかを考慮される必要はない。
【００６７】
一実施形態において、ＭＤＰは価値反復手順で解かれる。しかしながら、ＭＤＰを解くための他の手順もまた企図される。価値反復手順は、システムの各状態と関連付けるために見込みの費用（すなわち、その状態からの一連の全イベントに関する見込みの費用）をコンピュータ計算するダイナミックプログラミング技術である。見込みの費用は、典型的には、無限であるので、一実施形態においては、数列の区間は有界にされ、および／または指数関数的に、または別の方法で、時の経過に伴った、順序における異なるステップの寄与を減少させる割引係数が導入される。有界区間の使用が利用されることが出来るが、以下の解は割引係数を利用する。
【００６８】
価値反復手順を使用してＭＤＰを解くことに関する１つの問題点は、割り振りの直後に、ある状態の値をどのようにコンピュータ計算するか（すなわち、どのようにタイムアウトを決定するか）である。印刷デバイスの数と同じだけ多くの変数が存在し、各変数は１つのデバイスのタイムアウトを表す。さらに、印刷デバイスの数が少ない（例えば、１０個以下）と想定される時さえ、解は、依然として非常に複雑であり、標準的な最適化方法に解を修正可能である凸状などの有利な性質を有していない。一実施形態において、問題が、一次元最適化の有界数列に問題を換算することによって解かれることが出来る。
【００６９】
価値反復方法
価値反復手順と割引係数とを使用してＭＤＰを解くために、マルチデバイス印刷システム１０はＫ個の印刷デバイスを含むと仮定されることが出来、各印刷デバイスｋは、２つの動作モード（０または１）を有し、０は、スリープモードなどの省電力モードを表し、１は、省電力モードよりも大きな電力が消費されるモード、例えば、アイドルモードを表す。二値の動作モードの組が考察を容易にするために選択されたが、それぞれのモードがそれぞれの電力消費を有する、例えば、３つのモード、４つのモード、または５つのモードなどのさらなるモードも企図される。
【００７０】
各印刷デバイスｋが、アイドルモードにおける電力費用率
【数４】
0005918106.tif 000005
と、スリープ（省電力）モードにおける電力費用率
【数５】
0005918106.tif 000006
と、印刷デバイスが省電力モードにある時の省力率ａｋとを有するものと仮定する。費用率
【数６】
0005918106.tif 000007
およびａｋはそれぞれ、単位時間当たりの通貨単位、例えば、ドル／時間として表されることが出来るか、または他の同様な単位で表されることが出来、そしてメモリ５４に格納されることが出来る。省電力モードにおける電力消費は、アイドルモードの電力消費よりも少ないので、省力率ａｋは、
【数７】
0005918106.tif 000008
と等しい。さらに、各印刷デバイスｋに、アイドルモードから省電力モードへの遷移に対する費用
【数８】
0005918106.tif 000009
と、省電力モードからアイドルモードへの遷移に対する費用
【数９】
0005918106.tif 000010
とを与える。これらの費用は、費用率
【数１０】
0005918106.tif 000011
およびａｋに関して通貨単位で表されることが出来、そしてメモリ５４に格納されることが出来る。
【００７１】
ベクトル（Ｒｋ）１：ｋが生成されることが出来、各成分Ｒｋｈは、デバイスｋによって印刷されることが選択されたジョブをデバイスｈに転送する費用である。理解されるように、このベクトルは、転送費用に対応する。ジョブの現在の費用を決定する時に、特定の転送費用が利用されることが出来、例えば、ジョブチケットにおけるジョブ１６のサブミッタによって特定されることが出来る。見込みの費用を決定する時に、転送費用は、確率的に、または（全デバイスにわたる）システムの平均に基づいて決定されてもよい。ベクトルの成分Ｒｋｈは、デバイスｋがデバイスｈと同じである場合には（転送費用が不要なので）ゼロの値を有すると想定され、そうでなければ、非負であると想定される。
【００７２】
タイムアウトτの後にスリープモードに切り替えることが予定されると共に、期間ｘの間に、期間ｘの開始時に単一のジョブを割り当てられる、最初はアイドル（準備完了）モードの印刷デバイスｋによって生成された全費用は、抑え難い費用や諸経費ｇｋを含む。抑え難い費用は、ジョブ実行費用に加えて、デバイスが全期間の間で最も費用効果が高いモード（すなわち、省電力モード）にある場合にデバイスによって負わされる費用
【数１１】
0005918106.tif 000012
を含む。諸経費ｇｋは、期間ｘのうちの一部または全部の間にアイドルモードでデバイスを維持する費用であり、その費用は、タイムアウトτによって制御される。従って、最初はアイドルモードであり、期間ｘの開始時に単一のジョブを割り振られるデバイスｋに対する諸経費ｇｋは、下記のようにモデリングされることが出来る。
【数１２】
0005918106.tif 000013
【００７３】
ＩＩ［条件］は、括弧内の条件が真である時に１に戻り、そうでなければ０である。抑え難い費用は固定され、行われた決断によって影響を受けないので、諸経費ｇｋだけが考慮される。
【００７４】
マルチデバイス印刷システム１０は、順番に、印刷ジョブ１６などのジョブリクエストを受信する。順番がｎ番目の印刷ジョブに関して、Ｌｎ∈｛１：Ｋ｝が、印刷ジョブに対して選択されたデバイスの指数であると仮定し、
【数１３】
0005918106.tif 000014
が、先の印刷ジョブがデバイスインフラストラクチャに提出されてから経過した時間（すなわち、大域的な到着間隔）であると仮定する（ここで、
【数１４】
0005918106.tif 000015
は、正数を示す）。ｎ番目の印刷ジョブに選択されたデバイスＬｎは、転送により印刷ジョブを実行したデバイスではないかもしれない。確率変数（ＸＬ）ｎは、考えられる要求状態の任意の空間Ｚに存在する、観察された要求状態Ｚｎによって制御されるセミマルコフ動力学などの確率分布に従うことが想定される。
【００７５】
２つの定常確率分布Ｐ、Ｑは、その過程を定義し、それらは既知であることがさらに想定される。
【数１５】
0005918106.tif 000016
【００７６】
これらの方程式は、セミマルコフ仮定を表し、関連する２つの確率分布を明らかにする。それらは、最初の要求状態Ｚ０が与えられると、下記のように確率過程の生成モデルを記載する。
１  ｎ：＝１を設定する。
２  永遠に繰り返す：
３  Ｘｎ、Ｌｎを分布
【数１６】
0005918106.tif 000017
から引き出す。
４  Ｚｎを
【数１７】
0005918106.tif 000018
から引き出す。
５  ｎ＋＝１を設定する。
【００７７】
「定常」は、これらの分布Ｐ、Ｑが、電力制御システム３８によって行われた決断によって影響を受けないことを意味する。それらは、外部要求だけに対処し、これは、電力制御システム３８の作用とは独立すると想定される。全体的に、確率変数（Ｚ，Ｘ，Ｌ）ｎは、Ｐ、Ｑによって決定された完全なマルコフ動力学に従う。
【００７８】
セミマルコフ仮定を常に本質的に満たす要求状態に対する１つの（悪い）選択は、Ｚｎが要求の全履歴Ｚｎ＝（Ｘ，Ｌ）１：ｎであると仮定することである。従って、Ｑは、決定性（すなわち、ディラック分布）であり、Ｘｎ＝ｘ、Ｌｎ＝ｌ、およびＺｎ−１＝ｚが与えられると、Ｑは、ｚの終了時に（ｘ，ｌ）を追加することによって取得された履歴ｚ’にＺｎの全集団を集中させる。しかしながら、その場合、要求空間Ｚは扱いにくい。従って、扱いやすい要求空間Ｚと、セミマルコフ仮定を満たすモデルとの選択は用途に従う。例示的な実施形態において、決定性であっても決定性でなくてもよいＰ、Ｑに関して想定は行われないが、それらが既知であることが想定される。
【００７９】
マルチデバイス印刷システム１０をモデリングするために、ジョブ実行時間は僅かであることと、デバイスｋ上での実行のために選択されたジョブは、そのジョブがデバイスｋまたは何らかの他のデバイスのいずれかに受信されるとすぐに割り振られることとが想定される。任意の時間におけるマルチデバイス印刷システム１０の状態は、対＜σ１：Ｋ，ｚ＞によって与えられ、σ１：Ｋはシステム１０の制御状態であり、ｚはシステム１０の要求状態を示す。制御状態σ１：Ｋは、ｋ番目の成分がデバイスｋのモード（０または１）を保持する二値のベクトルである。
【００８０】
デバイスのうちの１つで実行されるジョブを受信することに応答して、２つの決断が行われる。ｈが選択されたデバイスの指数であると仮定する。第１の決断は、ジョブを受診するとすぐに行われ、第１の決断は、どのデバイスにジョブを割り振るべきかである。第２の決断は、システム１０が状態σである時に割り振りの直後に行われる。この決断は、非負のタイムアウトの集団（τｋ）ｋ∈σであり、各τｋは、デバイスｋに対するタイムアウト（すなわち、デバイスｋがジョブを割り振られていない場合に、デバイスｋが省電力モードに切り替えられる時間）を示す。
【００８１】
割引係数γを用いて無限区間における最適化を考慮する。Ｖｈ＜σ，ｚ＞とＶ＜σ，ｚ＞とが、割り振りの前後にそれぞれ状態＜σ，ｚ＞からの残りの見込みの最適費用であると仮定する。これらの費用に対する最適性方程式（すなわち、ベルマン方程式）は以下の通りである。
【数１８】
0005918106.tif 000019
【００８２】
ｅｋは、サイズＫのベクトルを示し、ｋ番目の成分は１に等しく、他の成分は０に等しい。
【００８３】
方程式（４）は、以下のように説明されることが出来る。デバイスｈに対するジョブが状態＜σ，ｚ＞において受信され、そのジョブが、デバイスｈではなく、デバイスｋに送信される場合には、残りの見込みの費用は、
１．Ｒｈｋ：見込みの転送費用（ｈ＝ｋの場合にはゼロ）
【数１９】
0005918106.tif 000020
２：必要な場合にデバイスｋを起動する費用（σｋ＝１の場合にはゼロ、すなわち、デバイスは既にアイドルモードにある）
３．Ｖ＜σ＋（１‐σｋ）ｅｋ，ｚ＞：同じ要求状態ｚと、デバイスｋが現在アイドルモードにある新たな制御状態とからの残りの見込みの費用（σｋ＝１である場合にはσに等しい、すなわち、デバイスは既にアイドルモードにある）
【００８４】
方程式（５）は、以下のように説明される。（ｎ−１）番目のジョブが割り振られた後の状態＜σ，ｚ＞において（従って、Ｚｎ−１＝ｚ）、タイムアウト（τｋ）ｋ∈σがアイドルデバイス（すなわち、σに属するデバイス）に適用される場合には、残りの見込みの費用は、以下の費用の確率変数Ｘｎ、Ｌｎ、Ｚｎに対する期待値（すなわち、方程式（２）および（３）によって定義された確率分布を有する確率変数の考えられる全ての値ｘ，ｌ，ｚ’に対する積分）である。
１．Σ（τｋ）ｋ∈σｇｋ（ｘ，τｋ）：方程式（１）によって定義されるように、現在アイドルモードの各デバイスに対するタイムアウトによって導かれる全諸経費。この項はｚ’に従わないので、この項は、その変数に対する積分から取得されることが出来る。
２．γＶｌ（σ’，ｚ’）：新たなジョブがデバイスｌ上で受信されたが、まだ割り振られていない時の、新たな状態＜σ’，ｚ’＞からの残りの割引費用。状態σ’はそのジョブが受信された時に依然としてアイドル状態であるデバイスからなり（すなわち、τｋ＞ｘであるｋ∈σ）、その状態は、
【数２０】
0005918106.tif 000021
として記載されることが出来る。
【００８５】
最適性方程式の換算
方程式（５）の最適化の問題は、制御変数τを変更することによって変換される。状態σにおいて、タイムアウトを割り振られる必要があるｒ＝Σｋσｋのデバイスが存在する。方程式（５）は、全てのｉ∈｛１：ｒ｝に対して、
【数２１】
0005918106.tif 000022
および
【数２２】
0005918106.tif 000023
であるように、τで、要素に関して分類された数列τ’１：ｒと、単射ｖ：｛１：ｒ｝→｛１：Ｋ｝とを与えることによって便利に特定されることが出来る。次に、最適化が、制御変数ｖ，τ’（利便性のために、τ’はτと改名される）を使用して再公式化される。
【数２３】
0005918106.tif 000024
【００８６】
τはここで、ｒ個の非減少成分を有するベクトルであり、σは目的から消滅したことが、方程式（６）において観察されることが出来る。ｖは、σのｒ非負成分の指数の順序であることだけが、制約に存在する。所与のτに関して、τをτ０＝０およびτγ＋１＝∞で拡張させる。全ての非負ｘに関しては、τは非減少であるので、τｉ−１≦ｘ＜τｉであるように単一のｉ∈｛１：ｒ＋１｝が存在する。さらに、その場合、全てのｊ∈｛１：ｒ｝に関して、全てのｊ∈｛１：ｒ｝は、ＩＩ［ｘ＜τｉ］＝ＩＩ［ｉ≦ｊ］を保持する。上記の方程式（６）を再公式化することが、下記を生じる。
【数２４】
0005918106.tif 000025
【００８７】
この最小化問題は、サイズｒの範囲における離散成分ｖと次元ｒにおける連続成分τとを有する。しかしながら、目的関数は、項ｒ＋１の合計であり、項ｒ＋１のそれぞれが、変数τｉ−１，τｉおよび
【数２５】
0005918106.tif 000026
の限られた部分集合を含む。これは、目的関数が一連の一次元最適化に変換されることが出来ることを示唆する。中間値関数
【数２６】
0005918106.tif 000027
が導入されることが出来、その中間値関数は、その一連の流れの間の異なるステップにおける価値関数であり、下記の通りに後退帰納的に定義された単一の追加パラメータｔ（非負数）を有する。
【数２７】
0005918106.tif 000028
【００８８】
任意のσ（ゼロ、または非ゼロ）に関して、下記が妥当性を有する。
【数２８】
0005918106.tif 000029
【００８９】
問題を解くための価値反復アルゴリズムは、以下の通りに実装されることが出来る。
手順  価値反復
１  Ｖを初期化する。
２  繰り返す。
３  方程式（４）を使用して各ｈ∈｛１：ｋ｝に対するＶｈをＶから更新する。
４  方程式（８）および（９）を使用して
【数２９】
0005918106.tif 000030
から
【数３０】
0005918106.tif 000031
を更新する。
５  方程式（１０）を使用して
【数３１】
0005918106.tif 000032
からＶを更新する。
６  安定するまで。
【００９０】
価値関数の伝播は、下記の通りに要約されることが出来る。
【数３２】
0005918106.tif 000033
【００９１】
解の表示
上記に関する１つの課題は、
【数３３】
0005918106.tif 000034
の帰納的定義は、τ≧ｔおよび
【数３４】
0005918106.tif 000035
に対してｔ，σ’における全ての値に従って、所与の要求状態ｚにおいて、ｔ，σにおける値をコンピュータ計算することである。有限で多数の
【数３５】
0005918106.tif 000036
が存在するが、無限で多数のτ≧ｔが存在する。この問題に対する解は、点別コンピュータ計算ではなく、関数空間における演算子に関する方程式の公式化を使用する。
【数３６】
0005918106.tif 000037
およびｖを下記のとおりに定義する。
【数３７】
0005918106.tif 000038
ここで、ｇσ（ｘ，ｔ）＝Σｋ∈σｇｋ（ｘ，ｔ）である。
【００９２】
変換方程式（８）、（９）、および（１０）は、下記をもたらす。
【数３８】
0005918106.tif 000039
【００９３】
この変換の目的は、ここで、点別の方程式が以下の関数方程式に簡単な方法で変換されることが出来ることである。
【数３９】
0005918106.tif 000040
【００９４】
ここで、
【数４０】
0005918106.tif 000041
という表記は、関数
【数４１】
0005918106.tif 000042
を示すために使用され、ｐは、何らかのパラメータ、またはそのタプルである。関数における演算子↓は、下記の通りに定義される
【数４２】
0005918106.tif 000043
【００９５】
価値関数の伝播はここで、一般的に、
【数４３】
0005918106.tif 000044
として、下記の方程式を用いて要約されることが出来る（括弧内の数字は、使用される方程式を示す）。
【数４４】
0005918106.tif 000045
【００９６】
ｚが与えられ、
【数４５】
0005918106.tif 000046
が、全σに対する初期関数
【数４６】
0005918106.tif 000047
からなる（有限の）組であると仮定する。コンピュータ計算可能な関数空間Ｆが識別され、その関数空間Ｆは、下記の特性を含む。
【数４７】
0005918106.tif 000048
【００９７】
そのような空間が与えられると、ｖ＜ｔ，σ，ｚ＞∈Ｆが、方程式（１６）および（１７）を使用してＦにおいて帰納的に構築されることが出来、Ｖは、最終的にはｖからコンピュータ計算されることが出来る。（Ａ）を満たす明白な空間Ｆが存在しない場合には、Ｆは先験的に選択されることが出来る。その場合、
【数４８】
0005918106.tif 000049
の要素と、演算子ｍｉｎ（ｆ，ｇ）および↓（ｆ‐ｇ）＋ｇとが、（Ａ）を満たす近似値によって置換される。近似値が考えられるそのような先験的な空間の典型的な例は、区分的な一定の関数の空間である。
【００９８】
解関数空間の選択
関数空間を選択するために、Ｆｃがｆ＋ｒ１の形態の関数の組であると仮定し、ここで、
【数４９】
0005918106.tif 000050
およびｒは、任意のスカラである。さらに、Ｆ＊が区分的Ｆｃである関数の空間（すなわち、
【数５０】
0005918106.tif 000051
の形態の関数の空間であり、（ｆｋ）ｋ∈Ｋは、Ｆｃにおける関数の有限の集団であり、（Ａｋ）ｋ∈Ｋは、実際の正数
【数５１】
0005918106.tif 000052
の組の間隔分割である）とする。下記の仮定が、
【数５２】
0005918106.tif 000053
が妥当性を有する場合には、Ｆ＊は、想定（Ａ）を満たし、上記の処置に受け入れ可能であることが示されることが出来る。
【数５３】
0005918106.tif 000054
において、Ｔは＋∞に等しくてもよいことを留意されたい。ここで、想定（Ａ＊）は、やや軽いことが観察される。実際に、２つの関数、ｆ、ｇ∈Ｆｃを考慮し、ｈ＝ｆ‐ｇと仮定する。＝Ｉを、２つの関数が所与の間隔Ｉで同じである時に２つの関数間で保持する（等しい）関係を意味することを仮定する。
【００９９】
ＩＩ［ｈ（ｔ）≧０］が、ｔにおいて区分的定数である場合には、仮定
【数５４】
0005918106.tif 000055
は妥当性を有する（すなわち、ｈが、各各間隔において、均一的に負であるか、または均一的に非負であるかいずれかであるように、
【数５５】
0005918106.tif 000056
の間隔分割が存在する）。実際に、ｈが間隔Ｉにおいて負である場合には、ｍｉｎ（ｆ，ｇ）＝Ｉｆ∈Ｆｃであり、ｈが間隔Ｉにおいて非負である場合には、ｍｉｎ（ｆ，ｇ）＝Ｉｇ∈Ｆｃである。従って、ｍｉｎ（ｆ，ｇ）は、区分的Ｆｃであり、Ｆ＊に存在する。さらに、分割の間隔の境界はコンピュータ計算されることが出来、境界は、ｈの不連続点、またはｈ（ｔ）＝０である点のいずれかである。ｍｉｎ（ｆ，ｇ）をコンピュータ計算する説明のために図３を参照されたい。
【０１００】
ｈが、有限の多数の不連続点だけを有し、ＩＩ［∃τ＞ｔｈＴ（ｔ）＜ｈＴ（ｔ）］が、ｔにおいて区分的定数である場合には、想定
【数５６】
0005918106.tif 000057
もまた妥当性を有し、ｈＴ＝１［０，Ｔ］ｈである。実際に、一定である間隔Ｉを考慮する。これらの間隔のうちの１つは、ｈＴ＝Ｉ０であるＩ＝［Ｔ，＋∞］であるので、↓ｈＴ＋ｇ＝Ｉｇ∈Ｆｃである。ここで、Ｉ⊂［０，Ｔ］が与えられる。普遍性を失うことなく、ｈは、Ｉ上で連続的であると想定する（そうでなければ、不連続点でＩを分割する）。全てのｔ∈Ｉおよびτ＞ｔに関して、ｈＴ（τ）≧ｈ（ｔ）が真である場合には、↓ｈＴ（τ）＝ｈ（ｔ）＝ｆ（ｔ）−ｇ（ｔ）であるので、↓ｈＴ＋ｇ＝Ｉｆ∈Ｆｃである。一方、全てのｔ∈Ｉに関して、ｈＴ（τ）＜ｈ（ｔ）であるようにτ＞ｔが存在する場合には、↓ｈＴがＩに関して一定であることを示すことは容易である。
【０１０１】
従って、↓（１［０，ｔ］（ｆ−ｇ））＋ｇが区分的ＦｃであるのでＦ＊に存在する。間隔の境界はコンピュータ計算するのがわずかに困難である。コンピュータ計算は、本質的に、ｈの不連続点、ｈの局所的な最小値、および局所的な最小値の値が到達する点の識別を必要とする。↓（１［０，ｔ］（ｆ−ｇ））＋ｇをコンピュータ計算する説明のために図４を参照されたい。
【０１０２】
実装
想定（Ａ＊）が妥当性を有する場合には、ｖ（ｔ，σ，ｚ）を取得するために必要とされるＦ＊における全コンピュータ計算がσ’、σ’’⊂σ（初期関数の相違）を有する形態
【数５７】
0005918106.tif 000058
の関数の空間
【数５８】
0005918106.tif 000059
において行われることが出来る。そして、このコンピュータ計算は、完全に、２つの手順ＳＩＧＮ（ｈ，ｒ）およびＧＬＭＢ（ｈ，ｒ）に基づくことが出来、
【数５９】
0005918106.tif 000060
および
【数６０】
0005918106.tif 000061
である。ＧＬＭＢという用語は、「最大下位単調境界」を意味する。
【０１０３】
両方の手順は、実際の正数
【数６１】
0005918106.tif 000062
の有限間隔分割を戻す。分割における各間隔Ｉに関して、ＳＩＧＮ（ｈ，ｒ）は、１Ｉ（ｈ‐ｒ１）≧０である場合には、インジケータ＋１を戻すか、または１Ｉ（ｈ‐ｒ１）≦０である場合には、インジケータ−１を戻す。さらに、分割における各間隔Ｉに関して、ＧＬＭＢ（ｈ，ｒ）が、実際に一定である場合には、ＧＬＭＢ（ｈ，ｒ）は、↓（１Ｉ（ｈ−ｒ１））＝Ｉｃであるように一定のスカラｃを戻すか、または↓（１Ｉ（ｈ−ｒ１））＝Ｉｈ−ｒ１である場合には、特別なインジケータ⊥を戻す。両方の手順は、大まかな意味では「同質である」と考えられることを留意されたい。任意の定数αに関して、ＳＩＧＮ（αｈ，αｒ）およびＧＬＭＢ（αｈ，αｒ）は、ＳＩＧＮ（ｈ，ｒ）およびＧＬＭＢ（ｈ，ｒ）それぞれから導き出されることが出来る。厳密には、これは、α＜０である時には手順ＧＬＭＢに関してはあまり明白ではないかもしれないが、簡潔にするためにここでは省かれた、その手順のわずかにより対称的な定義は、手順を完全に同質にする。
【０１０４】
（簡潔にするために）
【数６２】
0005918106.tif 000063
におけるすべての関数が連続的であると想定すると、次に、両方の手順が、
【数６３】
0005918106.tif 000064
であるＢＥＨＡＶＩＯＲ（ｈ）手順と、
【数６４】
0005918106.tif 000065
および
【数６５】
0005918106.tif 000066
であるＥＶＡＬ（ｈ，ｔ）手順とを使用して実装されることが出来る。
【０１０５】
ＢＥＨＡＶＩＯＲ（ｈ）は、
【数６６】
0005918106.tif 000067
の有限間隔分割を戻し、分割の各間隔Ｉに関して、ｈが非減少である場合には、インジケータ＋１を戻し、ｈが非増加である場合には、インジケータ−１を戻す。ＥＶＡＬ（ｈ，ｔ）は、値ｈ（ｔ）を戻すか、またはｔ＝＋∞の場合には、ｈの漸近線を戻す。例えば、ＳＩＧＮ（ｈ，ｒ）は、以下のアルゴリズムを用いて以下で示されるように実装されることが出来る。
手順  ＳＩＧＮ（ｈ，ｒ）：
１  Ｐを空の間隔分割とする。
２  Ｔ：＝＋∞とする。
３  ｓをＥＶＡＬ（ｈ，Ｔ）−ｒの標識（＋１または−１）とする。
４  減少する順序におけるＢＥＨＡＶＩＯＵＲ（ｈ）における各間隔［ｕ，ｖ］に関して、
５  ｓ’をＥＶＡＬ（ｈ，Ｔ）−ｒの標識（＋１または−１）とする。
６  ｓ≠ｓ’である場合には、
７  二分することによって［ｕ，ｖ］上のｈ−ｒ１の根ｔをコンピュータ計算する。
８  インジケータｓを用いてＰに間隔［ｔ，Ｔ］を追加する。
９  ｓ：＝ｓ’およびＴ：＝ｔとする。
１０  インジケータｓを用いてＰに間隔［０，Ｔ］を追加する。
１１  Ｐを戻す。
【０１０６】
６行目において、条件が満たされた場合には、ｈ−ｒ１は、［ｕ，ｖ］の間に、標識を変更し、そして、手順ＢＥＨＡＶＩＯＲの定義によって、根はこの間隔の間単調であるので、根は固有である。７行目において根は二分することによってコンピュータ計算され、これは、利用可能な下位のプレディクタＥＶＡＬに依存するだけである。しかしながら、７行目における根のコンピュータ計算は、任意の数値法または分析法によって行われることが出来ることが理解されるべきである。例えば、根は、ニュートン−ラプソン法などの高位のプレディクタを使用してコンピュータ計算されることが出来る。手順ＢＥＨＡＶＩＯＲ（ｈ）は、手順が戻る分割の各間隔Ｉと追加の情報を関連付けることが出来る場合には、そのような方法もまた最適化されることが出来る。例えば、凸性行為がニュートン−ラプソン法を最適化するために使用されてもよいが、当然、分割自体は、単調性として改善される必要が有ってもよく、凸性が同じ間隔で同時に起こらない可能性がある。手順ＳＩＧＮのステップは、図３に続いて生じやすい。手順ＧＬＭＢの同様な段階的な定義は、図４を観察することによって考え出されることが出来る。
【０１０７】
モデルの初期化
要求を導き出す分布に関するいくつかのさらなる想定を用いて、
【数６７】
0005918106.tif 000068
における関数は、仮定の分析を簡略化する通常の形態を有する。
【数６８】
0005918106.tif 000069
【０１０８】
ｚが与えられると、ｘおよびｌは独立し、そして、ｚｌが与えられると、ｚ’は、ｘから独立する。想定
【数６９】
0005918106.tif 000070
の下で、
【数７０】
0005918106.tif 000071
は、下記の形態のものであることが示されることが出来る。
【数７１】
0005918106.tif 000072
ここで、ａσ＝Σｋ∈σａｋ、
【数７２】
0005918106.tif 000073
であり、そして
【数７３】
0005918106.tif 000074
は下記の通りに定義される。
【数７４】
0005918106.tif 000075
【０１０９】
前者が連続的である場合にはいつでも、ψ’は、実際にψの導関数であることを留意されたい。方程式（３４）は、解空間
【数７５】
0005918106.tif 000076
は、
【数７６】
0005918106.tif 000077
によって広げられた関数空間に含まれることを意味する。手順ＳＩＧＮおよびＧＬＭＢが同質であるので、ψ＋ｃψ’の形態またはψ’単独の形態の関数に関して手順をどのようにコンピュータ計算するかを知ることで十分である。
【０１１０】
意思決定を簡略化する特別な特性を有するいくつかの例が、以下に記載される。
【０１１１】
１．単一のデバイス
システム１０が単一の印刷デバイスだけを含むと仮定する。理解されるように、この例は、方法の適用可能性を示し、例示的なマルチデバイスシステムを表すことを意図していない。そのようなシステムにおいて、ジョブの割り振りに対する代替案は存在しない。さらに、２つの制御状態０または１だけが存在するが、省電力モードは割り振りの直後（すなわち、単一のデバイスがアイドルモードにある時）に予定されることだけを必要とするので、状態１だけが関心のある状態である。次に、最適化問題は、以下の方程式に簡略化される。価値関数の伝播がＶ→Ｖとして要約されることが出来る。
【数７７】
0005918106.tif 000078
【０１１２】
所与の要求状態ｚにおいて、上記の最小化問題は、分布Ｑに依存せず、考えられる次の状態に対する積分から外れることが観察されることが出来る。言い換えると、最適化は、各要求状態において独立して行われることが出来、一区間の区間においてのみ行われることが出来る。価値関数の実際のコンピュータ計算は、関心のあるものではなく、所与の要求状態ｚにおける最適なタイムアウトの予定は、上記の最小化目的によって直接的に取得され、その最小化目的は、（ｚを省略して）下記のように書き換えられることが出来る
【数７８】
0005918106.tif 000079
【０１１３】
従って、下記が妥当性を有する。
【数７９】
0005918106.tif 000080
【０１１４】
方程式（３３）は、分布Ｐが密度ｆ（すなわち、ｄＰ（ｘ）＝ｆ（ｘ）ｄｘ）を有すると共にＦがＰの累積密度であると想定すると、単に目的の導関数を取り消すことによって取得される。
【０１１５】
２．無記憶プロセス
この例においては、Ｐは、単一の要求状態下での指数関数であるので、Ｑは自明であり、要求状態は式においては省略されることが出来る。Ｐは下記の通りに表されることが出来る。
【数８０】
0005918106.tif 000081
ここで、Σｌπｌ＝１である。
【０１１６】
これは、ジョブリクエストが、速度λのポアソン分布プロセスに従って到着し、各リクエストは、デバイスに対するパラメータπの多項式に従って独立して送られることを想定する。あるいは、そして同様に、任意の１つのデバイスＩに対するリクエストは、速度λπｌのポアソン分布プロセスに従って到着し、デバイスは独立している。想定
【数８１】
0005918106.tif 000082
は、結果
【数８２】
0005918106.tif 000083
を保持する。
【０１１７】
方程式（１７）から理解されることが出来るように、定数−ａσ／λは、その定数が、σ＝０であるときにはゼロであり、そうでなければ無関係であるので、
【数８３】
0005918106.tif 000084
に落とされることが出来ることを留意されたい。従って、空間
【数８４】
0005918106.tif 000085
は、ｅｘｐ（−λ）だけによって広げられる一次元関数空間に含まれる。
【０１１８】
任意のスカラａに関して、
【数８５】
0005918106.tif 000086
であることが示されることが出来る。
【０１１９】
これは、下記の簡略化された方程式をもたらす。
【数８６】
0005918106.tif 000087
【０１２０】
無記憶プロセスの場合における価値関数の伝播は、方程式（４０）および（４１）を用いてＶ→Ｖ１：ｋ→Ｖとして要約されることが出来る。
【０１２１】
Ｖ，Ｖ１：Ｋがこれらの方程式を満たす場合には、最適な制御が下記の通りに取得される。
・デバイスｈ上でジョブリクエストを受信する際の状態＜σ＞において、方程式（４０）の最小値がｋにおいて到達されるようにデバイスｋにジョブリクエストを割り振る。
・割り振り後の状態＜σ＞において、方程式（４１）の最小値がσ’において到達されるようにシステムの制御状態の値（σ’⊂σ）を見出し、現在その状態に対応するモードにある（ｋ∈σ’）全てのデバイスに対してはτｋ＝∞において、そして、その状態に対応するモードではない（ｋ∈σ／σ’）他の全てのデバイスに対してはτｋ＝０においてスリープモードに切り替えることを予定する。
【０１２２】
３．部分的に明らかにされたプロセス
分布ＰおよびＱは、要求プロセスのドライバである。数列
【数８７】
0005918106.tif 000088
が与えられ、下記の通りに、分布Ｐ’およびＱ’によって導出された要求プロセスの変化形を考慮する。変化系の状態空間は、
【数８８】
0005918106.tif 000089
であり、そして、全ｉ∈｛１：Ｎ｝に対しては、
（１）
【数８９】
0005918106.tif 000090
は、（ｘｉ，ｌｉ）上に全集団を集める。さらに、ｚ∈Ｚに対して、
【数９０】
0005918106.tif 000091
である。
（２）
【数９１】
0005918106.tif 000092
は、
ｘｌに依存せず、状態ｉ＋１上に全集団を集め、ここで、表記を簡略化するために、ｚｎ＋１∈Ｚで識別された状態Ｎ＋１が導入される。さらに、ｚ∈Ｚに対して、
【数９２】
0005918106.tif 000093
である。
【０１２３】
言い換えると、Ｐ’，Ｑ’は、Ｎ個の第１の項目が規定されるプロセスを駆動し、残りのものがＰ、Ｑによって駆動される。要求状態ｚ∈Ｚにおける最適な価値関数は、元々のプロセスＰ、Ｑとその変化形Ｐ’、Ｑ’との下では同一である。従って、規定された要求状態ｉ∈｛１：Ｎ｝だけが関心のあるものである。これらの状態において、想定
【数９３】
0005918106.tif 000094
は妥当性を有し、下記をもたらす。
【数９４】
0005918106.tif 000095
【０１２４】
任意の非減少関数ｆに関して、
【数９５】
0005918106.tif 000096
であることが示されることが出来る。
【０１２５】
これは、下記の簡略化された方程式をもたらす。
【数９６】
0005918106.tif 000097
【０１２６】
次に、部分的に明らかにされた場合に対する価値関数の伝播が、方程式（４５）および（４６）を用いてＶ→Ｖ１：ｋ→Ｖとして要約されることが出来る。
【０１２７】
Ｖ、Ｖ１：ｋがこれらの方程式を満たす場合には、最適な制御が下記の通りに取得されることが出来る。
・デバイスｈに対するジョブリクエストを受信する際の状態＜σ，ｉ＞において、方程式（４６）における最小値がｋにおいて到達されるようにデバイスｋにジョブリクエストを割り振る。
・割り振り後の状態＜σ，ｉ＞において、方程式（４７）における最小値がσ’において到達されるようにσ’⊂σを見出し、全てのデバイスｋ∈σ’に対してτｋ＝∞において、そして、全てのデバイスｋ∈σ＼σ’に対してτｋ＝０においてスリープモードに切り替えることを予定する。
【０１２８】
４．ワイブル要求
この例において、Ｐは、単一の要求状態の下で、ワイブル分布となるように考慮されるので、Ｑは自明であり、要求状態は、式において省略されることが出来る。Ｐは、下記の通りに表されることが出来る。
【数９７】
0005918106.tif 000098
ここで、Σｌπｌ＝１である。
【０１２９】
さらに、想定
【数９８】
0005918106.tif 000099
は、下記をそのままにして保持する。
【数９９】
0005918106.tif 000100
【０１３０】
γは、不完全なガンマ関数を示し、Ψは関数
【数１００】
0005918106.tif 000101
を示す（従って、ｋだけに依存する）。再スケーリングするまで、
【数１０１】
0005918106.tif 000102
における関数は、指数関数的な形状を有するΨ’、または図５に示される異なる形状を想定することが出来ると共に、ｋ≠１である時に下記の特徴を有するΨ＋ｃΨ’のいずれかの形態のものである。
（１）それらの関数は、常に継続的であり、０において値ｃを有し、
【数１０２】
0005918106.tif 000103
によって与えられた無限大において制限を有する。
（２）それらの関数は、ｃ≦０の場合には単調に増加し、そうでなければ、それらの関数は、ｋ＞１である場合には最大であり、ｋ＜１である場合には最小である
【数１０３】
0005918106.tif 000104
において、単一の局所的な最適条件を有する。
（３）それらの関数は、ｃ≦０でありｋ＜１である場合には凹性であり、そうでなければ、それらの関数は、単純な多項式
【数１０４】
0005918106.tif 000105
の単一の変曲点の解を有する。
【０１３１】
ここで、方程式は単純化されないが、原始関数ＢＥＨＡＶＩＯＲおよびＥＶＡＬはコンピュータ計算することが容易である。従って、手順ＳＩＧＮおよびＧＬＭＢ、従って、方程式（１９）〜（２３）を満たす各制御状態σに対する関数ｖ＜・，σ＞およびスカラＶｋ＜σ＞は、コンピュータ計算することは容易である。全ての関数は、２つの係数、すなわち関数が及ぶ空間におけるΨおよびΨ’に関するものによって単純に（区分的に）表される。次に、最適な制御が以下の通りに取得されることが出来る。デバイスｈ上でジョブリクエストを受信する際の状態＜σ＞において、方程式（４）の最小値がｋにおいて到達されるようにデバイスｋにジョブリクエストを割り振る。割り振り後の状態＜σ＞において、σの要素の数列を見出し、方程式（１４）における最小値が到達されるタイムアウト値τを整合させ、初期化としてｔ＝０で方程式（１３）を使用し、次のステップにおけるｔの値として数列において各ステップにおけるτの値を報告する。
【０１３２】
５．他の要求分布
多くの他の要求分布は、上記のワイブル分布の例と同じ方法で取り扱われることが出来る。上記の分布の例は、以下を含む。単一の要求状態が存在する（従って、Ｑは自明であり、要求状態は式においては省略されることが出来る）。そして、
【数１０５】
0005918106.tif 000106
は妥当性を有し、それは、本質的に、要求がは独立して大域的なジョブフローを生成して、デバイス間の一定の多項式に従ってやはり独立して各ジョブを送ることを意味する。関数ψ’は、本質的には、Ｐと関連付けられる補完的な累積分布関数であり、多くの場合に分析形態を有する。関数ψはψ’の積分によって取得される。分析形態は、ワイブルの場合のように、ψに対して利用可能である場合には、関心のある関数に対する、形態ψ＋ｃψ’の原始関数ＢＥＨＡＶＩＯＲおよびＥＶＡＬのコンピュータ計算が、分析的にか、または（一次元における）いくつかの単純な数値法を使用してかのいずれかで解かれることが出来る。ψが分析形態を有さない場合には、ψは積分の概算によって点別に依然としてコンピュータ計算され、数値法に当てはめられることが出来る。
【０１３３】
例示的な実施形態の範囲を限定することを意図することなく、以下の例示的な実験例は方法の利用可能性を説明する。
【実施例】
【０１３４】
１．模擬要求実験
模擬要求を使用して実験を行なった。この実験は、以下のステップ（ｉ）ψおよびψ’が分析形態を有する分布Ｐだけでなく、送るための何らかの任意の多項式分布πを選択することと、（ｉｉ）長さＴであるＮ個の要求数列を生成することにより、何らかの所与の要求状態において開始することと、（ｉｉｉ）要求Ｐ、πの下で様々な方策の価値関数をコンピュータ計算することと、（ｉｖ）Ｎ個の数列のそれぞれに対して、その数列が明らかにされた時に、各方策の変化形をコンピュータ計算することと、（ｖ）Ｔ個のステップのそれぞれにおいて、２種類の方策（明らかにされていないもの、および明らかにされたもの）によって生成された費用をコンピュータ計算することと、（ｖｉ）Ｎ個の数列全体にわたる費用を平均することとを含んだ。結果として得られるＴ個の（累積）費用が描かれることが出来、各方策に対して、Ｔまでの未来関数が既知である時のその方策と、既知ではない時のその方策との間のリグレット関数を示す。あらゆる場合において、明らかにされた方策が元々の関数よりも悪くはない関数を行うことが予期される。
【０１３５】
上記のようにコンピュータ計算された最適な方策である転送方策と、各デバイスが別個に、（上記の単一のデバイスの場合に関して）他のデバイスから独立してデバイス自体の最適化を実装する利己的方策との２つの方策を利用した。利己的方策は、大域的要求から容易にはコンピュータ計算されない。実際に、大域的要求プロセスは、デバイス固有の要求プロセスを誘発し、そのデバイス固有の要求プロセスは、大域的な要求プロセスとは非常に異なるものであってもよく、容易にコンピュータ計算可能ではないものであってもよい。概して、デバイスｌに対する要求プロセスは、大域的要求の順序ｎの自己畳込みの幾何学的な重みπｌ（１−πｌ）ｎを有する無限混合として取得される。しかしながら、速度λを有する指数関数的な大域的要求の場合において、コンピュータ計算は簡略化され、デバイスｌに対する個々のデバイスの要求もまた、速度πｌλを有する指数関数である。その場合、２つの方策である転送方策と利己的方策とを比較することが可能である。
【０１３６】
結果が図６〜９に示される。図６および図７の図は、低転送費用と高転送費用とをそれぞれ有する２つの方策に対する累積費用を示す。図６を参照すると、実線は転送方策に対応し、破線は利己的方策に対応し、短い破線と長い破線とは、利己的方策と転送方策との両方に対する部分的に明らかにされた変化形に対応する（すなわち、累積費用は同じである）。図７を参照すると、破線は利己的方策と転送方策との両方に対応する（すなわち、累積費用は同じである）。短い破線と長い破線とは利己的方策と転送方策との両方に対する部分的に明らかにされた変化形に対応する（すなわち、累積費用は同じである）。論理的には、元々の方策のそれぞれに対してそのような１つの変化形があるが、それらは、ほぼ同一であり、図上では区別することが出来ない。さらに詳細には、２つの変化形は、元々の方策が顕著であるときには、数列の終わりにおいてわずかに異なるが、この相違は、実際の要求の認識が引き継ぐ、数列における早い段階で迅速に消去される。図８および図９の図は、低転送費用と高転送費用とのそれぞれに関して、順序の終了時における、割り振り費用（許可された場合には、起動費用に加えた転送費用）とタイムアウト費用（スリープモードに切り替える費用に加えた、準備完了モードにおけるエネルギー消費）との間の費用の乖離を詳細に述べる。これらの割り振り費用は、細切れにされた長方形として示される。（垂直な線によって識別される）満たされた棒は、元々の方策のためのものであり、白い棒は、その方策の部分的に明白にされた変化形のためのものである。
【０１３７】
２．実際の要求実験
実際の要求データを使用して別の実験を行なった。この実験は、下記のステップ、（ｉ）大域的要求モデルをデータに適合させることと、（ｉｉ）この要求モデル下で転送方策の価値関数をコンピュータ計算することと、（ｉｉｉ）デバイスのそれぞれに対して、そのモデルに対応するデータに個々の要求モデルを適合させることと、（ｉｖ）デバイスが単独であることを想定して、その要求モデル下で利己的方策の価値関数をコンピュータ計算することと、（ｖ）利用可能なデータに関して転送方策の費用と利己的方策の費用とをコンピュータ計算することとを含んだ。模擬データとの主な相違は、ここで、大域的要求モデルと、各デバイスに対する個々のモデルとが、同じ集団（例えば、ワイブル）から選択されることが出来ることである。なぜならば、それらのモデルは両方とも、いずれにしても正確ではない可能性が非常に高いからである。
【０１３８】
低転送費用と高転送費用とのそれぞれに関して、結果が図１０および１１に示される。データは、１ヶ月にわたって、最も使用される３つのデバイスだけが保有される実際のインフラストラクチャから取得された約３６００のジョブからなる。それぞれの日の最初のジョブは、その到着時間、典型的には前日の夜からの到着時間および典型的には異常値が数えられないように除去される。有用な手段が、転送方策の費用に対する利己的方策の費用の比である「利得」によって与えられる。利得は、２つの係数の関数として図１２に描かれる。（対数尺度における）転送係数が、転送費用行列Ｒに倍数的に適用される。その係数が小さくなる時には、転送費用が減少し転送によってより高い利得を可能にする。（やはり対数尺度である）電力係数は、消費費用速度ベクトルａに倍数的に適用される。係数が小さくなる時には、消費が減少し、全デバイスに対するより長いタイムアウトを可能にし、利得を増加させる。
【０１３９】
本開示は、マルチデバイス印刷システム１０に関して記載されてきたが、本開示は他の用途計画に用途を見出すことが理解される。例えば、本開示は、在庫管理システムに適用されることが出来、在庫管理システムにおいては、印刷デバイス１２は、ある費用で取替え可能な、在庫における品物と置換され、電力消費は維持費に対応し、品物がないことに対する不利益は無限大である（これは、ジョブをすぐに実行することに関する制約に対応する）。さらに、単一の項目が複数の要求に役立つことが出来るので、項目に関する２つ以上の構成単位に対する必要性は存在せず、おそらくは費用で構成単位を捨てる選択肢が存在する。
【０１４０】
さらに、本開示は電力消費に関して記載されたが、本開示はエネルギー消費に対してさらに広範囲に適用可能であることが理解される。本明細書において使用されるように、「エネルギー」という用語は消費される電力の量である。対照的に、電力は、エネルギー消費の速度である。印刷システムに関して、エネルギー費用は、印刷ジョブを完了するために使用される電力の量、紙、インク／トナー、および取替が必要な他の資源を作るエネルギー費用などを含む。例えば、より軽い紙に印刷することは、エネルギーを節約する。なぜならば、厚い紙は、製造するためにより多くのエネルギーを必要とするからである。従って、本開示は、消費可能な構成要素（例えば、インク、紙など）などの、プリンタの構成要素を製造するエネルギーを含み、最も少ないエネルギー量を使用するように、印刷ジョブを転送し、タイムアウトを最適化することが出来る。
【図１】
0005918106.tif 000116
【図２】
0005918106.tif 000117
【図３】
0005918106.tif 000118
【図４】
0005918106.tif 000119
【図５】
0005918106.tif 000120
【図６】
0005918106.tif 000121
【図７】
0005918106.tif 000122
【図９】
0005918106.tif 000123
【図１０】
0005918106.tif 000124
【図１１】
0005918106.tif 000125
【図１２】
0005918106.tif 000126
【図８】
0005918106.tif 000127