DEIM Forum 2023 4b-8-4

時間経過を考慮したワークフローにおけるタスク割当て手法
山口 大河†

鈴木 伸崇††† 筑波大学人間総合科学学術院人間総合科学研究科 〒 305-8550 茨城県つくば市春日 1-2†† 筑波大学図書館情報メディア系 〒 305-8550 茨城県つくば市春日 1-2
E-mail: †s2121659@s.tsukuba.ac.jp, ††nsuzuki@slis.tsukuba.ac.jp
あらまし

多様なワーカを取り入れるためにはワーカ側の視点・リクエスタ側の視点双方が重要である．本研究ではワークフローへの割当てを扱うが，ワークフローには時間的制約が存在する．1 つはサブタスク間の順序関係であり，また 1 つはサブタスクの処理に時間が必要な点である．これらの制約を明示的に扱うことは，ワーカがタスクに取り組むべき時間を局所化 することにつながり，ワーカの効率なタスク受注の実現が期待できる．以上を踏まえ，本研
究では，多くのワーカを差別なく組み込み，それによる効率の低下を防ぎ．かつワークフローが含む時間制約を明示的に取り扱い，ワーカがタスクを行うべき期間を局所化する割り当て手法の構築を目指す．そのために，本研究ではワーカにスケジュールの概念を取り入れ，それに基づいた割当てを行う．その手法として，既存手法を拡張した手法
および，各期間の割当ワーカ数を最大化する手法を提案する．これら 2 手法を比較する実験を行った．その結果，最大流問題を利用した手法が多くの場合において優位であ ること，および，時間を明示的に取り扱うことにより，割当ての効率性という面において優位な結果となることを示した．また，それらの結果を併せ，より実践的な割当てに応用できる可能性を示した．
キーワード クラウドソーシング，タスク割当て，ボランティア，スケジューリング

に扱い，類似するタスクを括りそれを同一のワーカに割当てる

1 はじめにクラウドソーシングにはプロジェクト型，コンペティション
型，マイクロタスク型など複数の形式が存在するが，中でもマイクロタスク型は通常 1 回当たりの作業量が数分程度で終了する分量（シンプルタスク）に設定され，また必要とされる能力も少ないという特徴を持っており，この特徴により，従来は様々な要因（労働に割ける時間が少ない，能力が低いなど）か
ら労働が困難であった層を労働人口として取り入れるための手段としても有用であると考えられている [13] が，一方で課題も多い．
現在は Amazon Mechanical Turk やクラウドワークスに代表されるようにマイクロタスク型のクラウドソーシングでは
シンプルタスクが主流である．しかし，マイクロタスク型クラウドソーシングの今後の活用のためにはコンプレックスタスク
への対応が望ましい．コンプレックスタスクとはシンプルタス
クに比べ複雑な課題を解決するようなタスク（ホームページを作成するなど）のことを指す．コンプレックスタスクを処理するための一般的なアプローチとして，主に２通りの手法が提案されている．１つはコンプレックスタスクを複数のより簡単なサブタスク（シンプルタスク）に分割し，各サブタスクに対してワーカを割り当てるという手法 [5] [6] である．２つめは複数のワーカでタスクを処理するためのグループを構築し，そのグループに対してコンプレックスタスクを割り当てるという手法 [14] [15] である．また，これら２通りの手法はいずれも１つの処理するべきタスク（コンプレックスタスク）に対してとりうるアプローチを挙げたものであるが，複数のタスクを縦断的

バッチ割当ての手法 [7] [16] なども提案されている．本論文では，これらの手法のうちサブタスクへコンプレックスタスクを分割する手法の中でも，ワークフロー形式にサブタスクを分割する場合のタスク割当て手法を取り扱う．
ワーカへのタスク割当て手法の多くでは生産性やスループットなどタスクを依頼する側（リクエスタ）の事情に配慮して割当て手法を評価してきた．一方で，前述の通りマイクロタスク
型のクラウドソーシングは，より幅広い層から労働人口を確保するという点からも期待されており，ワーカへの配慮を行うことも重要である [2]．加えて，クラウドソーシングはボランティ
ア活動においての活用も活発になってきており [4]，そのようなボランティアベースの場面ではより顕著にワーカへの配慮が求められる．このようなワーカへの配慮の観点から提案された指標の１つがインクルージョン性である．インクルージョン性とは集まったワーカに対してどれだけのワーカが実際にタスクに関わることができているかどうかを測る指標である．ワーク
フローにおけるタスク割当てを扱った先行研究として生産性やスループットとインクルージョン性を両立することを目指した
手法 [11] が提案されている．本論文もこの流れを汲み，ボラン
ティアベースでの活用を想定し，効率性とインクルージョン性の両面から評価を試みる．
本論文ではワークフローで表現されるサブタスクの集合に対してワーカを割当てる課題を取り扱う．ワークフローはサブタ
スク処理の順番と経路を定義するものであり，そこには一定の時間的制約（タスクの先後，タスク処理に係る時間）と構造的制約（タスク処理の経路）が存在する．先行研究の多くでは構造的制約のみに着目し，時間的制約が明示的に示されることは

少なかった．一方で，時間的制約について言及した先行研究も存在し，サブタスクの処理期間が考慮されておらず全体としてのタスクが時に完了しない可能性があるという指摘 [7] [16] や，有向グラフ形式で表現されるサブタスクには順序関係が存在するため，これを考慮するべきであるという指摘 [8] という形で示されている．また加えて， [16] では，多くのワーカが同時に受注するタスクを１つに絞る傾向があり，なおかつ，タスクの期限は通常処理に必要な期間に対してやや冗長に設定される傾向があるため，ワーカの労働が効率的ではないことをも指摘し

図 1: ワークフロー例

た．以上のような指摘を踏まえ，本論文ではワークフローの時間的制約を明示的に取り扱うことでこれらの課題に対処することを試みる．
本論文の提案する手法の目的は以下の２つに設定されている．
１つに多くのワーカを差別なく組み込み（インクルージョン性2 諸 定 義2. 1 タ ス クに配慮する），それによる効率の低下を防ぐこと．２つ目に，

本研究では「タスク」というワードに対し，複数の定義が存

ワークフローが含む時間的制約を明示的に取り扱い，ワーカが在するため，それらを使い分けるために以下のように定義する．

タスクを行うべき期間を局所化することの２点である．本論文

１つ目はメインタスクである．本研究における「メインタス

で取り扱う課題の一例として，期間Ｐにおいて，ワークフロー

ク」とは，コンプレックスタスクそのものの事を指す．例えば，（Ａ⇒Ｂ⇒Ｃ）を実行する必要がある場合においてワーカ {a，T :「授業 L の録画動画に対して日本語の音声に英語字幕をつけb，c} にタスクを割当てるという課題を想定する．タスクＡにる」というタスクが存在した場合，T をメインタスクとする．

ワーカ a を，タスクＢにワーカ b を，タスクＣにワーカ c を割

２つ目はサブタスクである．サブタスクはメインタスクに対り当てるといった割当てを行うのが時間的制約の存在しない従してそれをより簡単なタスクの集合（本研究ではワークフロー）

来手法である．しかし，この場合現実にはワーカ a がタスクＡに構成し直した場合の，各タスク（ワークフローにおけるノーを終えない限り，ワーカ b はタスクＢに取り掛かることはでき

ド Vi ）の事を指す．上述の例に則ると，例えばメインタスク Tず（ワーカ c も同様），期間Ｐのうち一部のみしかタスクの作を３つのタスク，A:「動画を３分程度の動画に分割する」，B:

業に使用されず，時間的なロスが発生すると考えられる．そこ「分割された動画に対して，日本語を文字として書き起こす」，

で本論文では期間Ｐを，{ 期間１，期間２，期間３ } の集合に

C:「書き起こされた日本語を英語として書き起こす」に分割し分割して考え，[タスクＡ，期間１] にワーカ a を，[タスクＢ，た場合，A，B ，C のような各タスクをサブタスクと定義する．

期間２] にワーカ b を，[タスクＣ，期間３] にワーカ c を割り

