(57)【特許請求の範囲】
【請求項１】
ネットワークを介して分散されたサービスによって実行されるジョブでありかつプロダクトをもたらすジョブを実行するための分散ドキュメントハンドリングシステムであって、
相互接続されたいくつかの処理装置に分散されたサービスからなるサービスプールと、
ジョブによって届けられるべきプロダクトを指定するプロダクト仕様を含むジョブ仕様を入力するための手段と、
プロダクト仕様に従ってジョブを実行するのに適した、サービスプールから選択されたサービスからなる、少なくとも２つのサービスを含むサービスパスを決定するための手段とを備え、
ジョブ仕様が、さらに、プロダクトに影響を与えることのない状況に応じた制約を指定する仕様を備え、
サービスのパスを決定するための手段が、該ジョブについて、状況に応じた制約を考慮に入れることを特徴とする分散ドキュメントハンドリングシステム。
【請求項２】
状況に応じた制約が、指示された範囲における制限を規定し、
システムが、さらに、状況に応じた制約の指示範囲に基づいて、ジョブを実行するのに適切なパスを順序づけるための手段と、ユーザが、順序づけられたパスに基づくジョブ仕様の順序づけられたリストから所望のジョブ仕様を選択するためのユーザインタフェース手段とを備えたことを特徴とする請求項１に記載の分散ドキュメントハンドリングシステム。
【請求項３】
システムが、パスの順序づけにおいて使用されるべき状況に応じた制約をユーザが選択するためのユーザインタフェース手段を備えたことを特徴とする請求項１または２に記載の分散ドキュメントハンドリングシステム。
【請求項４】
状況に応じた制約が、実行されるべきジョブの合計料金であり、
システムが、決定されたパスに含まれるサービスの料金属性から合計料金を計算する手段を備えたことを特徴とする請求項２に記載の分散ドキュメントハンドリングシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ジョブを実行するための分散ドキュメントハンドリングシステムに関し、ここでは、ジョブは、ネットワークに分散されたサービスによって実行され、かつ、ジョブは、プロダクトをもたらし、前記システムは、相互接続された多くの処理装置に分散されたサービスプールと、ジョブによって届けられるべきプロダクトを指定するプロダクト仕様を備えたジョブ仕様を入力するための手段と、プロダクト仕様に基づいてジョブを実行するのに適切なサービスのパスを決定するための手段とを備え、前記サービスは、サービスプールから選択される。
【０００２】
サービスのパスという用語は、要求されたジョブを実現するのに必要な一組のサービスを表現するのに使用され、それらは、必ずしも、順次に実行される一組のサービスではなく、並行して実行されなければならないサービスを含むこともある。
【０００３】
【従来の技術】
ディジタル技術の出現によって、ディジタル複写機が、実現可能なものとなった。基本的には、ディジタル複写機は、ハードコピー画像を電子的な画像に変換するスキャナと、電子的な画像をハードコピー画像に変換するプリンタとを備える。スキャナとプリンタとの間では、画像は、電子的なディジタル画像として利用することができる。以前には実現できなかった様々な機能をディジタル複写機に与える能力を提供するのは、まさに、この特徴である。ディジタル技術のおかげで、複写機は、ジョブのキューイング、電子的なｒｄｆ、電子的な画像にディジタル信号処理を施すことによる画質改善、画像の編集、パターン認識処理などのような、現在可能となったあらゆる種類の機能によって向上した。
【０００４】
さらに、これらの装置は、電子的な画像を送受信することができ、それによって、そのような複写機は、ホストコンピュータから受信した画像を印刷するためのプリンタとして使用されてもよく、あるいは、他のファクシミリ装置と画像を交換するためのファクシミリ装置として使用されてもよい。
【０００５】
また、近年、別の装置で画像を処理し、その後に、処理した画像を発信元の再生装置へ返送して印刷するために、印刷ジョブ画像を一方の再生装置から他方の再生装置へ交換する通信機能を使用することが知られるようになった。
【０００６】
そのような通信機能が、ＳｈａｒｐのＥＰ−Ａ０７９７３４４に記載されている。Ｓｈａｒｐは、互いに通信を行うように適切に接続された複数の画像形成装置を備えた分散ドキュメントハンドリングシステムを説明している。それぞれの画像形成装置は、画像処理機能を実行するいくつかのサービスを備える。Ｓｈａｒｐによって開示されたものは、装置が、通信装置を介して、画像情報をお互いに交換することのできるシステムである。上述したシステムに示されるように、動的な分散環境において、サブタスクを実行するいくつかのサービスをリンクすることによって、タスクを実行することができる。しかしながら、そのような環境においては、より多くのサービスが利用可能になればなるほど、それだけ、より多くのサービスの組み合わせが可能となる。さらに、利用可能なサービスの数が、増加すれば、所望のタスクを実行する組み合わせの数も増大することが予想できる。そうなれば、従来技術によるシステムは、管理できなくなる。さらに、環境または要求者によって強いられる制約を考慮すれば、そのような組み合わせのすべてが、望ましいものであるとは限らない。従来の技術は、これらの問題を取り扱ったものでない。
【０００７】
【発明が解決しようとする課題】
本発明の目的は、上述した不都合を回避することであり、そして、サービスをリンクするのを効率的かつ効果的にサポートする分散情報処理システムを提供することであり、ユーザのニーズをできる限り満足させるサービスの組み合わせを提供する。
【０００８】
【課題を解決するための手段】
このために、請求項の前提部に記載されるような分散情報処理システムは、ジョブ仕様が、さらに、プロダクトに影響を与えることない状況に応じた制約を指定する仕様を備えるように、かつ、サービスのパスを決定するための手段が、そのジョブに対する状況に応じた制約を考慮に入れるように改善される。これは、組み合わせの数が管理できないほど多くなるという欠点を除去する。また、パスを選択するとき、本発明によるシステムは、例えば、料金、信頼性、安全性に関する制限を考慮に入れることができる。本発明による方法によれば、ユーザは、より多くの制約を適用することができ、また、制約は、ジョブによって届けられるべき最終的なプロダクトに反映されることはなく、そのために、システムによって提供される処理方法の数は、ユーザのニーズをより満足させるものである。
【０００９】
さらなる実施形態においては、状況に応じた制約は、指示された範囲における制限を規定する。さらに、システムは、状況に応じた制約の指示範囲に基づいてジョブを実行するのに適切なパスを順序づけるための手段と、ユーザが、所定の順序で並べられたパスに基づいて所定の順序で並べられたジョブ仕様のリストから所望のジョブ仕様を選択するためのユーザインタフェース手段とを備える。例えば、料金は、ある通貨単位で表現された金額よりも安くなければならないように、状況に応じた制約は、それが、ある特定の領域の範囲を有する値として示されるようなものであってもよい。これは、ある特定の状況に応じた制約に対して探索された値にはばらつきがあるにもかかわらず、すべてが制約を満足するいくつかのパスを生成するのを可能にする。このようにして、ある特定の制約について最適化することができる。
【００１０】
さらなる実施形態においては、システムは、パスを順序づけるときに使用されるべき状況に応じた制約をユーザが選択するためのユーザインタフェース手段を備える。ほとんどの場合、ジョブを実行するのに適したいくつかのパスが、システムによって届けられる。これらのパスは、条件付きの制約をどの程度まで満足するかが異なる。本発明によるこの特徴は、ユーザのニーズに最も適合したパスを容易に把握するための機能をユーザに提供する。
【００１１】
また、さらなる実施形態においては、状況に応じた制約は、実行されるべきジョブの合計料金であり、システムは、決定されたパスに含まれるサービスの料金属性から合計料金を計算する手段を備える。このようにして、ユーザは、ジョブを実行する最も安い方法を容易に探索することができる。
【００１２】
以下、添付の図面を参照して、本発明をより詳細に説明する。
【００１３】
【発明の実施の形態】
図１は、本発明による分散ドキュメントハンドリングシステムの実施形態を概略的に示す。画像形成システム１０１は、ネットワーク１１０を介して相互接続され、それによって、お互いに通信を行うことのできるいくつかの処理装置または周辺機器１０２から１０９を備える。具体的には、例として、周辺機器１０９は、低容量の複写機／プリンタであり、周辺機器１０８は、スキャナであり、周辺機器１０４は、大容量のプリンタであり、周辺機器１０７は、ファイルサーバであり、周辺機器１０５は、汎用サーバであり、周辺機器１０２、１０３、１０４、および、１０６は、ワークステーションである。ネットワーク１１０は、ローカルエリアネットワークである。また、ネットワーク１１０は、インターネットであってもよい。
【００１４】
本発明による分散ドキュメントハンドリングシステムは、ドキュメントに対してジョブを実行する。ドキュメントは、様々に表現されてもよく、あるいは、様々な特徴を有してもよい。本発明の説明においては、ドキュメントは、ある特定の時点においてドキュメントが有する実際のプロパティに依存した特徴を有する。そのようなプロパティは、その時点におけるドキュメントの状態を決定する。そのような状態は、ある特定の時点において現れるドキュメントのある特定の表現に対応する。第１の状態においては、ドキュメントは、ＡＳＣＩＩコードでコード化された特定のファイルとして現れ、次の状態においては、ドキュメントは、Ａ４規格の用紙に両面印刷されて綴じられたハードコピーとして現れるかもしれない。ここで、ジョブは、初期状態ｓｉにあるドキュメントを、ターゲット状態ｓｔにあるドキュメントに変換するものとして表現される。
【００１５】
本発明によれば、ジョブは、ネットワークに分散されたサービスによって実行される。これらのサービスは、ネットワーク内の様々な周辺機器で利用することができ、ドキュメントに対して固有の機能を実施する。そのような機能の例としては、画像処理、スキャン、暗号化、および、一方のページ記述言語からまた別のページ記述言語への変換がある。これらの種類のサービスは、以下で、アプリケーションサービスと呼ばれる。それぞれのアプリケーションサービスは、ある特定のドキュメントを処理するために呼び出されると、ドキュメントの状態を変化させる。ジョブを実行するときには、典型的にはいくつかのアプリケーションサービスが、関与する。ドキュメントの状態の変化を参照して、ドキュメントを処理するときのこれらの各アプリケーションサービスの作用を説明する。初期状態ｓｉから開始して、本発明によって選択されたいくつかのアプリケーションサービスは、ドキュメントを順次におよび／または並行して処理し、それによって、ターゲット状態ｓｔに到達するまで、それぞれの処理の後、ドキュメントは、状態を変化させる。関連するアプリケーションサービスは、有向グラフとしてパスを形成し、それに基づいて、ジョブを処理するその時点において、次のアプリケーションサービスが、決定される。
【００１６】
図２は、アプリケーションサービスのそのようなパスの例を示す。パスにおけるノード（２０１、２０２、２０３）は、ドキュメントが位置している特定の状態ｓを表現し、有向グラフにおける辺（２０４）は、ドキュメントを入力状態から出力状態にするアプリケーションサービスを表現する。図示されるサービスのパスにおいて、ドキュメントは、それの初期状態ｓｉ（２０１）から、いくつかの中間状態（２０３）を経由して、ターゲット状態ｓｔ（２０２）まで、段階的に変換され、それぞれの状態は、アプリケーションサービスによって実現される。この説明においては、状態は、明示的にタイプづけされたパラメータ値の列挙として提供される。
【００１７】
（計算処理的環境）
図３は、相互接続された周辺機器３０１の一般的構造を示す。それぞれの周辺機器は、それ自身のオペレーティングシステム３０２を有する。そのようなオペレーティングシステムは、基本タスクを実行し、アプリケーションプログラムの実行される環境を定義する。それぞれの周辺機器は、固有のタスクを実行するいくつかのアプリケーションプログラム３０３を有する。周辺機器は、ネットワークリンク３０５を介してお互いに接続され、それによって、ネットワークシステムが、構築される。そのネットワークリンクを介して、異なる周辺機器上のアプリケーションプログラムは、お互いに対話することができる。
【００１８】
１つの実施形態においては、いくつかのアプリケーションプログラムは、Ｊａｖａ言語によってプログラムされており、その周辺機器で実行できるＪａｖａ仮想マシンを必要とする。Ｊａｖａ仮想マシンは、特定のＯＳの上位に層３０４として提供される。その結果として、下位にあるオペレーティングシステムが異なっていても、すべてのこれらのアプリケーションプログラムをすべての周辺機器上で実行できる。相互接続されたいくつかの異機種周辺機器の全体をアプリケーションから見て１つの仮想マシンとして動作させるために、ミドルウェア層３０６が、提供される。この分野では良く知られているミドルウェア層は、例えば、サン・マイクロシステムズ社（Ｓｕｎ  ＭｉｃｒｏＳｙｓｔｅｍｓ）のＪＩＮＩである。しかしながら、様々な異機種コンピュータで実行されるアプリケーションに、お互いに対話するための手段を提供できさえすれば、その他のどのような環境でも、同様に、利用できる。
【００１９】
本発明によれば、ネットワーク内の様々な周辺機器において、ドキュメントに対して固有の機能を実施するアプリケーションサービスが、利用できる。システム内の様々な周辺機器に分散されたすべてのアプリケーションサービスは、それらが一体となって、サービスプールを構成する。これらのアプリケーションサービスを管理するために、ミドルウェア層は、サービス管理システムによって拡張される。
【００２０】
図４を参照して、以下で、サービス管理システムを説明する。図４は、ミドルウェア層４０３の一部としてのサービス管理システム４０２と、いくつかのアプリケーションサービス４０４と、ローカルアプリケーション４０５および４０６とを備えたワークステーション４０１の実施形態を示す。サービス管理システムは、いくつかのサービス管理コンポーネントを備える。基本的なサービス管理コンポーネントは、それぞれのノードでいつでも利用できる。その他のサービス管理コンポーネントは、必要に応じて、局所的に利用できる。サービス管理コンポーネントは、局所的に、および、遠隔からのいずれによってもアプリケーションサービスをアドレス指定できるように取り計らう。アプリケーションサービスは、サービス管理コンポーネントを局所的にしかアドレス指定することができない。必要であれば、局所的なアクセスのために、プロキシが立てられる。これらの複数のサービス管理コンポーネントは、レジストリ４０６と、パス作成モジュール４０７と、トランザクションマネージャ４０８と、移行マネージャ４０９とからなる。
【００２１】
本発明によるシステムの説明においては、オブジェクト指向モデルを使用する。これは、しかるべき場合に、クラスと、それらのクラスからインスタンス化されるオブジェクトとを参照して、本発明を説明することを意味する。オブジェクトは、データのコンテナと考えることができ、このデータには、オブジェクトによって提供されるメソッドによってしかアクセスすることができない。永続的オブジェクトは、アプリケーションを終了および開始すると、自動的に保存および復元されるオブジェクトである。クラスからオブジェクトのインスタンスを作成するのは、キーワード「ｎｅｗ」によって記述される。ｊａｖａ言語およびオブジェクト指向プログラミングに関する背景情報は、Ｊ．ＧｏｓｌｉｎｇおよびＨ．ＭｃＧｉｌｔｏｎによる「Ｊａｖａ言語環境、白書（Ｔｈｅ  Ｊａｖａ  Ｌａｎｇｕａｇｅ  Ｅｎｖｉｒｏｎｍｅｎｔ，Ａ  Ｗｈｉｔｅ  Ｐａｐｅｒ）」、および、Ｄｏｕｇｌａｓ  Ｋｒａｍｅｒによる「Ｊａｖａプラットホーム（ＴｈｅＪａｖａ  Ｐｌａｔｆｏｒｍｘ）」などの出版物から知ることができ、これらの著者は、いずれもＳｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓに勤務している。本発明によるパス作成モジュール４０７は、ジョブ要求を満足させるアプリケーションサービスの０かまたはそれ以上のパスを決定する。この点で、ジョブ要求は、クラスＲｅｑｕｅｓｔからインスタンス化されたＲｅｑｕｅｓｔオブジェクトを意味する。クラスＲｅｑｕｅｓｔは、データメンバーとして、ｉｎｐｕｔＳｔａｔｅ、ｏｕｔｐｕｔＳｔａｔｅ、および、ｃｏｎｓｔｒａｉｎｔＥｘｐｒｅｓｓｉｏｎを有する。サポートされるメソッドは、ｇｅｔＩｎｐｕｔ（）、ｇｅｔＯｕｔｐｕｔ（）、ｇｅｔＣｏｎｓｔｒａｉｎｔＥｘｐｒｅｓｓｉｏｎ（）である。ほとんどの典型的なアプリケーションサービスは、きわめて固有なタスクだけを実行し、その結果、ほとんどの場合において、サービスプールは、ユーザの要求に正確に一致するサービスは１つも含まない。したがって、ほとんどの場合、要求は、いくつかのアプリケーションサービスを組み合わせることによってしか一致させることはできない。しかしながら、あらゆる組み合わせが望ましいわけではない。いくつかのパスは、遅いサービスを含んでいるかもしれず、あるいは、高価なサービスを含んでいるかもしれない。ユーザによって指定された制約の範囲内で動作する適切なサービスの組み合わせを見つけるのは、とりわけ、本発明によるパス作成システムのタスクである。パス作成モジュールは、オブジェクトｐａｔｈＣｏｍｐｏｓｅｒとして実施される。このオブジェクトは、メソッドｐａｔｈＣｏｍｐｏｓｅｒ．ｇｅｔＰａｔｈ（Ｒｅｑｕｅｓｔ）を提供し、これは、Ｒｅｑｕｅｓｔを満足している０かまたはそれ以上のパスを戻す。
【００２２】
レジストリ４０６は、アプリケーションサービスを登録および登録抹消し、要求された属性に基づいてアプリケーションサービスを検索し、そして、サービスを呼び出すための識別子を戻す。このために、レジストリは、利用可能なアプリケーションサービスのデータベースを内部的に管理する。データベースは、図５のテーブルに示されるような、アプリケーションサービスのレコードを含む。アプリケーションサービスに関するすべてのデータは、テーブル内の横列として提供されるアプリケーションサービスレコード内に記憶される。それぞれのアプリケーションサービスは、タイプ、グローバルに一意な識別子（ＧＵＩＤ）、および、一組の属性によって表現される。タイプは、サービスが実行する機能の一般的示唆を与える。属性は、サービスの特徴、例えば、それが実行する固有の機能、場所などの物理的な特徴、１回の印刷に対する料金または１つのデータ単位に対する料金などの課金特徴を定義する。サービスが実行できる第１の状態から第２の状態への考えられるあらゆる変換を、例えば、この分野で良く知られている構文解析手段によって、サービスのしかるべき属性から抽出することができる。料金体系は、いくつかの体系の中の１つを参照して定義されてもよく、あるいは、図５の例に示されるように、明示的に定義される。図５については、以下で例を詳細に説明する際に、さらに詳しく説明する。
【００２３】
レジストリは、また、ＧＵＩＤをネットワークシステムのアドレス空間の１つのアドレスに対応付けるためのテーブルを含む。同様に、レジストリは、また、例えば、パス作成モジュールなどの、ネットワーク全体に分散されたサービス管理コンポーネントのデータベースを管理する。
【００２４】
レジストリは、オブジェクトｒｅｇｉｓｔｒｙとして実施される。データにアクセスするのに利用できるメソッドは、ｇｅｔＳｅｒｖｉｃｅ（）、ｇｅｔＡｔｔｒｉｂｕｔｅｓ（）、および、ｇｅｔＯｕｔｐｕｔＳｔａｔｅｓ（）である。メソッドｒｅｇｉｓｔｒｙ．ｇｅｔＳｅｒｖｉｃｅ（ｒｅｔｒｉｅｖａｌ＿ｃｒｉｔｅｒｉｏｎ）は、レジストリからサービスを検索する。このメソッドは、検索基準（ｒｅｔｒｉｅｖａｌ  ｃｒｉｔｅｒｉｏｎ）を満足するサービスの識別子を戻す。メソッドｒｅｇｉｓｔｒｙ．ｇｅｔＡｔｔｒｉｂｕｔｅｓ（Ｓｅｒｖｉｃｅ）は、特定のサービスからの属性を戻す。最後に、メソッドｇｅｔＯｕｔｐｕｔＳｔａｔｅｓ（Ｓｅｒｖｉｃｅ，ｉｎｐｕｔＳｔａｔｅ）は、その特定のｉｎｐｕｔＳｔａｔｅを与えられた特定のＳｅｒｖｉｃｅによって達成可能な出力状態を戻す。
【００２５】
トランザクションマネージャは、パスを提供されると、実際にジョブを実行するために、必要なすべてのリソースに要求し、また、パスの一部を構成するすべてのアプリケーションサービスを呼び出すのを制御する。
【００２６】
移行マネージャは、一方のホストから他方のホストへアプリケーションサービスを移行するのを管理する。
【００２７】
プロキシをバインドあるいは生成することに関して分散環境を管理するのに必要なその他のミドルウェアコンポーネントは、この分野では良く知られており、ここでは、さらに詳細には説明しない。
【００２８】
（ジョブ依頼ハンドラ）
図１に示される実施形態において、ユーザは、図４に示されるような接続されたワークステーションの１つから、印刷ジョブを定義して依頼（ｓｕｂｍｉｔ）することができる。従来、ワークステーションは、印刷ジョブ依頼ハンドラ４０５を備えている。印刷ジョブ依頼ハンドラは、印刷ジョブ依頼アプリケーションとして実施される場合にはユーザが直接に動作させることができ、あるいは、例えば、ワードプロセッサプログラム４０６などの別のアプリケーションプログラム内で起動されるプリンタドライバによって呼び出されてもよい。ここで、図６および図７を参照して、印刷ジョブ依頼ハンドラについて詳細に説明する。
【００２９】
図６ａは、ジョブ依頼ハンドラの制御下においてジョブを定義するためにユーザに提供された操作画面を示す。ユーザは、操作画面６０１内のエントリに値を入力することによってジョブを定義する。エントリ、すなわち、コピー部数（６０２）、カラー印刷（６０３）、綴じ（６０４）、出力用紙（６０５）、丁合い／仕分け（６０６）、濃淡（６０７）、および、倍率（６０８）は、すべて、ジョブによって届けられるプロダクトを指定するものである。単価（６０９）、セキュリティレベル（６１０）、サービスの信頼性（６１１）、届け場所（６１２）、および、前回の印刷（６１３）などのエントリは、すべて、条件付きの制約（ｃｏｎｄｉｔｉｏｎａｌ  ｃｏｎｓｔｒａｉｎｔ）であり、ユーザによってそれらが定義される限り、満足されなければならない。当然ながら、メーリングリストによる物理的な配信などのさらなる制約も可能である。また、操作画面は、印刷されるべきファイルを入力するための領域（６１３）およびジョブに関係するメッセージを表示するためのメッセージ領域（６１４）を含む。最後に、ジョブの指定が完了したこと、あるいは、ユーザがジョブの依頼をキャンセルしたいことをユーザが確認するために、ＯＫボタン（６１５）およびキャンセルボタン（６１６）が提供される。
【００３０】
図７は、ジョブ依頼ハンドラによって実行されるステップを説明するフローチャートである。ユーザが、印刷コマンドまたはそれに類似するものを起動すると、ジョブ依頼ハンドラが、呼び出される（ステップ７０１）。呼び出された後、ステップ７０２において、図６に示される操作画面が、ジョブパラメータを入力するためにユーザに表示される。ＯＫボタンを起動した後、印刷ジョブのためのすべてのパラメータが、可能なデフォルト値も含めて収集される。次に、ステップ７０３において、Ｒｅｑｕｅｓｔオブジェクトが、生成され、インスタンス変数ｉｎｐｕｔＳｔａｔｅ、ｏｕｔｐｕｔＳｔａｔｅ、および、ｃｏｎｓｔｒａｉｎｔＥｘｐｒｅｓｓｉｏｎが、収集されたパラメータ値によって初期化される。ユーザによって入力された制約を反映する式が、ｃｏｎｓｔｒａｉｎｔＥｘｐｒｅｓｓｉｏｎインスタンス変数に割り当てられることに注意されたい。
【００３１】
Ｒ＝Ｎｅｗ  Ｒｅｑｕｅｓｔ（ｉｎｐｕｔＳｔａｔｅ，ｏｕｔｐｕｔＳｔａｔｅ，ｃｏｎｓｔｒａｉｎｔＥｘｐｒｅｓｓｉｏｎ）
次に、ステップ７０４において、Ｒｅｇｉｓｔｒｙは、パス作成モジュールにアクセスするように要求される。すなわち、
Ｒｅｇｉｓｔｒｙ．ｇｅｔＳｅｒｖｉｃｅ（ｔｙｐｅ＝ＰａｔｈＣｏｍｐｏｓｅｒ）
Ｒｅｇｉｓｔｒｙは、パス作成モジュールにハンドルを戻し、レジストリの制御下で、ローカルステーションにおいて、パスファインダのプロキシが、生成される。
【００３２】
次に、ステップ７０５において、パス作成モジュールは、定義された要求のためのパスを戻すように要求される。すなわち、
ｐａｔｈＣｏｍｐｏｓｅｒ．ｇｅｔＬｉｓｔＯｆＰａｔｈｓ（Ｒ）
ステップ７０６において、パス作成モジュールは、ジョブによって指定されたプロダクトを届けるパスのリストを戻す。このリストは、見つかったすべてのパスだけでなく、パスごとに、ｃｏｎｓｔｒａｉｎｔＲｅｃｏｒｄ内の制約パラメータの値を含み、また、パスごとに、指定された制約を満足しているかどうかを示すフラグを含む。メッセージ領域に、制約パラメータの値が、探索されたパスごとに表示される。１つの例が、図６ｂに示される。ユーザは、いくつかの領域６１７の中から１つをポインティングデバイスでクリックすることによって、パスを選択することができる。多数のパスが戻された場合には、システムは、いくつかの領域６１８の中から１つをポインティングデバイスでクリックすることによって、ユーザが、いくつかの制約の１つに基づいて、これらのパスを順序づけるのを可能にする。この場合、料金での制約に応じて順序づけられたパスが表示される。料金の点で最も魅力のあるパスが、最上部に配置される。
【００３３】
ステップ７０７において、リストが１つでもパスを含むかどうかが検査される。もし含んでいれば（Ｙ）、メソッドは、ステップ７０８へ進み、そこで、ユーザは、いくつかのパスの中から１つを選択するようにプロンプトで指示される。ユーザが、１つを選択すると（Ｙ）、メソッドは、ステップ７０９へ進む。ステップ７０９において、トランザクションマネージャが、呼び出され、選択されたパスを提供される。トランザクションマネージャは、必要なアプリケーションサービスを要求し、それに続いて、要求を満足させるのに必要なサービスを呼び出す。呼び出されたサービスからのリターンメッセージは、トランザクションマネージャによって受け取られる。トランザクションマネージャは、これらのメッセージを、クライアントアプリケーションすなわちジョブ依頼ハンドラへ転送する。ジョブ依頼ハンドラは、これらのメッセージを、操作画面のメッセージ領域に表示する。また、ジョブが終了して届けられてしまえば、そのことが、操作画面のメッセージ領域に表示される。ステップ７１０において、ユーザによってこのメッセージが確認されると、ジョブ依頼ハンドラは、ジョブのデータをログファイルに記録し、そして、最終的に、メソッドは、終了する。
【００３４】
ステップ７０７において、戻されたパスのリストが、空であれば（Ｎ）、パス作成モジュールは、要求されたプロダクト仕様ではジョブを実行できない旨のメッセージを戻し、ステップ７１１に進む。また、ステップ７０８において、ユーザが、パスを選択しなければ（Ｎ）、メソッドは、ステップ７１１に進む。
【００３５】
ステップ７１１において、ユーザは、仕様に属するパラメータを変更するように要求される。ユーザが、否定的な応答をすれば（Ｎ）、メソッドは、ステップ７１０において終了し、ジョブは、なにも実行されない。もしユーザが、変更の可能性を受け入れるならば（Ｙ）、メソッドは、ステップ７１２に進み、そこで、ユーザは、ジョブ仕様を修正し、その後に、すべてのパラメータが、収集され、そして、再び、ステップ７０３において、新しい要求オブジェクトが、インスタンス化される。
【００３６】
（パス作成モジュール）
ここで、図８に示されるフローチャートを参照して、パス作成モジュールのｇｅｔＰａｔｈ（）メソッドについて詳細に説明する。タスクのｇｅｔＰａｔｈ（）メソッドは、与えられた制約の範囲内で、ある特定のタスクを実行することのできるアプリケーションサービスのパスを探索するためのものである。
【００３７】
このために、メソッドは、以下のステップを実行する。すなわち、
ステップ８０１において、ｇｅｔＰａｔｈメソッドを呼び出すとき、Ｒｅｑｕｅｓｔ  Ｒが、渡される。このＲｅｑｕｅｓｔ内には、変換されるべきデータオブジェクトの初期状態、完全に変換された後の所望のターゲット状態、および、完全な変換が満足しなければならない制約が、指定される。
【００３８】
ステップ８０２において、キューオブジェクトｑ、グラフオブジェクトｇ、および、オブジェクトｌｉｓｔＯｆＰａｔｈが、インスタンス化され、そして、初期化される。オブジェクトｑおよびオブジェクトｌｉｓｔＯｆＰａｔｈは、メソッドａｄｄＥｌｅｍｅｎｔ（）、ｈａｓＭｏｒｅＥｌｅｍｅｎｔ（）、および、ｇｅｔＮｅｘｔＥｌｅｍｅｎｔ（）をサポートするクラスＬｉｓｔからインスタンス化される。メソッドａｄｄＥｌｅｍｅｎｔ（）は、要素をリストに追加する。メソッドｈａｓＭｏｒｅＥｌｅｍｅｎｔ（）は、リストが１つでも要素を含んでいれば、ＴＲＵＥを戻し、そうでなければ、ＦＡＬＳＥを戻す。メソッドｇｅｔＮｅｘｔＥｌｅｍｅｎｔ（）は、リスト内の次の要素を戻し、その要素をリストから削除する。初期化するとき、要求のｉｎｐｕｔＳｔａｔｅが、キューオブジェクトｑ内に要素として配置される。
【００３９】
グラフオブジェクトｇは、クラスＧｒａｐｈからインスタンス化される。クラスＧｒａｐｈからインスタンス化されるオブジェクトは、有向グラフを記憶および操作するのに使用される。グラフ内のノードは、ドキュメントの状態を表現し、そして、第１のノードから始まり第２のノードに至る有向辺は、第１のノードの状態を第２のノードの状態に変換するアプリケーションサービスを表現する。要求に対して、グラフオブジェクトは、ｇｅｔＰａｔｈメソッドを実行しているときに、ある特定の時点において達成可能なすべての状態と、そのために必要なアプリケーションサービスとを管理する。図９は、ｇｅｔＰａｔｈ（）メソッドを実行しているときに組み立てられるようなグラフの例を示す。クラスＧｒａｐｈは、メソッドｓｅｔＲｅｑｕｅｓｔ（）、ａｄｄＮｏｄｅ（）、ｃｏｎｔａｉｎｓ（）、ｃｏｎｎｅｃｔ（）、および、ｐａｔｈＦｏｕｎｄ（）をサポートする。メソッドｓｅｔＲｅｑｕｅｓｔは、入力状態についてノードを追加し、Ｃｏｎｓｔｒａｉｎｔｓ式を記憶する。メソッドａｄｄＮｏｄｅ（）は、ノードをＧｒａｐｈに追加する。メソッドｃｏｎｎｅｃｔ（Ｎｏｄｅ１，Ｎｏｄｅ２，Ｓｅｒｖｉｃｅ）は、この状態変換を実行することのできるアプリケーションサービスに対応する、Ｎｏｄｅ１からＮｏｄｅ２への辺を追加する。メソッドｃｏｎｔａｉｎｓ（Ｎｏｄｅ）は、グラフ内にノードが含まれるかどうかを検査する。
【００４０】
上述したステップ８０２の結果として、
ｑ＝ｎｅｗ  Ｑｕｅｕｅ（）
ｑ．ａｄｄｅｌｅｍｅｎｔ（Ｒ．ｉｎｐｕｔ）
ｎｅｗ  ｇ＝Ｇｒａｐｈ（）
ｇ．ｓｅｔＲｅｑｕｅｓｔ（Ｒ）
となる。
【００４１】
ステップ８０３において、Ｑｕｅｕｅの中に要素が１つでもあるかどうかが検査される。もしなければ（Ｎ）、ステップ８１４へ進む。もし要素が利用可能であれば（Ｙ）、ステップ８０４において、次の入力状態が、キューからフェッチされ、その入力状態に基づいた変換を実行することのできるアプリケーションサービスのリスト（ＬＡＳ）が、Ｒｅｇｉｓｔｒｙに要求される。すなわち、
ｃｕｒｒｅｎｔｌｎ＝ｑ．ｇｅｔＮｅｘｔＥｌｅｍｅｎｔ（）
ＬＡＳ＝Ｒｅｇｉｓｔｒｙ．ｇｅｔＳｅｒｖｉｃｅ（ＩＮＰＵＴ＿ＳＴＡＴＥ＝＝ｃｕｒｒｅｎｔｌｎ）
ＩＮＰＵＴ＿ＳＴＡＴＥのための検索基準を満足しているかどうかが、図５に一覧表として示されるような「サポートされる変換」属性に関して検査される。
【００４２】
ステップ８０５において、アプリケーションサービスのＬｉｓｔであるＬＡＳが、要素を１つでも含んでいるかどうかが検査される。もし含んでいなければ（Ｎ）、メソッドは、ステップ８０３に進んで、次の入力状態を処理する。もし含んでいれば（Ｙ）、ステップ８０６において、次のアプリケーションサービスが、リストから取り出され、そのＡｐｐｌｉｃａｔｉｏｎ  Ｓｅｒｖｉｃｅによってまもなく届けられる出力状態のＬｉｓｔ（ＬＯＳ）が、作成される。すなわち、
ｃｕｒｒｅｎｔＳｅｒｖｉｃｅ＝ＬＡＳ．ｇｅｔＮｅｘｔＥｌｅｍｅｎｔ（）
ＬＯＳ＝Ｒｅｇｉｓｔｒｙ．ｇｅｔＯｕｔｐｕｔＳｔａｔｅｓ（ｃｕｒｒｅｎｔＳｅｒｖｉｃｅ，ｃｕｒｒｅｎｔｌｎ）
ステップ８０７において、次の要素が、ＬＯＳ内にあるかどうかが検査される。もしなければ（Ｎ）、メソッドは、ステップ８０５に進み、次のアプリケーションサービスを処理する。もしあれば（Ｙ）、ステップ８０８において、出力状態が、リストから取り出される。すなわち、
ｃｕｒｒｅｎｔＯｕｔ＝ＬＯＳ．ｇｅｔＮｅｘｔＥｌｅｍｅｎｔ（）
そして、以前にこの状態に到達したことがあるかどうかが検査される。すなわち、
ｇ．ｃｏｎｔａｉｎｓ（ｃｕｒｒｅｎｔＯｕｔ）
もし到達したことがなければ（Ｎ）、メソッドは、ステップ８０９に進み、そこで、状態が、Ｑｕｅｕｅに追加され、そして、ノードとしてＧｒａｐｈに追加される。すなわち、
ｑ．ａｄｄＥｌｅｍｅｎｔ（ｃｕｒｒｅｎｔＯｕｔ）
ｇ．ａｄｄＮｏｄｅ（ｃｕｒｒｅｎｔＯｕｔ）
次に、ステップ８１０が、実行される。ステップ８０９の結果が、肯定的なものであれば（Ｙ）、メソッドは、直接にステップ８１０に進む。ステップ８１０において、現在のアプリケーションサービスが、Ｇｒａｐｈに辺として追加される。すなわち、
ｇ．ｃｏｎｎｅｃｔ（ｃｕｒｒｅｎｔｌｎ，ｃｕｒｒｅｎｔＯｕｔ，ｃｕｒｒｅｎｔＡｐｐｌｉｃａｔｉｏｎＳｅｒｖｉｃｅ）
ステップ８１１において、入力からターゲットへのパスが、存在するかどうかが検査される。すなわち、
ｇ．ｐａｔｈＦｏｕｎｄ（）
もし存在しなければ（Ｎ）、メソッドは、ステップ８０６に進む。
【００４３】
もしパスが見つかれば（Ｙ）、メソッドは、ステップ８１２に進む。ステップ８１２において、見つかったいくつかのパスが、Ｇｒａｐｈから要求される。それぞれのパスごとに、ｃｏｎｓｔｒａｉｎｔＥｘｐｒｅｓｓｉｏｎ内に存在するすべてのパラメータが、計算される。これまでに、パス内のそれぞれのサービスごとに、パラメータ値への貢献度が、設定され、それに続いて、それぞれのパラメータごとに、パス全体についてのグローバルな値が、計算される。計算されたこれらの値は、その特定のパスのためのｃｏｎｓｔｒａｉｎｔＲｅｃｏｒｄ内に記憶される。これらの値によって、ｃｏｎｓｔｒａｉｎｔＥｘｐｒｅｓｓｉｏｎが、評価され、その評価の結果が、満足できるようなものであれば、要求された制約を満足していることを示すその特定のパスのためのフラグが、セットされ、カウンタｐが、１だけインクリメントされる。タプル（パス、ｃｏｎｓｔｒａｉｎｔＲｅｃｏｒｄ、フラグ）が、ｌｉｓｔＯｆＰａｔｈに要素として追加される。すなわち、
ｌｉｓｔＯｆＰａｔｈｓ．ａｄｄＥｌｅｍｅｎｔ（（ｐａｔｈ，ｃｏｎｓｔｒａｉｎｔＲｅｃｏｒｄ，ｆｌａｇ））
次に、ステップ８１３において、要求された制約を満足するパスｐの数が、しきい値Ｐよりも大きいかどうかが検査される。もし大きければ（Ｙ）、メソッドは、ステップ８１４に進む。ステップ８１４において、リストが、戻され、メソッドは、ステップ８１５に進む。もし大きくなければ（Ｎ）、メソッドは、ステップ８０６に進み、次のパスを検索する。
【００４４】
もしパスが、１つも見つからなければ、メソッドは、ステップ８１１（Ｎ）、ステップ８０６（Ｎ）、ステップ８０５（Ｎ）、および、ステップ８０３（Ｎ）から構成されるループを実行し、そして、ステップ８０３（Ｎ）において、ステップ８１４に到達し、空のリストが、戻される。このようにして、すべての適切なサービスからなる完全なグラフをトラバースしたことになる。
【００４５】
もし制約を満足するパスの数が、所望の数Ｐよりも小さければ（ステップ８１３：Ｎ）、これらのパスは、ステップ８１２において、リストに追加され、最終的には、ステップ８０６、８０５、および、８０３を経由して、ステップ８１４に到達し、そこで、これまでに収集されたパスを備えたリストが、届けられる。
【００４６】
ステップ８１１からステップ８０６までを任意の回数だけ反復するのを所定の最大回数に制限してもよく、それによって、この最大回数に達したとき、メソッドは、ステップ８１４に進み、そこで、これまでに収集されたすべてのパスが、戻される。この方法は、多数のサービスが利用可能な場合に、グラフを組み立てるのに要する時間を減少させる。
【００４７】
（クラスＧｒａｐｈ）
ここで、本発明によるシステムにおいて使用されるクラスＧｒａｐｈの実施形態を、図８および図９を参照して説明する。
【００４８】
クラスＧｒａｐｈからインスタンス化されたグラフオブジェクトは、図８のステップ２において生成および初期化され、かつ、図８のステップ１０および１１を繰り返して実行したときに拡張される有向グラフを表現する。図９に示されるグラフにおいて、ノードは、状態を表現し、第１のノードから始まり第２のノードに至る有向辺は、第１のノードの状態を第２のノードの状態に変換するアプリケーションサービスを表現する。要求に対して、グラフは、ある特定の時点で達成可能なすべての状態と、そのために必要なアプリケーションサービスとを管理する。まず最初に、グラフは、開始ノードを備える。
【００４９】
外部からアクセスすることのできるグラフオブジェクトのデータ要素は、Ｓｔａｔｅｓ、Ｒｅｑｕｅｓｔ、Ｎｏｄｅｓ、Ｅｄｇｅｓ、Ｓｅｒｖｉｃｅｓ、および、Ｐａｔｈであり、また、メソッドは、ｓｅｔＲｅｑｕｅｓｔ（）、ａｄｄＮｏｄｅ（）、ｃｏｎｔａｉｎｓ（）、ｐａｔｈＦｏｕｎｄ（）、および、ｃｏｎｎｅｃｔ（）である。
【００５０】
グラフの内部要素は、次のものがある。すなわち、
・ベクトルｖ、それの要素はグラフのノードを表現する、
・要素ｃｉｊを備えた接続のマトリックスＣ、
・初期状態から到達することのできる状態を含むｒｅａｃｈａｂｌｅＳｅｔ、
・ターゲット状態に変換することのできる状態を含むｔｒａｎｓｆｏｒｍａｂｌｅＳｅｔ。
【００５１】
ベクトルｖの要素ｖｉは、グラフのノードｎｉに対応する。それぞれのノードは、状態を表現する。状態は、ベクトルｓによって表現される。状態の要素ｓｉは、パラメータｉを表現する。情報オブジェクト、例えば、ドキュメントは、いくつかのパラメータの実際の値によって決定される状態を有する。一方の状態から他方の状態への変換を表現する辺は、マトリックスＣとして記憶される。それぞれの要素（ｉ，ｊ）は、ノードｉの状態からノードｊの状態になる変換を提供する。
【００５２】
ここで、図８を参照して、ｇｅｔｐａｔｈ（）メソッドで与えられるような、メソッド呼び出しのフローに沿って、グラフオブジェクトを組み立てることについてさらに説明する。
【００５３】
ステップ８０２において、Ｇｒａｐｈオブジェクトが、ステートメントを呼び出すことによって生成される。すなわち、
ｇ＝ｎｅｗ  Ｇｒａｐｈ（）
それに続いて、メソッドｇ．ｓｅｔＲｅｑｕｅｓｔ（Ｒ）を呼び出すことによって初期化される。
【００５４】
渡されるパラメータは、初期状態ｓ０、ターゲット状態ｓｔ、および、ｃｏｎｓｔｒａｉｎｔＥｘｐｒｅｓｓｉｏｎ  ｃＥである。ベクトルｖは、２つの要素すなわちｓ０およびｓｔを得る。マトリックスＣは、ヌル値だけで初期化される。ｒｅａｃｈａｂｌｅＳｅｔは、初期状態ｓ０で初期化され、ｔｒａｎｓｆｏｒｍａｂｌｅＳｅｔは、ターゲット状態ｓｔで初期化される。
【００５５】
ステップ８０９において、状態すなわちノードであるｃｕｒｒｅｎｔＯｕｔは、明らかに、まだ未知なものであり、状態が、ｒｅａｃｈａｂｌｅＳｅｔに追加される。また、メソッドｇ．ａｄｄＮｏｄｅ（）の呼び出しが、さらなる行およびさらなる列を追加することによって、状態をベクトルに追加し、マトリックスを更新する。
【００５６】
ステップ８１０において、メソッドｇ．ｃｏｎｎｅｃｔ（ｃｕｒｒｅｎｔｌｎ，ｃｕｒｒｅｎｔＯｕｔ，ｃｕｒｒｅｎｔＡｐｐｌｉｃａｔｉｏｎＳｅｒｖｉｃｅ）が、ｃｕｒｒｅｎｔｌｎのインデックスおよびｃｕｒｒｅｎｔＯｕｔのインデックスをベクトルからルックアップし、それに続いて、このインデックスを備えた位置にｃｕｒｒｅｎｔＡｐｐｌｉｃａｔｉｏｎＳｅｒｖｉｃｅを追加することによって、マトリックスを更新する。
【００５７】
次に、ステップ８１１において、ノードｃｕｒｒｅｎｔＯｕｔがｔｒａｎｓｆｏｒｍａｂｌｅＳｅｔ内に含まれるかどうかが検査される。もし含まれるならば（Ｙ）、ステップ８１２において、Ｆｌａｇ  Ｐａｔｈｆｏｕｎｄが、セットされ、メソッドは、利用可能なパスを見つけるために、グラフトラバースアルゴリズムを実行する。さらに、パスのメンバーであるすべてのノードが、ｔｒａｎｓｆｏｒｍａｂｌｅＳｅｔ内におかれる。このようにして、次の繰り返しにおいて、すでにパスの一部となったノードに到達すれば、結論として、新しいパスが見つかったと断定することができる。ｇｅｔＰａｔｈ（）メソッドのさらなるステップについては、すでに上述した。
【００５８】
（具体例）
ここで、具体例を参照して、本発明によるシステムの汎用性について説明する。図５に基づいて登録されたアプリケーションサービスと、図１に示される画像形成システムとが、与えられる。状態は、明示的な型を有するパラメータ値の集合として定義される。
【００５９】
ワークステーション１０６において、ユーザが、図６ａに示されるような画面に表示された印刷コマンドを指定する。ワークステーション１０６上のアプリケーションによって生成される印刷ファイルは、ｅｍｆ（拡張メタファイル）内にコード化される。
【００６０】
図７のフローチャートによれば、ジョブ依頼ハンドラ内で、ステップ７０３において、要求オブジェクトが、生成される。すなわち、
Ｒ＝Ｎｅｗ  Ｒｅｑｕｅｓｔ（ｓｓｏｕｒｃｅ，ｓｔａｒｇｅｔ，ｃＥ）
ここで、開始状態ｓｓｏｕｒｃｅ        ＝（ｆｏｒｍａｔ：ｅｍｆ）
ターゲット状態ｓｔａｒｇｅｔ  ＝（ｆｏｒｍａｔ：Ａ４，ｓｔａｐｌｉｎｇ：Ｙ，ｎｕｍｂｅｒ＝１００，ｓｏｒｔｅｄ／ｃｏｌｌａｔｅｄ＝ｓｏｒｔｅｄ）
制約ｃＥ＝（ｐｒｉｃｅ  ｒａｔｅ＝＜１５＄）  したがって、入力状態は、フォーマット：ｅｍｆによって定義され、出力状態は、フォーマット：Ａ４（印刷することを意味する）、綴じ、丁合い、および、コピー部数１００によって定義され、制約式は、（単価＝＜１５＄）である。  次に、ステップ７０４において、パスファインダサービスが、ルックアップされる。パスファインダサービスは、サーバ１０７において利用することができ、それに続いて、パスファインダサービスのプロキシが、ワークステーション１０６において生成される。次に、ステップ７０５において、パスファインダは、要求によって呼び出される。すなわち、
Ｐａｔｈｆｉｎｄｅｒ．ｇｅｔｐａｔｈｓ（Ｒ）
図８に示されるフローチャートによれば、ステップ８０２において、要求を受け取ると、キューｑおよびグラフｇが、生成され、初期化される。すなわち、
これによって、キューについては、
ｑ＝｛ｓ０｝、ここで、ｓ０＝ｓ（ｓｏｕｒｕｃｅ）ｅ＝（ｆｏｒｍａｔ：ｅｍｆ）となり、
そして、グラフｇについては、初期状態のためのノードおよびターゲット状態のためのノードが、生成される。
【００６１】
Ｇｒａｐｈオブジェクトについては、これは、内部的に、
νω＝（ｓ０）    Ｃ＝｛０｝
ｔａｒｇｅｔＳｔａｔｅ＝ｓ（ｔａｒｇｅｔ）
ｒｅａｃｈａｂｌｅＳｅｔ＝｛ｓ０｝
ｔｒａｎｓｆｏｒｍａｂｌｅＳｅｔ＝｛ｓｔ｝
であることを意味する。
【００６２】
ｇｅｔＰａｔｈ（）メソッドのステップ８０４において、まず最初に、キューからの要素が、取り出される。すなわち、
ｃｕｒｒｅｎｔｌｎ＝ｓ０
それに続いて、その入力状態に基づいて変換を実施することのできるアプリケーションサービスが、ルックアップされる（図５）。アプリケーションサービスのリストＬＡＳが、最後に戻される。すなわち、
ＬＡＳ＝｛ａｓ５｝
ステップ８０５において、ＬＡＳが要素を１つでも含むかどうか（Ｙ）が検査された後、ステップ８０６において、ａｓ５が、リストから取り出され、そのアプリケーションサービスによって届けることのできる出力状態のリストＬＯＳが、組み立てられる。すなわち、
ｃｕｒｒｅｎｔＡｐｐｌｉｃａｔｉｏｎＳｅｒｖｉｃｅ＝ａｓ５
ＬＯＳ＝｛ｓ１，ｓ２｝
ここで、ｓ１＝（ｆｏｒｍａｔ：ＰＣＬ）、および、
ｓ２＝（ｆｏｒｍａｔ：ＨＴＭＬ）
ステップ８０７において、ＬＯＳが要素を１つでも含むかどうか（Ｙ）が検査された後、ステップ８０８において、要素が、リストから取り出され、この要素がすでにＧｒａｐｈ内のノードであるかどうかが検査される。すなわち、
ｃｕｒｒｅｎｔＯｕｔ＝ｓ１
ｇ．ｃｏｎｔａｉｎｓ（ｓ１）
これは、ＦＡＬＳＥ（Ｎ）を戻し、その結果、ステップ８０９において、ｓ１が、Ｇｒａｐｈ内のノードとして記憶され、キューｑに追加され、また、ｒｅａｃｈａｂｌｅＳｅｔに追加される。すなわち、
ｑ．ａｄｄＥｌｅｍｅｎｔ（ｓ１）
ｇ．ａｄｄＮｏｄｅ（ｓ１）
ｒｅａｃｈａｂｌｅＳｅｔ＝｛ｓ０，ｓ１｝
その後、ステップ８１０において、アプリケーションサービスｃｕｒｒｅｎｔＡｐｐｌｉｃａｔｉｏｎＳｅｒｖｉｃｅによる状態ｃｕｒｒｅｎｔｌｎから状態ｃｕｒｒｅｎｔＯｕｔへの変換が、有向辺としてグラフ内に記憶される。すなわち、
ｇ．ｃｏｎｎｅｃｔ（ｓ０，ｓ１，ａｓ５）
ステップ８０９および８１０の実行は、Ｇｒａｐｈオブジェクトｇにとって、内部的には、ノードがベクトルおよびｒｅａｃｈａｂｌｅＳｅｔに追加されたことを意味し、また、マトリックスＣのディメンジョンを適合した後、ｃｕｒｒｅｎｔＡｐｐｌｉｃａｔｉｏｎＳｅｒｖｉｃｅが、マトリックスに追加されることを意味する。
【００６３】
ｇの内部のメンバーに対して、これは、以下のことをもたらす。すなわち、
νω＝（ｓ０，ｓ１）
ｒｅａｃｈａｂｌｅＳｅｔ＝｛ｓ０，ｓ１｝
【００６４】
【数１】
0003822087.tif 000002
ｔｒａｎｓｆｏｒｍａｂｌｅＳｅｔ＝｛ｓｔ｝
その後、ステップ８１１において、メソッドは、ノードｃｕｒｒｅｎｔＯｕｔがｔｒａｎｓｆｏｒｍａｂｌｅＳｅｔ内に含まれるかどうかを検査する。すなわち、これは、明らかに、含まれない（Ｎ）。その結果として、
Ｐａｔｈｆｏｕｎｄ：ＦＡＬＳＥ
そのために、メソッドは、ステップ８０７に進む。
【００６５】
要素ｓ２は、ＬＯＳ（Ｙ）内で利用可能であり、そのために、ステップ８０８において、この要素が、リストから取り出され、上述したように、ステップ８０９−８１０−８１１からなる同じシーケンスが、実行される。
【００６６】
これは、ｑ＝｛ｓ１，ｓ２｝をもたらし、ｇの内部メンバーについては、以下のことをもたらす。すなわち、
νω＝（ｓ０，ｓ１，ｓ２）
ｒｅａｃｈａｂｌｅＳｅｔ＝｛ｓ０，ｓ１，ｓ２｝
ｔｒａｎｓｆｏｒｍａｂｌｅＳｅｔ＝｛ｓｔ｝
【００６７】
【数２】
0003822087.tif 000003
Ｐａｔｈｆｏｕｎｄ：ＦＡＬＳＥ
ステップ８１１において、フラグＰａｔｈｆｏｕｎｄが、検査される。これは、再び、「ＦＡＬＳＥ」（Ｎ）をもたらし、そのために、メソッドは、ステップ８０７に進む。ステップ８０７において、ＬＯＳが出力状態を１つでも含むかどうかが検査される。この場合には含まないので（Ｎ）、メソッドは、ステップ８０５に進む。ステップ８０５において、リストＬＡＳが要素を１つでも含むかどうかが検査される。この場合には含まない（Ｎ）。メソッドは、ステップ８０３に進む。ステップ８０３において、キューｑが要素を１つでも含むかどうかが検査される。この場合にはもちろん含む（Ｙ）。ステップ８０４において、次の要素が、キューから取り出され、ｌｉｓｔＯｆＡｐｐｌｉｃａｔｉｏｎＳｅｒｖｉｃｅｓＬＡＳが、この状態について、戻される。すなわち、
ｃｕｒｒｅｎｔｌｎ＝ｓ１
ＬＡＳ＝｛ａｓ３，ａｓ４｝
要素がＬｉｓｔ内に存在するかどうかをステップ８０５において検査した後（Ｙ）、ａｓ３が、リストから取り出され、このアプリケーションサービスによって届けることのできる出力状態のリストが、組み立てられる。すなわち、
ｃｕｒｒｅｎｔＡｐｐｌｉｃａｔｉｏｎＳｅｒｖｉｃｅ＝ａｓ３
ＬＯＳ＝｛ｓ３｝
ここで、ｓ３＝（ｆｏｒｍａｔ：Ｐｏｓｔｓｃｒｉｐｔ）
それに続いて、ステップ８０８−８０９−８１０−８１１が、実行され、
ｑ＝｛ｓ２，ｓ３｝
νω＝（ｓ０，ｓ１，ｓ２，ｓ３）
ｒｅａｃｈａｂｌｅＳｅｔ＝｛ｓ０，ｓ１，ｓ２，ｓ３｝
ｔｒａｎｓｆｏｒｍａｂｌｅＳｅｔ＝｛ｓｔ｝
【００６８】
【数３】
0003822087.tif 000004
Ｐａｔｈｆｏｕｎｄ＝ＦＡＬＳＥ
となる。
【００６９】
ステップ８１１において、フラグＰａｔｈｆｏｕｎｄが、検査される。これは、再び、「ＦＡＬＳＥ」（Ｎ）をもたらし、それによって、メソッドは、ステップ８０７に進む。ステップ８０７において、ＬＯＳが出力状態を１つでも含むかどうかが検査される。この場合には含まないので（Ｎ）、メソッドは、ステップ８０５に進む。ステップ８０５において、リストＬＡＳが要素を１つでも含むかどうかが検査される。この場合にはもちろん含む（Ｙ）。メソッドは、ｃｕｒｒｅｎｔＡｐｐｌｉｃａｔｉｏｎＳｅｒｖｉｃｅとして、ａｓ４を処理する。このＡｐｐｌｉｃａｔｉｏｎＳｅｒｖｉｃｅは、出力状態として、
ＬＯＳ＝｛ｓ４｝、ここで、ｓ４＝（ｆｏｒｍａｔ：ＰＤＦ）
をもたらす。
【００７０】
ステップ８０８−８１１における処理の後、
ｑ＝｛ｓ２，ｓ３，ｓ４｝
νω＝（ｓ０，ｓ１，ｓ２，ｓ３，ｓ４）
ｒｅａｃｈａｂｌｅＳｅｔ＝｛ｓ０，ｓ１，ｓ２，ｓ３，ｓ４｝
ｔｒａｎｓｆｏｒｍａｂｌｅＳｅｔ＝｛ｓｔ｝
【００７１】
【数４】
0003822087.tif 000005
Ｐａｔｈｆｏｕｎｄ＝ＦＡＬＳＥ
となる。
【００７２】
メソッドは、ステップ８０７（Ｎ）およびステップ８０５（Ｎ）を経由して、ステップ８０３（Ｙ）に戻る。ステップ８０４において、ｓ２が、キューｑから取り出される。登録を検査することによって、入力状態としてＨＰＧＬを有する利用可能なアプリケーションサービスがないことがわかる。したがって、メソッドは、ステップ８０３に戻り、そこで、ｓ３が、キューｑから取り出される。ステップ８０４、８０５、８０６、８０８、および、８０９を実行することによって、
ＬＡＳ＝｛ａｓ１｝
ｃｕｒｒｅｎｔＡｐｐｌｉｃａｔｉｏｎＳｅｒｖｉｃｅ＝ａｓ１
ＬＯＳ＝｛ｓ５｝、
ここで、
ｓ５＝（ｓｈｅｅｔ＝Ａ４，ｃｏｌｏｒ＝Ｎｏ，Ｓｔａｐｌｅ＝Ｙｅｓ）
ｃｕｒｒｅｎｔＯｕｔ＝ｓ５
がもたらされる。
【００７３】
これは、ステップ８１０において、以下の状況をもたらす。
【００７４】
ｑ＝｛ｓ４，ｓ５｝
νω＝（ｓ０，ｓ１，ｓ２，ｓ３，ｓ４，ｓ５）
ｒｅａｃｈａｂｌｅＳｅｔ＝｛ｓ０，ｓ１，ｓ２，ｓ３，ｓ４，ｓ５｝
ｔｒａｎｓｆｏｒｍａｂｌｅＳｅｔ＝｛ｓｔ｝
【００７５】
【数５】
0003822087.tif 000006
ステップ８１１において、ｓ５が、変換可能なセット内に含まれる状態の中の１つのスーパーセットかどうかが検査される。実際に、ｓｔａｒｇｅｔは、ｓ５のサブセットである。これは、以下のことをもたらす（Ｙ）。すなわち、
Ｐａｔｈｆｏｕｎｄ＝ＴＲＵＥ
メソッドは、ステップ８１２に進む。ステップ８１２において、探索されたパスが、設定される。これは、（ａｓ５，ａｓ３，ａｓ１）をもたらす。ｃｏｎｓｔｒａｉｎｔＲｅｃｏｒｄは、それぞれの制約パラメータごとに決定される。パラメータ「ｐａｙ」だけが、指定される。したがって、探索されたパスの場合の合計額が、計算される。これは、ｃｏｎｓｔｒａｉｎｔＲｅｃｏｒｄ＝（ｐａｙ：１４＄）をもたらす。計算された値によって、ｃｏｎｓｔｒａｉｎｔＥｘｐｒｅｓｓｉｏｎが、評価される。これは、ＴＲＵＥをもたらす。得られたタプルは、ｌｉｓｔＯｆＰａｔｈｓに追加される。
【００７６】
これは、
ｌｉｓｔＯｆＰａｔｈｓ＝（（（ａｓ５，ａｓ３，ａｓ１），（ｐａｙ：１４＄），ＴＲＵＥ））
をもたらす。
【００７７】
この例においては、Ｐ＝２であると仮定する。
【００７８】
次に、ステップ８１３において、ｐ＞＝２であるかどうかが検査される。この場合にはそうではないので、次のパスを探さなければならない。
【００７９】
これは、ｐａｔｈ（ａｓ５，ａｓ４，ａｓ２，ａｓ１）をもたらす。また、このパスは、ｌｉｓｔＯｆＰａｔｈｓに追加され、
ｌｉｓｔＯｆＰａｔｈｓ＝（（（ａｓ５，ａｓ３，ａｓ１），（ｐａｙ：１４＄），ＴＲＵＥ），（（ａｓ５，ａｓ４，ａｓ２，ａｓ１），（ｐａｙ：１３＄），ＴＲＵＥ）
となる。
【００８０】
最後に、ステップ８１４において、このリストが、ジョブ依頼ハンドラに戻される。ステップ７０８において、ユーザが選択するために、パスが、図６ｂに示されるように料金順に並べて表示される。ユーザが、１つを選択し、メソッドは、上述したように、次の処理に進む。
【００８１】
ここで、本発明を十分に説明したが、この分野に通常の知識を有する者には、頭記の請求の範囲を逸脱することなく、これに多くの変更および変形を容易に施すことができる。
【００８２】
本発明は、テキストドキュメントに限定されるものではなく、同様に、あらゆる種類のドキュメント、例えば、ビデオ情報およびオーディオ情報を単独であるいは組み合わせて含むドキュメントにも適用できることに注意されたい。
【図面の簡単な説明】
【図１】分散システムを示す図である。
【図２】アプリケーションサービスのパスの例を示す図である。
【図３】相互接続された周辺機器の一般構造を示す図である。
【図４】サービス管理コンポーネントを備えたワークステーションの例を示す図である。
【図５】アプリケーションサービスのレコードを示す図である。
【図６ａ】ジョブ依頼ハンドラの操作画面を示す図である。
【図６ｂ】ジョブ依頼ハンドラの操作画面を示す図である。
【図７】ジョブ依頼ハンドラのフローチャートである。
【図８】ｇｅｔＰａｔｈ（）メソッドのフローチャートである。
【図９】例においてｇｅｔＰａｔｈ（）メソッドを実行するときに組み立てられる、サービスの有向グラフである。
【符号の説明】
ｓ０、ｓ１、ｓ２、ｓ３、ｓ４、ｓ５  状態
ｓｔ  ターゲット状態
ａｓ１、ａｓ２、ａｓ３、ａｓ４、ａｓ５  アプリケーションサービスの識別子
【図１】
0003822087.tif 000007
【図２】
0003822087.tif 000008
【図３】
0003822087.tif 000009
【図４】
0003822087.tif 000010
【図５】
0003822087.tif 000011
【図６ａ】
0003822087.tif 000012
【図６ｂ】
0003822087.tif 000013
【図７】
0003822087.tif 000014
【図８】
0003822087.tif 000015
【図９】
0003822087.tif 000016