私は現在、仕事のためのシフトスケジューリングアルゴリズムに取り組んでいます。私たちのシフトスケジュールは完全に4-3（4日オン、3日オフ）と4-3のローテーション（例：日曜日、月曜日、火曜日、1週間と翌週オフ、日曜日、金曜日、土曜日オフ）で構成されています）-日曜日から土曜日までの週。
「ストレート」4-3シフトまたは回転4-3のいずれかの49の可能なバリエーションがあります。24時間年中無休の運用であるため、7日間すべてを考慮する必要があります。現在、これをアーリーシフトで11人、レイトシフトで12人の小規模なワークグループに利用していますが、このアルゴリズムを拡張したい200人ものワークグループが他にもあります。
基本的な前提は、管理グループには毎日必要な人員があり、アルゴリズムは必要な人員を与える初期シフトと後期シフトのセットのみを返すことです。
11人に49の可能なシフトを（繰り返しで）配置し、それらすべての可能な組み合わせを分類するのに数千年かかることが非常に早く明らかになりました。その結果、49シフトのリストを、最も一般的に使用されるシフトの約16〜20に選別することができました。
それはそれを扱いやすくしますが、11人か12人だけです。明らかに、可能な組み合わせの数は、人が追加されるたびに指数関数的に増加します。現在のところ、私のアルゴリズムは次のことを行います。
私は変数として、2週間にわたって、そこにある曜日ごとに「オンシフト」と「オフシフト」を表す1と0のシフトの束を持っています。今のところサンプルのみを使用します。例：
h = [0,1,1,1,1,0,0,0,1,1,1,1,0,0]
e = [0,0,1,1,1,1,0,0,0,1,1,1,1,0]
d = [0,0,0,1,1,1,1,0,0,0,1,1,1,1]
c = [1,1,1,1,0,0,0,1,1,1,1,0,0,0]
m = [0,1,1,0,1,1,0,0,1,1,0,1,1,0]
p = [1,1,0,0,0,1,1,1,1,0,0,0,1,1]
q1 = [1,1,1,0,0,0,1,1,1,1,0,0,0,1]
a = [1,0,0,0,1,1,1,1,0,0,0,1,1,1]
次に、約16〜20（この例では8のみを使用します）シフトのリストがあります。これは、排他的ではないにしても、最も一般的に使用されます。さらに、計算する人数の変数と、マネージャーの要件の変数（early_count）：
shifts = [h,e,c,d,m,p,q1, a]
early_bid_personnel = 11
early_count = [5,6,7,7,6,8,5]
次に、ジェネレータ式でアーリーシフトの可能なすべてのシフトの組み合わせを作成し、日曜日が必要な数（5）になるかどうかを確認します。日曜日に合計されるものは、monジェネレーター式によって参照され、それらすべての月曜日は表にされてから、火曜日リストによって参照されます。私はこれを14日間にわたって行います。これは、交代制勤務によって2週目の人員のバランスが歪むためです。
sun = (combs for combs in combinations_with_replacement(shifts,early_bid_personnel) if (sum(combs[i][0] for i in range(0,early_bid_personnel)) == early_count[0]))
mon = (mon for mon in sun if (sum(mon[i][1] for i in range(0,early_bid_personnel)) == early_count[1]))
tue = (tue for tue in mon if (sum(tue[i][2] for i in range(0,early_bid_personnel)) == early_count[2]))
wed = (wed for wed in tue if (sum(wed[i][3] for i in range(0,early_bid_personnel)) == early_count[3]))
thu = (thu for thu in wed if (sum(thu[i][4] for i in range(0,early_bid_personnel)) == early_count[4]))
fri = (fri for fri in thu if (sum(fri[i][5] for i in range(0,early_bid_personnel)) == early_count[5]))
sat = (sat for sat in fri if (sum(sat[i][6] for i in range(0,early_bid_personnel)) == early_count[6]))
sec_sun = (sec_sun for sec_sun in sat if (sum(sec_sun[i][7] for i in range(0,early_bid_personnel)) == early_count[0]))
sec_mon = (sec_mon for sec_mon in sec_sun if (sum(sec_mon[i][8] for i in range(0,early_bid_personnel)) == early_count[1]))
sec_tue = (sec_tue for sec_tue in sec_mon if (sum(sec_tue[i][9] for i in range(0,early_bid_personnel)) == early_count[2]))
sec_wed = (sec_wed for sec_wed in sec_tue if (sum(sec_wed[i][10] for i in range(0,early_bid_personnel)) == early_count[3]))
sec_thu = (sec_thu for sec_thu in sec_wed if (sum(sec_thu[i][11] for i in range(0,early_bid_personnel)) == early_count[4]))
sec_fri = (sec_fri for sec_fri in sec_thu if (sum(sec_fri[i][12] for i in range(0,early_bid_personnel)) == early_count[5]))
sec_sat = (sec_sat for sec_sat in sec_fri if (sum(sec_sat[i][13] for i in range(0,early_bid_personnel)) == early_count[6]))
繰り返し処理するsec_sat式は、カスタム辞書で1と0の文字列を検索し、それをシフト割り当ての実際の文字に変換します。それから私は基本的に遅いシフトのためにまったく同じことを繰り返します。この2つを組み合わせると、マネージャーは探している正確な数を知ることができます。これは問題なく機能します。たとえば、8シフトしかない11人が早い段階から選択し、12人が8シフト遅れて選択します。しかし、ワークグループのサイズがたとえば20人に拡大し、12、14、16を使用するか、49シフトすべてをあえぎながらシフトを決定したい場合、それでもかなり不合理です。
私は、最初のジェネレータ式がまだ各組み合わせを置換でチェックし、日曜日が合計されたものだけを返すことを理解しています。それが主要な問題です。これをO（n ^ 2）よりも良くしたり、悪くしたりする方法を見つけるために、私は真剣にいくつかの助けを使うことができました。
考えられるすべての組み合わせを生成し、それぞれをチェックする方法はありますか？また、最大5'a 'シフトなど、最初のジェネレータ式にいくつかの制約を設定すると、次のようになります。
sun = (combs for combs in combinations_with_replacement(shifts,early_bid_personnel) if (sum(combs[i][0] for i in range(0,early_bid_personnel)) == early_count[0]) and combs.count(a) <= 5)
ジェネレータ式はまだ何かを生成する必要があります。5つ以下の「a」シフトがあるかどうかを確認し、それ以上ある場合はスキップします。
この問題を解決するには、モンテカルロシミュレーションを使用できます。可能なすべての組み合わせを実行する必要はありません。基準を満たすものを見つける必要があるだけで、たくさんあります。あなたの問題を再定義させてください。する[日、月、火曜、...、sec_sat]上司の要件。[q1、q2、...、q49]は、49の異なるシフトのそれぞれの人数になります。そしてマトリックス：
s1[0] s1[1] ... s1[13] s2[0] s2[1] ... s2[13] .................... s49[0] s49[1] ... s49[13]
は、すべてのシフトおよび曜日のオン/オフテーブルです。例：日曜日がシフト1の当日である場合、s1 [0]は1になり、それ以外の場合は0になります。s3 [7]は、第2日曜日がシフト3の当日である場合は1、それ以外の場合は0になります。などなど。この定義を使用すると、問題を次のように書き直すことができます。
sun <= q1*s1[0] + ... + q49*s49[0] mon <= q1*s1[1] + ... + q49*s49[1] tue <= q1*s1[2] + ... + q49*s49[2] wed <= q1*s1[3] + ... + q49*s49[3] thu <= q1*s1[4] + ... + q49*s49[4] fri <= q1*s1[5] + ... + q49*s49[5] sat <= q1*s1[6] + ... + q49*s49[6] sec_sun <= q1*s1[7] + ... + q49*s49[7] sec_mon <= q1*s1[8] + ... + q49*s49[8] sec_tue <= q1*s1[9] + ... + q49*s49[9] sec_wed <= q1*s1[10] + ... + q49*s49[10] sec_thu <= q1*s1[11] + ... + q49*s49[11] sec_fri <= q1*s1[12] + ... + q49*s49[12] sec_sat <= q1*s1[13] + ... + q49*s49[13]
あなたの未知数は[q1、q2、...、q49]です。残りは知られています。シミュレーションを使用して解決策を見つける方法は？ランダムな[q1、...、q49]ベクトルを生成し、基準が満たされているかどうかを確認します。そうである場合は、アルゴリズムを破って結果を返します。例（一種の擬似コード）：
import random # Define your restrictions mon = tue = ......... sec_sat = # Define your shifts s1 = [1,1,1,1,0,0,0,1,1,1,1,0,0,0] s2 = [0,1,1,1,1,0,0,0,1,1,1,1,0,0] ................................... s49 = [...] while True: q = [0]*49 # We place workers in random shifts for i in range(number_of_workers): q[random.randint(0,len(q)-1)] += 1 if (mon <= q[0]*s1[0] + q[1]*s2[0] + ... + q[48]*s49[0]) and (tue <= q[0]*s1[1] + q[1]*s2[1] + ... + q[48]*s49[1]) and ......................................................... (sec_sat <= q[0]*s1[13] + q[1]*s2[13] + ... + q[48]*s49[13]): # Condition met, return result return q
上記の例のソリューションを、シフト数を制限して実装しました。
import random # Restrictions r = [5, 6, 7, 7, 6, 8, 5, 5, 6, 7, 7, 6, 8, 5] # Shifts s = [] s.append([0,1,1,1,1,0,0,0,1,1,1,1,0,0]) s.append([0,0,1,1,1,1,0,0,0,1,1,1,1,0]) s.append([0,0,0,1,1,1,1,0,0,0,1,1,1,1]) s.append([1,1,1,1,0,0,0,1,1,1,1,0,0,0]) s.append([0,1,1,0,1,1,0,0,1,1,0,1,1,0]) s.append([1,1,0,0,0,1,1,1,1,0,0,0,1,1]) s.append([1,1,1,0,0,0,1,1,1,1,0,0,0,1]) s.append([1,0,0,0,1,1,1,1,0,0,0,1,1,1]) number_of_shifts = len(s) number_of_workers = 11 number_of_days = len(s[0]) while True: q = [0]*number_of_shifts for i in range(number_of_workers): q[random.randint(0,len(q)-1)] += 1 t = [sum([q[j]*s[j][i] for j in range(number_of_shifts)]) for i in range(number_of_days)] if sum([r[i] <= t[i] for i in range(number_of_days)]) == number_of_days: print q break
実行するのにそれほど時間はかかりませんでした。これはそれが見つけた解決策の1つです：[0、3、2、2、1、2、1、0]
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加