３つ目はタスクインスタンスである．タスクインスタンスは当てるといった形式で時間的制約を明示化し，タスクの割当て

サブタスクに含まれる１単位（１人が１単位時間中に処理するを考える．これによりワーカはタスクを行うべき期間が局所化タスク）の事を指す．例に則ると，サブタスク B:「分割された

されより効率的に時間を使うことが可能になる．

動画に対して，日本語を文字として書き起こす」に対して，B3
本論文では，以上を踏まえ，2 つの手法（既存手法拡張型， 「動画（06:00〜09:00）に対して，日本語を文字として書き起こ最大流問題利用型）に対して，ワーカの能力数およびワークフ
す」のようなタスク B3 をタスクインスタンスと定義する．
ローを変化させた複数の実験条件を準備し，インクルージョン

また，本論文では「パス」というワードを使用する．パスと性を評価する inclusion，同じ成果量に対して必要なワーカ数

は，メインタスクを処理可能なサブタスクの一連の処理経路のを評価する inf lux，完成しなかった成果の数を評価する loss

事を指す．例えば，P1 ：「サブタスク A，サブタスク B ，サブの 3 つの観点について評価実験を行った．評価実験は 2 手法のタスク C の順に処理」というような場合の P1 を指す．これを，比較評価実験と，時間の明示化を導入した割当ての特性を評価

グラフ（図 1）を例にとると，次のように表記する．

する特性評価実験を行った．なお，後者では前述の 2 つの要素

P1 = (Vin , V1 , V2 , Vout )に加え，期間の分割数を実験条件に加えている．比較評価実験
では，最大流問題利用型の手法が多くの場合優位であるということ，また，手法の優位性がワークフローの違いによる影響を受けることを示した．特性評価実験では，時間の明示化を導入
した割当て手法が，主に inf lux や loss といった効率性に関係する指標に影響を及ぼすことを示した．

ま た ，こ の 場 合 P2=

(Vin , V3 , V4 , V5 , Vout ) や P3=

(Vin , V6 , Vout ) などの経路もパスである．
2. 2 モ デ ル
本研究では以下のようなモデル（図 2）のもとワーカの割当てを考える．まず，各ワーカはメインタスクに対して申込を行
い，各ワーカをメインタスクで受け入れるかどうかを判断する．
この際，基本的には全てのワーカを受け入れることを想定しているが，ワーカの有する能力（Aw ）とタスクに必要とされる能

在する場合，いずれか１つの期間に対してタスクが実際に割当てられている状態をタスクが割当てられているとみなす．

3 提案手法
本章では，本論文の提案手法について解説する．まず，本論文で取り扱う時間の明示化について例を交えながら概説し，そ図 2: 本研究の割当てモデルの後，手法に共通する処理，既存手法を拡張した手法について述べ，最後に最大流問題を活用した手法について解説する．

力（At ）とを比較し，いずれのタスクに対しても必要な能力を有さないと判断される場合にのみ受け入れを拒否する．そうし3. 1 時間の明示化て受け入れられたワーカでワーカのプール（集合 W ）を作成

本研究で取り扱うモデルについては第２章で述べた．ここでし，形成された W に対して割当て手法を適用，想定される処は，第２章で取り上げたモデル（図 2）における割当て手法の理可能タスクインスタンス数 Nt を算出する．これをリクエス

適用について詳細に記述する．例として以下のような割当てをタ側が提示する希望処理タスク（タスクインスタンス）数 Dt

考える．

と比較し，Nt >= Dt となった時点でワーカの流入を停止し，募集を打ち切る．
この際，リクエスタおよび，ワーカは以下の情報を与えるも
のとする．

•

リクエスタ

– 希望処理タスク数（Dt ）：必要な処理済みタスクインス
タンスの数を設定する– 希望処理期間（N ）：単位期間（標準的な１タスクインス
タンスを処理するために要する期間）に対してどの程度の期間内に処理が完了することを求めるか，期間の長さを設定する– ワークフロー：サブタスクに分解済みのワークフローを

Dt = 3N =3•

W orkf low = (V, E)•

V = {Vin , V1 , V2 , V3 , V4 , V5 , V6 , Vout }•E = {(Vin , V1 ), (Vin , V3 ), (Vin , V6 ), (V1 , V2 ), (V2 , Vout ),(V3 , V4 ), (V4 , V5 ), (V5 , Vout ), (V6 , Vout )}•Ability = {a1 , a2 , a3 }•At = {(V1 , [a1 , a2 ]), (V2 , [a3 ]), (V3 , [a1 ]), (V4 , [a2 ]),(V5 , [a3 ]), (V6 , [a1 , a2 , a3 ])}•W = {w1 , w2 , w3 , w4 , w5 }•Aw = {(w1 , [a1 ]), (w2 , [a2 ]), (w3 , [a3 ]), (w4 , [a1 , a2 ]),(w5 , [a1 , a2 , a3 ])}提供する– サブタスクに要する能力（At ）：各サブタスクを処理す•

Sw = {(w1 , [1, 0, 1]), (w2 , [0, 1, 0]), (w3 , [0, 1, 1]),

(w4 , [1, 0, 0]), (w5 , [0, 0, 1])}

る為に必要な能力を設定する•••

ここで各要素について順に改めて解説する．Dt はリクエスタ

ワーカ– 能力（Aw ）：自身が有する能力（サブタスクの処理に必側が提示した必要なタスクインスタンス数を示すものである．

N は割当てを考える期間の長さを示し，上記の例では３つの要な能力）を申告する– スケジュール（Sw ）：メインタスクの処理期間内におけ単位期間でタスクを終了することを示す．W orkf low，V ，E

るタスク割当ての希望を単位期間ごとに提出するはいずれもワークフローを定義するものである．これについ

なお，割当て手法の適用については，第３章において詳細に記ては第２章で提示したワークフローの例（図 1）を用いてい述する．

る．Ability は使用するワークフローにおいて考慮するべき能力として提示される能力の集合である．At は各サブタスクに

2. 3 インクルージョン性

おいて必要とされる能力をサブタスクごとに定義したものであ

インクルージョン性とは集まったワーカに対して，そのうちり，例えば (V1 , [a1 , a2 ]) はサブタスク V1 に対して必要な能力

どの程度のワーカに実際にタスクが割り当てられたかどうか

は a1 と a2 であることを示している．また，Vin および Voutを評価する指標である．本論文では，これを以下のように定義

は始点と終端のサブタスクを定義するものであり，実際に処理する．

するべきタスクインスタンスは存在せず，これらのサブタスク∑
inclusion =w∈W allocation(w)|W |ここで W は集まった全てのワーカの集合，allocation(w) はワーカ w に対して，そのワーカに対してタスクが割当てられていれば１をそうでなければ０を返す関数である．本研究においては，ワーカはスケジュール上の複数期間に対してタスク
割当ての希望を提出することを想定しており，またそれら複数に対して実際にタスクが割当てられることをも想定している．

allocation(w) はこのようにワーカ側が希望する期間が複数存に能力は設定されない．W はプールされたワーカの集合である．Aw は各ワーカの有する能力を定義するものであり，例中の (w4 , [a1 , a2 ]) はワーカ w4 が能力 a1 と a2 を有していることを示す．最後に，Sw は各ワーカの各期間におけるメインタ
スクへの参加の可否（希望）を示すものである．上記の例では

N = 3 となっていることから，各ワーカが提示するスケジュール長は 3 となる．例えば，(w1 , [1, 0, 1]) はワーカ w1 が提示したスケジュールが [1, 0, 1] であることを示し，[1, 0, 1] は３つの

また，第２章で提示したモデル（図 1）に拠ると，割当てをし

表 1: ワーカのスケジュール例

たのち予想処理可能タスク数 Nt を算出する必要がある．これ

worker 期間 1 期間 2 期間 3
w1

⃝

−

⃝

は Vin から Vout までの完成したパスの数と同義である．例のよ

w2

−

⃝

−

うな割当ての場合，(Vin , V1 , V2 , Vout )，(Vin , V3 , V4 , V5 , Vout )，

w3

−

⃝

⃝

(Vin , V6 , Vout ) の３つのパスが完成していることを確認できる．

w4

⃝

−

−

よって，Nt = 3 である．最後に，これを Dt = 3 と比較し，

w5

−

−

⃝

Nt >
= Dt が成立するため，このような割当てが考えられる場合にはワーカの募集を打ち切ることになる．
以上が，時間の明示化とそれを考慮した割当て，およびそれ

表 2: 割当て例

を利用したモデル中での活用の例である．

サブタスク名

期間 1

期間 2

期間 3

V1

w4

−

−

V2

−

w3

−

V3

w1

−

−

前節では本研究で取り扱うタスク割当ての適用について述べ

V4

−

w2

−

た．本節以降では，実際に本研究が提案する割当て手法につい

V5

−

−

w3

て解説する．本論文では２種類の割当て手法を提案する．１つ

V6

−

−

w5

は既存手法拡張型，もう一方は最大流問題利用型である．それ3. 2 ワーカのグループ化

ぞれ第３．３節，第３．４節で詳細な手法については記述する．
期間において，１番目と３番目の期間にメインタスクへの参加

本論文では，両手法に共通で行っている処理について解説する．

が可能（割当て可能）であることを示している．また，このス

本研究では，割当ての簡略化のため，ワーカのグループ化をケジュールを表に示すと以下のようになる（表 1）．本研究で行っている．ワーカのグループ化の手順は以下の通りである．

は，割当て上の時間的制約を以下のように設定する．

（ 1 ） 各単位期間に１人のワーカは１種類・１つのタス

Gs は各グループでグループ内全体を統合したスケジュール，Gt（ 2 ） 先行タスクが存在する場合，それより前の期間には各グループが実行可能なタスクの集合を登録する変数である．

おいて先行タスクのインスタンスが実行されていることを

５〜１３行目では，各ワーカについて，実行可能なタスクを必要とする抽出し，ワーカをグループ化している．６行目では各ワーカが（ 3 ） 各ワーカへはスケジュール上参加可能としている

実行可能なタスクの集合を保存する tasks を初期化する．７行

期間のみタスク割当て可能である目では各サブタスクについてワーカが有する能力とサブタスク



以上を踏まえ，このような例に対して適当な割当ての一例は
上表（表 2）のようになる．なお，ここで行：V1 ，列：期間１に記された w4 はサブタスク V1 のタスクインスタンスを期間１においてワーカ w4 に割当てることを表す．以下，割当てが適当であることを確認する．まず，期間１において割当て可能なワーカは表 1 より w1 および w4 であり，各ワーカは V3 ，V1の各１種類のサブタスクに対してのみ割当てられている．よって，期間１において時間的制約１と３を満たしている．これは期間２，期間３についても同様である．また，時間的制約２について確認すると，V2 はサブタスク V1 を先行タスクにもつが，
期間２における w3 への割当てについて，期間１において既にサブタスク V1 のインスタンスを実行済みである．同様に，V4 ，

V5 についても先行タスクが実行済みであることが確認できる．
次に能力について確認する．割当ての際には，ワーカがサブタ
スクに必要とされる能力全てを有している必要がある．この点について，V6 を例にとると，V6 は a1 ，a2 ，a3 全ての能力を必要とするサブタスクであるが，期間３において割当てられた
ワーカ w5 は全ての能力を有しており，条件を満たしていることが確認できる．これもまた全てのサブタスクについて同様に確認できる．

１〜４行目では，各値の初期化を行っている．Gw はワーカのグループの集合，Gm は各グループに含まれるワーカの集合，

クインスタンスを実行する



以下，ワーカのグループ化について概説する．

に必要とされる能力とを比較し，ワーカが必要な能力を有する
場合に tasks に該当サブタスクを追加する．１２行目では，各ワーカの tasks を参照し，現状登録されているワーカのグルー
プに同様のグループが存在するかどうかを確認し，存在しない
場合，新規のグループを作成し，存在する場合，該当グループのワーカ集合に追加する．
１４〜２０行目では，グループごとにグループ内のワーカが提出したスケジュールを統合している．１５行目では各グループの統合後スケジュールを長さ N ，初期値 0 で初期化している．１６行目から１８行目ではグループに含まれる各ワーカのスケジュールを参照し，ワーカがメインタスクに参加可能と提示している期間の値を 1 加算する．１９行目は作成された各グ
ループの統合スケジュールを保存している．
このような処理を行うことで，ワーカは実行可能なタスクを特徴量としてグループ化されることになる．上記のアルゴリズ
ム中で使用している関数は以下のような機能をもつ．なお，Gwにはワーカのグループの集合が，Gm には各グループに含まれるワーカの集合が，Gs には各グループでグループ内全体を統合したスケジュールが，Gt には各グループが実行可能なタスクの集合が登録されている．

•

update-group(Gw , Gm , Gt , tasks, wi )– Gt 中の全ての value（集合）を参照し，tasks と一致する集合が存在するかどうかを確認する– 存 在 し た 場 合 ，該 当 value の key を 参 照 し ，当 該
key = name に結びついた Gm (name) に wi を追加する– 存在しなかった場合，Gw にユニークなグループ名 nameを生成し，Gm (name) に wi を追加する•

update-schedule(schedule, wj , Sw )– Sw (wj ) を参照し，wj のスケジュールを取り出す– schedule に取り出したワーカ wj のスケジュールを期間
図 3: 割当て例用ワークフロー

ごとに足し合わせる

Algorithm 1 Grouping Algorithm

かる．これらをひな形に，各パスの先頭サブタスク [P1 , 1] とInput: N ,W ,Workﬂow,At ,Aw ,Sw[P2 , 1] を処理待ちタスクに追加する．この時，例えば [P1 , 1] はOutput: Gw ,Gm ,Gs ,Gt
Initialization :パス P1 の 1 番目のサブタスクを表している．なお，Vin および

1: Gw = ∅Vout はパスの始点と終点を定義するものであり，実際のタスク

2: Gm = ∅を持たないため順番には含めない．次いで，処理待ちタスクを

3: Gs = ∅パスの完成までに必要な残りタスク数が昇順になるようにソー

4: Gt = ∅5: for i = 1 to |W | do

トする．この場合，[P2 , 1]，[P1 , 1] の順になる．また，ワーカ

6:tasks = ∅のグループについても，グループが実行可能なタスク数の昇順

7:for j = 1 to |V | doif Aw (wi ) ⊇ At (tj ) then8:tasks.push(tj )9:になるようにソートする．この場合，{G2 , G3 , G1 } である．これにより，実行可能なサブタスクが少ないワーカのグループに

10:

end if

優先的にタスクが割当てられる．以上が初期化の処理である．

11:

end for

次に，期間ごとの割当てを行う．期間ごとの割当てでは期間

12:

update-group(Gw , Gm , Gt , tasks, wi )13: end for
14: for i = 1 to |Gw | do15:

schedule = ∅(length = N, initial-value = 0)16:

for j = 1 to |Gm (gi )| do
update-schedule(schedule, wj , Sw )

17:
18:

end for19:

Gs (gi ) = schedule内で割当て可能であるワーカのグループのうち，ソートされたグループの先頭から順に割当てを行う．例の場合，期間１ではG2 ，G1 の順である．グループへの割当てでは処理待ちタスク
を先頭から参照する．例の場合まず，先頭 [P2 , 1] を参照する
が，該当するタスクは V3 であり，G2 はこれを実行できない．
よって，次のタスク [P1 , 1] を参照する．すると，該当するタス

20: end for

クは V1 であり，G2 はこれを実行できるため，G2 に P1 中の

21: return Gw ,Gm ,Gs ,Gt

V1 を割当て，割当て済タスクに [P1 , 1] を追加する．また，これは P1 中の先頭サブタスクであり，他のサブタスクの処理結

3. 3 既存手法拡張型
本節で取り扱う既存手法拡張型の手法は，先行研究 [11] で提案された手法を前節で取り上げた割当てに対応できるように拡張するものである．先行研究で提案された手法は「できるタスクが少ないワーカを優先的にタスクに割当て，そのタスク結果が無駄にならないようにできるタスクが多いワーカを割り当てていく手法」である．本研究では時間制約を考慮するため，これを各期間において適用することを考える．
まず，簡単な例を用いて概要を説明する．例として，期間長：

N = 2，ワークフロー：図 3，ワーカグループ：{G1 , G2 , G3 }に対して割当てを行うことを考える．また，実行可能タスクは

G1 ：{V1 , V2 , V3 }，G2 ：{V1 }，G3 ：{V2 } であり，期間１ではG1 と G2 に，期間２では G1 と G3 に各 1 ずつのワーカを割当て可能であるとする．この時，本手法での割当て手順は以下の通り．
ま ず，ワ ー ク フ ロ ー に 対 し て 可 能 な パ ス を 探 索 す る と ，

P1 = (Vin , V1 , V2 , Vout )，P2 = (Vin , V3 , Vout ) の 2 つが見つ果を必要としない．そのため，処理待ちタスク中から [P1 , 1] は削除しない．次いで，G1 の割当てを考えるが，G1 には処理待
ちタスクの先頭 [P2 , 1] について該当するタスク V3 を実行可能であるため，P2 中の V3 に割当て，割当て済タスクに [P2 , 1] を追加する．これで期間１での処理は終了し，更新作業に移る．
更新作業では割当て済タスクを次の期間のために処理待ちタスクへ移行する．例の場合，[P1 , 1] は次のサブタスクを表す[P1 , 2] とし，該当するタスク V2 が存在するため，これを処理
待ちタスクに移行する．この際，P1 は残り 1 つのタスクでパスが完成することから同様に残り 1 つのタスクでパスが完成するもののうち先頭に追加する．この場合，処理待ちタスクは{[P1 , 2], [P2 , 1], [P1 , 1]} となる．次に，[P2 , 2] を考えるが，これに該当するタスクは存在しない．よって，処理待ちタスクへは移行せず，パスが完成したものとし，処理済みタスクインス
タンスをカウントする Nt を 1 加算する．以上で更新作業は終了である．
期間２では，G3 ，G1 の順にタスクを割り当てる．G3 については処理待ちタスクの先頭 [P1 , 2] に該当するタスクは V2 であり，これを実行可能である．よって，P1 中の V2 に割当て，[P1 , 2] を割当て済タスクに追加する．また，[P1 , 2] はパス中先– Gs からワーカグループ gj のスケジュール i 番目の期間に登録されている数値（人数）を参照する

頭タスクではなく，先行するサブタスクの処理結果を使用・消•費するため，これを処理待ちタスクから削除し，処理待ちタス– processingm （[Ps , t]）について，パス Ps 中の t 番目のクは {[P2 , 1], [P1 , 1]} となる．以下同様にして，G3 に P2 中のV3 が割当てられる．
最後に更新作業を行う．この際，さらに 2 つのパスが完成するため，Nt = 1 + 2 = 3 となり，割当ては期間１で G1 に V3 ，extract-task(processingm )タスクを参照する•

update-pass(processingm , allocated)– processingm （[Ps , t]）について，allocated に [Ps , t + 1]
を保存する

G2 に V1 ，期間２で G1 に V3 ，G3 に V2 が最終的な割当てと– t=| 1 の時，processing 中から processingm を取り除く

なる．以上が手法の概要である．続いて，アルゴリズムの詳細•を以下に示す．まず，アルゴリズム中で使用している表記と関– processing 中の完成しないパスを削除する関数である

processing = adjust(processing, N, i)– allocated に含まれる個々のデータ [Pu , v] を先頭から順
Algorithm 2 Allocation Algorithm 1
Input: N , Workﬂow, At , Gw , Gs , Gt
Output: Allocation, Nt
Initialisation :に処理する– |Pu | − v >= N − i である場合には，u 番目以降のパスを全て P から削除する

1: Allocation = ∅•2: Nt = 0

– allocated に含まれる個々のデータ [Pu , v] を順に処理する

3: processing = ∅4: P = all-passes(Workﬂow)
5: P.sort!
6: Gw = sort-ability(Gw , Gt )7: for i = 1 to |P | doprocessing.push([Pi , 1])

8:

9: end for
10: for i = 1 to N do
11:

allocated = ∅12:

for j = 1 to |Gw | do

13:

k=1

14:

while k ¡ Gs (i, gj ) dofor m = 1 to |processing| do

15:
16:

task = extract-task(processingm )17:

if task ⊆ Gt (gj ) then18:

update-pass(processingm , allocated)

19:

Allocation.push([i, gj , task])20:

k =k+121:

breakmerge(processing, allocated, Nt )– v > |Pu | である場合には Nt に 1 を加算する– v <= |Pu | である場合には processing の適切な位置に[Pu , v] を挿入する– 適 切 な 位 置 と は processing 中 に お い て ，各 デ ー タ が|Pu | − v の昇順に並ぶ状態をいう– |Pu | − v が同値の場合には同値中の先頭に挿入する– processing 中において |Pu | − v
以下，アルゴリズムについて解説する．１〜３行目では，各値を初期化している．Allocation は最終的な全割当てを [(割当て期間), (割当て先グループ名), (割当てサブタスク)] の形式で保存する．また，Nt は完成したパスの数を，processing は [(パス), (パス先頭からの順番)] の形式で処理途中（割当て可能）のパスを保存する．
４行目では，ワークフローに対して，全パスを探索し，P に保存している．

22:

end if23:

end for

５，６行目では，P および，Gw をソートしている．P はパ

end while

スを構成するサブタスクの数により，Gw はグループが実行可

24:
25:

end for26:

processing = adjust(processing, N, i)

27:

processing = merge(processing, allocated, Nt )28: end for
29: return Allocation, Nt

能なサブタスクの種類数により，いずれも昇順となるようにソートしている．
７〜９行目では，processing に P に含まれる全パスについて
先頭タスクを処理途中のパスとして登録している．
１０〜２７行目では実際に割当てを行っている．１１〜２６

数について解説する．

•

all-passes(Workﬂow)

行目では各期間に行う処理を記述している．１１行目では該当期間に割当てが行われたパスを保存する allocated を初期化し– Workﬂow 中の全てのパスを探索するている．１２〜２５行目ではワーカグループごとに先頭から行•

う処理を記述しており，１４〜２４行目は該当期間にメインタ

sort-ability(Gw , Gt )– Gw 中のワーカグループについて，Gt を参照する

スクへ参加可能としたワーカ１人ごとに処理を行うことを示し– 各ワーカグループが実行可能なタスク数により Gw を昇ている．１５〜２３行目では，processing（処理中パスの集合）

順にソートする•

gjについて先頭から該当ワーカグループに対してタスクを割当て可能であるかどうかを確認し割当てを行っている．より詳細に– Gw 中に含まれる j 番目のワーカグループ

は，１６行目で，パス中で次に処理されるべきタスクを抽出し，•

１７行目でワーカグループに当タスクを割当て可能であるかど

Gs (i, gj )うかを確認し，割当て可能な場合には１８〜２１行目の処理を実行する．１８行目では，processing から allocated に該当パスを移動し，重複して同一のパスにワーカを割り当てることを防ぐ．ただし，８行目で登録したパスについては重複して割当て可能（先行タスクが存在しないため）であるため，allcoated にコピーを作成する．１９行目では Allocation に割当てを保存する．２０〜２１行目ではワーカ１人分の割当てを終了し，次のワーカの割当てに移行するための処理を行っている．最後に
２６，２７行目で次の期間の割当てへと移行するための処理を
図 4: 期間１割当て用重み付きグラフ

行っている．まず，２６行目で残りの期間では完成しないパスを processing 中から削除する．２７行目では allcoated 中のパスについてパスが完成していれば，Nt を加算し，そうでなけ
れば processing に「パス先頭からの順番」を 1 加算し，パスの完成までに必要なタスクの数が processing 中で昇順となる位置に挿入する．
以上の処理において，Gw がグループの実行可能なサブタス
クの種類数により，また processing がパスの完成までに必要なタスク数の種類により昇順にソートされている．これにより，ワーカは実行可能なタスクの少ないワーカを優先的に割当て，

図 5: 期間２割当て用重み付きグラフ

また割当てたワーカが無駄にならないように完成しやすいパス
に対して優先的に割当てを行うことができる．

3. 4 最大流問題利用型
本節では最大流問題利用型の割当て手法について記す．最大流問題利用型の割当ては，各期間におけるワーカへのタスクイ
ンスタンスの割当て数を最大化する割当てを導出している．まず，３．２節と同様の例を用いて本手法の概要を説明する．ただし，本手法では割当てを求める際に Gt を利用し，ここではGt = 3 であるとする．また以下，stock(V ) の表現を利用する．
これはサブタスク V について V までが終了しているタスクイ
ンスタンスの数を表し，初期値として stock(Vin ) = Gt ，その他のタスク Vn に対して stock(Vn ) = 0 を設定する．また，終端を形成するサブタスク（Vout へと接続するタスク）の集合をE とする．この例では E = {V2 , V3 } となる．
本手法では，各期間の割当てに重み付きグラフを作成する．
期間１において作成されるグラフは図 4 である．なお，重みが0 となるエッジは省略している．グラフ作成の詳細は後述する
が，概要は図 6 に示す通りである．W eight w はその期間に割当てることが可能なグループの人数を，W eight t は集合２中のタスク T2 について，stock(T2 ) で算出される．本手法ではこの作成した重み付きグラフに対してフォードファルカーソン法
を用いて最大流を求めることで割当てを行う．図 4 のような場
合，考えうるフローの 1 つは (input, G1 , V1 , Vin , output) である．これは，ワーカグループ G1 に対して，タスク V1 をタス
ク Vin の処理結果を利用し，割り当てると解釈する．なお，このとき Vin の処理結果を利用すると述べたが，Vin は例外として処理するべきタスクインスタンスの最大数を管理するための処置であり，実際には処理するべきタスクが存在するわけではない．このようにして，1 つのフローを 1 つの割当てとみなし，最大流を求めることで期間内に可能な限り多くのワーカグルー
プに割当てる手法が最大流問題利用型の手法である．期間１では，考えうる最大流の 1 つは (input, G1 , V1 , Vin , output) と(input, G2 , V1 , Vin , output) の 2 つである．これより，G1 に V1
を，G2 に V1 を割当て，いずれも Vin の処理結果を利用する．
次に，更新作業を行う．この時，Vin の結果を利用していることから，stock(Vin ) = 3 − 2 = 1 また，V1 に 2 人のワーカが割当てられていることから，stock(V1 ) = 0 + 2 = 2 とする．以上
で，更新作業を終了し，期間２の割当てに移る．
期 間 ２ で 作 成 さ れ る グ ラ フ は 図 5 の 通 り で あ る ．こ こから考えうる最大流の 1 つは (input, G1 , V1 , Vin , output) と(input, G3 , V2 , V1 , output) の 2 フローである．これより，更新作業を行い，stock(Vin ) = 1−1 = 0，stock(V1 ) = 2−1+1 = 2，

stock(V2 ) = 0 + 1 = 1 で あ る ．最 後 に ，Nt の 算 出 を 行∑
う．こ こ で ，Nt =v∈E stock(v) で あ る ．よって ，Nt =stock(V2 ) + stock(V3 ) = 1 + 0 = 1 となる．以上より，Nt = 1
であり，割当てとして，期間１で G1 と G2 に V1 ，期間２で G1に V1 ，G3 に V2 の割当てが得られる．
以下，アルゴリズムの詳細について解説する．まず，アルゴ
リズム中で使用している関数について解説する．

•

terminal?(Ei )– エッジ Ei が終端を表すノード Vout に向かうエッジであるかどうかを判定する– Vout に向かうエッジであれば true を返す•

extract-terminal(Ei )– Vout に向かうエッジから実際の終端ノードを抽出する– (Vn , Vout ) のようなエッジの場合，Vn を抽出する•

make-graﬀ(stock, Workﬂow, At , Gw , Gs , Gt )– 以下のような割当て用グラフ（図 6）を作成する– ワーカグループ集合には |Gw | 個のノード（gi (∈ Gw )）が含まれる

– サブタスク集合１には Vin と Vout を除く V 中の各ノード（vj (∈ V )）が含まれる– サブタ ス ク 集 合 ２に は Vout を除 く V 中 の 各 ノ ー ド（vk (∈ V )）が含まれる– Weightw はエッジの始点もしくは終点となっているワー
図 6: 割当て用グラフの作成

カグループ集合中のノード gi について，Gs (gi ) である– Weightt はエッジの始点もしくは終点となっているサブ
タスク集合２中のノード vk について，stock(vk ) である(input, g1 , v1 , vin , output)）– input からワーカグループ集合中の各ノード，およびサ– 5 つのノードは順に，input，ワーカグループ集合中のブタスク集合２中の各ノードから output へはそれぞれ 1 本ずノード（例：g1 ），サブタスク集合１中のノード（例：v1 ），サ

つのエッジを伸ばす

ブタスク集合２中のノード（例：vin ），output である– ワーカグループ集合中の各ノード（gi ）からサブタスク– これらのうち，ワーカグループ集合中のノード（例：g1 ）集合１中の各ノード（vj ）へは vj ∈ Gt (gi ) である場合にエッが割当先ワーカグループ，サブタスク集合１中のノード（例：ジを伸ばすv1 ）が割当てるサブタスク，サブタスク集合２中のノード（例：– サブタスク集合１中の各ノード（vj ）からサブタスク集
合２中の各ノード（vk ）へは (vk , vj ) ∈ E である場合にエッジ

vin ）が必要となる先行サブタスクのインスタンスの供給元を
表す

を伸ばす

– 以上から割当てとして，割当て期間，割当先グループ，割•当てるサブタスクのデータを取り出し，返す（例：[2, g1 , v1 ](たford(graph)– graph に対してフォードファルカーソン法を適用するだし，この例では i=2)）– 返り値を保存する passes を初期化する•– 増大路を探索し，みつかった順に passes に保存する– simpliﬁedj により stock の値を更新する関数である– 返り値として保存した増大路の集合 passes を返す•

simplyfy(simpliﬁed, roadsj )– 増大路 roadsj を単純化する関数である– 例えば，(input, g1 , v1 , vin , output) のような５つのノードから構成される増大路が最も単純な増大路である– 一方で，フォードファルカーソン法の適用では増大路（roadsj ）がupdate-stock(simpliﬁedj , stock)– simpliﬁedj の構成は上述の通りであり，この関数ではサ
ブタスク集合１中のノード vm とサブタスク集合２中のノード

vn を使用する– stock(vm ) = stock(vm ) + 1 お よ び ，stock(vn ) =stock(vn ) − 1 の処理を行い，タスクインスタンスの処理状況を記録する stock を更新する– stock を返す

pa = (input, g1 , v1 , g1 , v2 , v1 , output) のような形で逆向きの

以下，アルゴリズムについて概説する．１〜１６行目では，必エッジ（このパスの場合，v1 , g1 の部分）を含むことがあり，こ要な変数の初期化を行っている．Allocation は割当てを保存すのような場合，以下のような手順で単純な増大路へ変換する

る変数，Nt は完成したパスの数をカウントする変数，terminal– 逆向きのエッジに対して正順のエッジ（上記の例の場

はパスの終端となるサブタスクの集合を保存する変数である．

合 g1 , v1 ）を考え，これを含む増大路 (この例のような場合

４〜８行目では，terminal に該当するサブタスクを登録していpb = (input, g1 , v1 , vin , output) など) を simpliﬁed 中から探索

る．９〜１６行目では，各サブタスクまでの処理済み（処理待する（フォードファルカーソン法の性質上必ず存在する）

ち）タスクインスタンスの数を保存する変数 stock の初期化を– 単純化されていない増大路（例：pa ）を当該逆向きエッジ行っている．なお，stock(Vn ) はサブタスク Vn について，その（例：v1 , g1 ）で 2 つのパスに分割する（例：a1 = (input, g1 , v1 )タスクまで処理が終了している（次のサブタスクは終了していと a2 = (g1 , v2 , v1 , output)）ない）タスクインスタンスの数を表す．stock(Vin ) には処理す– 次に，既に単純化されている増大路（例：pb ）を当該正るべきタスクインスタンスの最大数を入れ，その他のサブタス

順エッジを削除し，2 つのパスに分割する（例：b1 = (input)

ク Vn （Vout のぞく）に対応する stock(Vn ) には 0 を入れる．

と b2 = (vin , output)）

１７〜２９行目では，実際に割当てを行っている．１８〜２– それぞれの増大路から作成された 4 つのパスをクロス

８行目は各期間ごとに行う処理である．１８行目では，フォー

するように（例：a1 と b2 ，および b1 と a2 ）連結する（例：

ドファルカーソン法の適用により探索された増大路の集合を(input, g1 , v1 , vin , output) と (input, g1 , v2 , v1 , output)）

保存する roads を初期化している．１９行目では，当期間にお– 以上の手順により作成された 2 つのパスが両者ともに単ける割当て用グラフを作成し，graph に保存している．２０行

純化されていれば，両者を simpliﬁed に保存する，そうでなけ

目では，作成した graph に対してフォードファルカーソン法をれば単純化されていないパスについて上述の手順を繰り返す

適用し，roads に順に増大路を登録している．２１〜２３行目•

extract-allocation(i, simpliﬁedj )– simpliﬁedj から割当てを取り出す関数である– simpliﬁedj は 5 つ の ノ ー ド か ら 構 成 さ れ る（ 例：では得られた増大路の集合 roads に対して，増大路を単純化することで最大流問題の解となるフローの集合 simpliﬁed を求める．２４〜２７行目では simpliﬁed に対して，当期間の割当てを保存するとともに，次の期間の割当てのために stock を更新している．２５行目では，各フローから割当てを導出し，期4. 1 概説

試行 1 回における実験の手順は以下の通り（図 2 参照）である．

間と合わせて整形し extracted に保存している．２６行目では（ 1 ） ワークフロー W orkf low およびワーカ生成確率 P に

extracted を Allocation に保存している．２７行目では，各フ基づき 1 人のワーカを生成し，プールされたワーカ集合 W にローから stock の更新を行っている．

追加する

３０〜３２行目では，Nt のカウントを行っている．各パスの（ 2 ） ワークフロー W orkf low を考慮し，W に対して割当終端となるサブタスクの集合に対して，各サブタスクの stockて手法 M ethod を適用するを求め，それらの合計を Nt とする．

（ 3 ） 予想処理可能タスク数 Nt を算出し，Nt と希望処理タ

Algorithm 3 Allocation Algorithm 2
Input: N , Dt , Workﬂow, At , Gw , Gs , Gt
Output: Allocation, Nt
Initialisation :1: Allocation = ∅2: Nt = 0
3: terminal = ∅4: for i = 1 to |E| do
5:
6:
7:

if terminal?(Ei ) == true thenterminal.push(extract-terminal(Ei ))end if

スク数 Dt を比較する（ 4 ） Nt < Dt であれば１から３を繰り返す（ 5 ） Nt >= Dt であれば，結果を記録しシミュレーションを終了する
また，実験条件を構成する要素の詳細は以下の通りである．

•

ワーカ生成確率 P

ワーカの能力数について以下の 3 通りの確率 P のもと，能力数 a を決定し，それに基づきワーカを生成する．ただし，ワー
カの能力数についてサブタスクに必要な能力の種類の総数を

8: end foramax ，サブタスクに必要な能力の最小数を amin としたとき

9: stock = ∅に，ahalf = (amax + amin )/2 と定義し，a について，「能力が10: for i = 1 to |V | do

多い」状態を a >「能力が少ない」状態を a <= ahalf ，= ahalf と

11:

if Vi == Vin then12:

stock(Vin ) = Dt

13:
14:
15:

else
stock(Vi ) = 0
end if

16: end for
17: for i = 1 to N do
18:

roads = ∅19:graph = make-graph(stock, Workﬂow, At , Gw , Gs , Gt )20:

roads = ford(graph)21:

for j = 1 to |roads| do

22:

simpliﬁed = simplyfy(simplyﬁed, roadsj )23:

end for24:

for j = 1 to |simpliﬁed| do

する．この時，(30, 70) のような確率は「能力が多い」状態にあるワーカを生成する確率が 30%，
「能力が少ない」状態にある
ワーカを生成する確率が 70% であることを表している．

– P (basic) = (50, 50)– P (high) = (70, 30)– P (low) = (30, 70)
また，amin <=a<= ahalf および，ahalf <=a<= amax を満たす
ような整数 a が複数存在する場合には a の値は等確率で決定されるが，ahalf が整数である場合にはその確率を他の値と比べて 12 とする．これは，能力数 ahalf であるワーカが過剰に生成されることを防ぐための処理である．その後，サブタスクに必25:

extracted = extract-allocation(i, simpliﬁedj )26:

Allocation.push(extracted)

要な能力全ての集合から，等確率で a 個の能力を生成するワー

stock = update-stock(simpliﬁedj , stock)

カに与える．ただし，与えられたタスクの集合ではいずれのサ

27:
28:

end for

29: end for
30: for i = 1 to |terminal| do
31:

Nt = Nt + stock(terminali )ブタスクも実行不可能であるような場合には，a を変化させずに再度，タスクを a 個与える処理を繰り返す．また，ワーカ生
成では，P に依らず以下の処理を行う．等確率で 1 <=n<=5を

32: end for満たす整数 n を決定し，期間長 N の範囲内で n 箇所をメイン

33: return Allocation, Nt

タスクへ参加可能であると表示し，ワーカのスケジュールとして付与する．

•

4 評価実験
本章では，評価実験について述べる．本研究では，シミュレー
ションにより評価実験を行った．実験ではワーカ生成確率 P ，ワークフロー W orkf low，手法 M ethod の 3 つの要素を変化させ，実験条件を作成した．また，各条件につき 20 回の試行を行い平均化を行った．本研究では，2 種類の評価実験を行った．以下概説で試行 1 回の処理について解説し，その後，2 種類の評価実験について述べる．

ワークフロー W orkf low

3 種類のワークフローを使用した．以下にその構造を示す．
ただし，ここでいう W orkf low には前述のサブタスクに必要な能力 At も含まれるものとする．

– W orkf low(A) シンプルな構造をもつ仮想のワークフローである．構造は図 7 の通り．また，サブタスクに必要な能力は以下の通り．

∗ Ability = {a1 , a2 , a3 , a4 }∗ At = {(V1 , [a1 ]), (V2 , [a2 ]), (V3 , [a3 )], (V4 , [a4 ]),下の通り．

∗ Ability = {a1 , a2 , a3 , a4 }∗ At = {(V1 , [a1 ]), (V2 , [a2 ]), (V3 , [a1 ]), (V4 , [a1 , a3 ]),(V5 , [a1 , a3 ]), (V6 , [a4 ]), (V7 , [a4 ]), (V8 , [a1 ])•手法 M ethod

３章で示した２つの提案手法のいずれかを指定する．

– M ethod(m1 ) 既存手法拡張型の手法を適用する．なお，手法の比較実験では，こちらの手法をベースラインとして，最大流問題利用型の手法を評価する．

– M ethod(m2 ) 最大流問題利用型の手法を適用する．手法
図 7: Workﬂow(A)の比較実験では主にこちらの手法について評価することを目的とする．
また，全ての実験条件で共通して使用する値（要素）は以下の
通り．

•

期間長 N

N = 60•

希望処理タスク数 DtDt = 100
次に，評価実験において取得するデータについて解説する．評
価実験の結果として取得する指標は以下の通りである．
図 8: Workﬂow(B)•inclusion インクルージョン性を評価する指標である．定義は２章に示した通りである．

•

inﬂux Nt >= Dt を満たすために要したワーカの数であり，inﬂux = |W | で定義する．割当ての効率性を評価するための指標である．値が小さいほど，より少ないワーカにより目標
数のインスタンスを処理できたことを表す．

•

loss ワーカを割り当てたが，パス内に存在する全てのサブタスクにワーカを割り当てることができずインスタンスの処理が終了しなかったもの，もしくは割当てを行ったが Nt > Dtとなり余剰となったインスタンスの割合である．このようなパnlスの数を nl として， Dと定義する．値が小さいほど，より無t

図 9: Workﬂow(C)(V5 , [a1 , a2 ]), (V6 , [a3 , a4 ]), (V7 , [a1 , a2 , a3 , a4 ])}駄の少ない割当てであることを表す．

5 手法の比較評価– W orkf low(B) 日本手話を英語の手話に翻訳するという

本節では 2 手法を比較評価する評価実験について述べる．

メインタスクに対して，実際に使用されたワークフローであ

ベースラインとして既存手法拡張型の手法を設定し，最大流問る [11]．構造は図 8 の通り．また，サブタスクに必要な能力は

題利用型の手法の評価を行うことが目的である．詳細は以下に以下の通り．

述べる通り．

∗ Ability = {JSL, J, E, ASL}

実 験 条 件 は ワ ー カ 生 成 確 率 P を 3 通 り，ワ ー ク フ ロ ー∗ At = {(V1 , [JSL, J]), (V2 , [J, E]), (V3 , [E, ASL]),W orkf low を 3 通りから作成した計 9 通りのワーカのフロー(V4 , [JSL, J, E]), (V5 , [E, ASL]), (V6 , [JSL, J]),とワークフローの組に対して，2 つの手法 Method を適用した(V7 , [J, E, ASL]), (V8 , [JSL, J, E, ASL])}

計 18 の実験条件を使用した．この際，各条件に対して，20 回– W orkf low(C) 音声データを文字データに書き起こすとの試行を行い平均化を行っている．また，使用したワーカのフいうメインタスクに対して考えられるワークフローである [11]．

ローの違いによる影響を軽減するため，ワーカのフローについ

ただし，本研究で使用可能なワークフローの構造に合わせるたてはあらかじめ十分な数のワーカのリストを条件に基づき生成

め，引用元と比較して統合のサブタスクを削除している．また，した．このリストについて，両手法とも同一のリストを 1 試

音声認識のサブタスクは引用元では記されているが，実際には行分として先頭から読み込むことで疑似的なワーカのフロー

機械により自動化された作業であるため，本論文では省略してを再現し，なおかつワーカのフローの違いによる影響を軽減いる．構造は図 9 の通り．また，サブタスクに必要な能力は以している．これらの実験条件について，以降 basicCm1 のような形式で表現し，この例のような場合，実験条件が P (basic)，

W orkf low(C)，M ethod(m1 ) であることを示す．また，指標には inclusion，inﬂux，loss を使用する．

5. 1 手法の特性評価
本節では手法の特性を検証する評価実験について述べる．本

表 3: Workﬂow(A)条件

inclusion inﬂux

loss

highAm1

94.0

70.1 11.6

highAm2

96.9

63.2

basicAm1

93.7

84.0 17.30basicAm2

96.7

77.4

節で述べる評価実験の目的は，割当てに時間経過（スケジュー

lowAm1

94.7

103.0 16.50ル）の考えを導入することによる利点を検証する点にある．こlowAm2

97.1

97.0

0

れは以下のような想定のもと行う実験である．
本研究では，時間経過（スケジュール）を取り入れることに

表 4: Workﬂow(B)より，30(min) × 12(set) × 5(day) のような形式で長期間にわ条件

たるメインタスクの募集に対応可能であり，かつ 1 回あたりのhighBm1

75.2

67.7

inclusion inﬂux

loss
5.5

拘束時間は 1 セット分 (30 分) に抑えることが可能である．一

highBm2

85.3

58.4

0

方，従来の割当て手法では時間経過が考慮されないため，例えbasicBm1

68.4

88.7

5.5

ば 5 日間で行うメインタスクへの参加は期間中全ての拘束時間

basicBm2

79.5

78.6

0

（上記例と同様の規模の場合 30 時間）を生じる．しかし，この

lowBm1

60.5

123.7 25.2

ような長期の拘束は現実的とはいえず，実際には期間の分割等

lowBm2

72.7

108.0

0

により対応することが想定される．一方で，期間を分割する場
表 5: Workﬂow(C)合においても課題は存在する．従来手法には著者の知る限り処理途中のインスタンスを考慮し，次の期間に引き継ぐといった

条件

期間をまたぐような割当て手法は存在しない．それゆえ，全てhighCm1

97.2

68.5

の期間を一括して割当てを行う場合と比較するとロスが生じることが想定される．これにより，従来手法の適用により募集を大規模化（長期化）する場合には，このようなロスを考える必要がある．そこで，本研究では，疑似的に期間の分割を再現す

inclusion inﬂux loss
5.9

highCm2

98.6

68.7

0

basicCm1

94.5

71.7

5.4

basicCm2

98.1

72.2

0

lowCm1

93.4

73.0

5.1

lowCm2

98.2

73.6

0

ることで，こうしたロスを生じない本研究の手法の有用性を検証する．具体的な実験の詳細は以下の通りである．
前述の実験条件に加え，実験条件を構成する要素に分割数

Sep を追加する．Sep は期間長を Sep の数に等分割することを示しており，例えば Sep = 3, N = 60 の時，N = 20 であ

6 実験結果と考察
6. 1 手法の比較評価

る期間 3 つに分割することを示す．本評価実験では，Sep を手法の比較評価実験の結果を以下に示す．表 3，表 4，表 5

1<= Sep <= 6(Sep ∈ N) の範囲で変化させる．割当て手法の適用については，分割された各期間 m(1 <=m<= Sep) について独にワークフローごとの結果を表す． 以下，ワークフローごとに立に割当て手法を適用し，期間 m で想定される処理可能タス∑
ク数 Nt (m) を算出，Nt = Sep
m=1 Nt (m) であるとする．また，

まず，W orkf low(A) について，inclusion，inf lux，loss の
いずれについても最大流問題利用型の手法が優位であった．まワーカのフローの生成等については概ね上述と同様の手順を踏た，ワーカのもつ能力数による影響は，inclusion に関しては

むが，ワーカのスケジュールについては，先頭から Sep に分割

いずれの手法を取ったとしても大きな違いは生じていない．一

結果を確認する．

したものを順に期間 m のワーカのスケジュールであるとする．

方，inf lux については，いずれの手法についても，ワーカの能

例えば，N = 6, Sep = 2 である時に Sw (w1 ) = [1, 0, 1, 1, 0, 0]

力数が少ないほど低い多くのワーカを必要とする傾向が存在すであるワーカ w1 が生成されている場合，期間 m = 1 においてることがわかる．loss については手法の性質上，最大流問題利Sw (w1 ) = [1, 0, 1]，m = 2 において Sw (w1 ) = [1, 0, 0] である

用型の手法についてはいずれにおいても 0 を維持している．既とみなす．つまり，ワーカ w1 が W に追加されるということ

存手法拡張型の手法については能力数の多いワーカが過半数とは，分割された各期間全てについてワーカ w1 が分割されたス

なる条件と，平均的な分布の条件とで違いが生じているが，一ケジュールを以って参加することを示す．

方で，能力数が少ないワーカが過半数となる条件と平均的な分本実験ではワーカ生成確率 P を P (basic) の 1 通り，ワーク布との間では大きな違いは生じていない．

フロー W orkf low を 3 通り，手法 Method を 2 通り，分割数

次 い で ，W orkf low(B) に つ い て で あ る が ，こ ち ら もSep を 1 <= 6(Sep ∈ N) の 6 通り，計 36 通りの実験条= Sep <

inclusion，inf lux，loss のいずれについても，最大流問題件を使用した．また，指標には inclusion，inﬂux，loss を使用

利用型の手法が優位である．また，ワーカのもつ能力数によるする．

影響は inclusion および inf lux において見られ，手法の違い
を問わず能力数が多いワーカの割合が高いほど良い結果を示す

ことが見て取れる．また，loss について，最大流問題利用型の手法については W orkf low(A) と同様に常に 0 を示している．
一方，既存手法拡張型の手法については，W orkf low(A) の条
件とは異なり，ワーカの分布が平均的である条件と，能力数の低いワーカの割合が高い条件との間で大きな違いができている．

W orkf low(C) に つ い て は ，他 の 2 つ の 条 件 と 異 な り，
inclusion において，既存手法拡張型の手法が優位を示している．また，inf lux については手法間に大きな違いは見られず，loss については，引き続き最大流問題利用型の手法が優位である．ワーカの能力数による影響については，inclusion において手法間で違いが見られ，既存手法拡張型の手法はほとん
ど影響を受けないのに対して，最大流問題利用型の手法では能力数が少ないワーカの割合が高くなるにつれ低下する傾向が見られる．inf lux については，影響は小さいものの，両手法とも能力数が少ないワーカが増えるにつれ inf lux が増加する傾向が見て取れる．loss については，最大流問題利用型の手法では他のワークフローと同様である．一方，既存手法拡張型の手法では，能力数の少ないワーカの割合が高いほど loss が減少するという通常想定されるものとは逆の結果が見て取れる．しかし，他のワークフローの条件と異なり，その差は 1 未満であり，誤差であると考えられる．
以上から，最大流問題利用型の手法は必要なワーカの数を抑える，未完成のパスを減らすという評価観点において既存手法拡張型の手法に比べ優れているといえる．また，インクルージョン性についても，多くの場合において高い値を取る．以上
から，最大流問題利用型の手法は概ね既存手法拡張型の手法よりも優れた手法であると判断できる．一方で，グラフの形状・条件により，結果に影響があるということも示されており，この点についてはワークフローの多様性への対応のため，さらなる追究が必要である．

6. 2 手法の特性評価
手法の特性評価実験の結果，分割数の増加による影響は主にinﬂux ，loss の割当の効率性に関係する指標に表れることが分かった．なお，詳細な結果については紙幅の都合上割愛する．

7 ま と め
本論文では，時間の明示化という概念をクラウドソーシングのタスク割当てに導入し，それに対する割当て手法を 2 種類提案した．1 つは既存手法に時間制約を取り入れ拡張したものであり，もう一方は最大流問題を活用し，割当てを行う手法である．これらの手法に対して，評価実験ではワーカの能力数の分
布，ワークフローの条件を変化させ 2 手法間の比較および，手法の特性についてワーカのインクルージョン性，必要なワーカ
数，割当てのロスの 3 つの観点から検証した．手法間の比較により，最大流問題を利用した手法が多くの条件で優位であること，また，時間の明示化という概念を導入することによる手法の特性として，主に割当ての効率性（必要なワーカ数，割当てのロス）という面で効果的であることが示せた．

文

献[1] Ho, Chien-Ju, Vaughan, Jennifer. Proceedings of the ...
AAAI Conference on Artiﬁcial Intelligence: Adaptive Task
Assignment for Crowdsourced Classiﬁcation. 2021, vol. 26,
no. 1, p. 45–51.
[2] Sihem Amer-Yahia, Senjuti Basu Roy. Toward WorkerCentric Crowdsourcing. Bulletin of the Technical Committee on Data Engineering. 2016, vol. 39, no. 4, p. 3-13.
[3] Kulkarni, Anand, Can, Matthew, Hartmann, Björn. Collaboratively crowdsourcing workﬂows with turkomatic. ACM,
2012, 1003–1012p., (CSCW).
[4] 西 記代子. MLA 機関によるクラウドソーシングの活用について: 欧米の事例と日本における導入の可能性 (小特集 アーカイブ
ズ・ノート). 国文学研究資料館紀要. アーカイブズ研究篇 = Thebulletin of the National Institute of Japanese Literature. 人
間文化研究機構国文学研究資料館 編. 2018, no. 14, p. 103-112.
[5] Ambati, Vamshi, Vogel, Stephan, Carbonell, Jaime. Collaborative workﬂow for crowdsourcing translation. ACM, 2012,
1191–1194p., (CSCW).
[6] Tran-Thanh, Long, Huynh, Trung Dong, Rosenfeld, Avi,
Ramchurn, Sarvapali, Jennings, Nicholas. Proceedings ofthe ... AAAI Conference on Artiﬁcial Intelligence: Crowdsourcing Complex Workﬂows under Budget Constraints.
2015, vol. 29, no. 1.
[7] Jiang, Jiuchuan, An, Bo, Jiang, Yichuan, Shi, Peng, Bu,
Zhan, Cao, Jie. IEEE transactions on parallel and distributed systems: Batch Allocation for Tasks with Overlapping Skill Requirements in Crowdsourcing. 2019, vol. 30, no.
8, p. 1722–1737. https://ieeexplore.ieee.org/document/8620370.
[8] Xiao, Lei, Gao, Zhigang, Xu, Ruichao, Wu, Bo, Zheng,
Leilei, Cen, Weipeng, He, Xuanzhang, Zhao, Wei. An allocation method of crowdsourcing tasks for protecting fairnessof participants.
[9] Goto, Shinsuke, Ishida, Toru, Lin, Donghui. Understanding
Crowdsourcing Workﬂow: Modeling and Optimizing Iterative and Parallel Processes. 2016.
[10] Ho, Chien-Ju, Vaughan, Jennifer. Proceedings of the ...
AAAI Conference on Artiﬁcial Intelligence: Online Task
Assignment in Crowdsourcing Markets. 2021, vol. 26, no.
1, p. 45–51.
[11] A Task Assignment Method Considering Inclusivenessand Activity Degree, Hashimoto,H.; Matsubara,M.; Shiraishi,Y.; Wakatsuki,D.; Zhang,J.; Morishima,A. IEEE, Dec
2018, p. 3498-3503.
[12] U. Pferschy and J. Schauer, The maximum ﬂow problem with disjunctive constraints, Journal of Comb. Optim.
(2013), 26:109-119[13] 総 務 省. ”ICT に よ る 多 様 な 人 材 の 労 働 参 加 促 進:
ク ラ ウ ド ソ ー シ ン グ の 広 が り”. 情 報 通 信 白 書.
https://www.soumu.go.jp/johotsusintokei/whitepaper/ja/h30/html/nd16(accessed 2020-7-15).
[14] Rokicki, Markus, Zerr, Sergej, Siersdorfer, Stefan. Groupsourcing. ACM, 2015, 906–915p.
[15] Wang, Wanyuan, Jiang, Jiuchuan, An, Bo, Jiang, Yichuan,
Chen, Bing. IEEE transactions on cybernetics: Toward Eﬃcient Team Formation for Crowdsourcing in Noncooperative
Social Networks. 2017, vol. 47, no. 12, p. 4208–4222.
[16] Jiang, Jiuchuan, Zhou, Yifeng, Jiang, Yichuan, Bu, Zhan,
Cao, Jie. Knowledge-based systems: Batch allocation fordecomposition-based complex task crowdsourcing e-markets
in social networks. 2020, vol. 194.