#############################
# 複雑な待ち行列問題
# coded by Y.Suganuma
#############################
#####################
# クラスInletの定義
#####################
class Inlet
###########################################################
# コンストラクタ
# name1 : 入り口名
# a_t1 # = -n : 到着する客の人数を負の値にしたもの
# # =0 : 指数分布
# # =1 : 一定時間間隔
# m_a： 到着時間間隔またはその平均
# que1 : 客の到着時刻リスト
# name2 : 待ち行列名
###########################################################
def initialize(name1, a_t1, m_a, que1, name2)
@_name = name1 # 入り口名
@_out = name2 # 待ち行列名
@_a_t = a_t1 # = -n : 到着する客の人数を負の値にしたもの
# =0 : 指数分布
# =1 : 一定時間間隔
@_mean = m_a # 到着時間間隔またはその平均
@_que = que1 # 客の到着時刻リスト
if @_a_t == 0
@_arrive_time = -@_mean * Math.log(rand(0)) # 客の到着時刻（負：客がない）
elsif @_a_t == 1
@_arrive_time = 0
else
@_arrive_time = @_que.delete_at(0)
end
@_out_n = 0 # 待ち行列番号（Q_baseのコンストラクタで設定）
end
attr_accessor("_out_n", "_out", "_name", "_arrive_time", "_a_t", "_mean", "_que")
end
#####################
# クラスQueueの定義
#####################
class Queue
#############################################
# コンストラクタ
# name1 : 待ち行列名
# n1 : =0 : 入り口から入る
# >0 : 複数の窓口から入る(窓口数)
# in1 : 入り口名，または，窓口名
# m1 : 処理する窓口数
# out1 : 窓口名
#############################################
def initialize(name1, n1, in1, m1, out1)
@_name = name1 # 待ち行列名
@_n = n1 # =0 : 入り口から入る
# >0 : 複数の窓口から入る(窓口数)
@_inn = in1 # 入り口名，または，窓口名（入り口）
@_m = m1 # 処理する窓口数
@_out = out1 # 窓口名（出口）
@_nc = 0 # 待ち行列への到着客数カウンタ
@_max_q_l = 0 # 最大待ち行列長
@_c_ql = 0.0 # 待ち行列長にその長さが継続した時間を乗じた値の累計
@_ql_t = 0.0 # 現在の待ち行列長になった時間
@_max_wt = 0.0 # 最大待ち時間
@_c_wt = 0.0 # 待ち時間の累計
@_in_n = Array.new() # 入り口番号，または，窓口番号（Q_baseのコンストラクタで設定）
@_out_n = Array.new() # 窓口番号（Q_baseのコンストラクタで設定）
@_que = Array.new() # 待ち行列
end
attr_accessor("_name", "_n", "_m", "_inn", "_in_n", "_out", "_out_n", "_nc", "_c_ql", "_que", "_ql_t", "_max_q_l", "_c_wt", "_max_wt")
end
######################
# クラスEntityの定義
######################
class Entity
########################################
# コンストラクタ
# name1 : 窓口名
# s_t1 # =0 : 指数分布
# # =1 : 一定時間
# m_s：サービス時間またはその平均
# name2 : 待ち行列(入力)の名前
# sw : =0 : システムの外に出る
# =1 : 待ち行列に入る
# name3 : 待ち行列(出力)の名前
########################################
def initialize(name1, s_t1, m_s, name2, sw, name3)
@_name = name1 # 窓口名
@_to = sw # =0 : システムの外に出る
# =1 : 待ち行列に入る
@_inn = name2 # 待ち行列(入力)の名前
if @_to > 0
@_out = name3 # 待ち行列(出力)の名前
end
@_end_time = -1.0 # サービス終了時刻（負：何も処理していない）
@_s_t = s_t1 # =0 : 指数分布
# =1 : 一定時間
@_mean = m_s # 平均サービス時間
@_service = 0 # サービス中の客番号（0のときは無し）
@_busy_t = -1.0 # 窓口がふさがった時刻
@_c_busy = 0.0 # 窓口がふさがっている時間の累計
@_in_n = -1 # 待ち行列(入力)番号（Q_baseのコンストラクタで設定）
@_out_n = -1 # 待ち行列(出力)番号（Q_baseのコンストラクタで設定）
end
attr_accessor("_service", "_name", "_inn", "_in_n", "_to", "_out", "_out_n", "_end_time", "_busy_t", "_s_t", "_c_busy", "_mean")
end
########################
# クラスCustomerの定義
########################
class Customer
#####################
# コンストラクタ
# s1,s2 : 状態
# t : 到着時刻
#####################
def initialize(s1, s2, t)
@_time = t # 到着時刻
@_state1 = s1 # 客の状態1
# =0 : 待ち行列に入っている
# =1 : サービスを受けている
@_state2 = s2 # 客の状態2(待ち行列番号，または，窓口番号）
end
attr_accessor("_state1", "_state2", "_time")
end
#######################
# クラスQ_baseの定義
#######################
class Q_base
########################################
# コンストラクタ
# v_i : Inletオブジェクトリスト
# v_q : Queueオブジェクトリスト
# v_e : Entityオブジェクトリスト
# e : シミュレーション終了時刻
########################################
def initialize(v_i, v_q, v_e, e)
print("\n")
# 接続関係のチェック
@_inl = v_i # Inletオブジェクトリスト
@_que = v_q # Queueオブジェクトリスト
@_ent = v_e # Entityオブジェクトリスト
# Inlet
for i1 in 0 ... @_inl.length-1
for i2 in i1+1 ... @_inl.length
if @_inl[i1]._name == @_inl[i2]._name
print("***error 同じ名前の入り口があります " + @_inl[i1]._name + "\n")
end
end
end
for i1 in 0 ... @_inl.length
k = -1
for i2 in 0 ... @_que.length
if @_inl[i1]._out == @_que[i2]._name
k = i2
break
end
end
if k >= 0
@_inl[i1]._out_n = k
else
print("***error 入り口から入る待ち行列名が不適当です " + @_inl[i1]._out + "\n")
end
end
# Queue
for i1 in 0 ... @_que.length-1
for i2 in i1+1 ... @_que.length
if @_que[i1]._name == @_que[i2]._name
print("***error 同じ名前の待ち行列があります " + @_que[i1]._name + "\n")
end
end
end
for i1 in 0 ... @_que.length
if @_que[i1]._n == 0
k = -1
for i2 in 0 ... @_inl.length
if @_que[i1]._inn[0] == @_inl[i2]._name
k = i2
break
end
end
if k >= 0
@_que[i1]._in_n.push(k)
else
print("***error 待ち行列に入る入り口名が不適当です " + @_que[i1]._inn[0] + "\n")
end
else
for i2 in 0 ... @_que[i1]._n
k = -1
for i3 in 0 ... @_ent.length
if @_que[i1]._inn[i2] == @_ent[i3]._name
k = i3
break
end
end
if k >= 0
@_que[i1]._in_n.push(k)
else
print("***error 待ち行列に入る窓口名が不適当です " + @_que[i1]._inn[i2] + "\n")
end
end
end
for i2 in 0 ... @_que[i1]._m
k = -1
for i3 in 0 ... @_ent.length
if @_que[i1]._out[i2] == @_ent[i3]._name
k = i3
break
end
end
if k >= 0
@_que[i1]._out_n.push(k)
else
print("***error 待ち行列を処理する窓口名が不適当です " + @_que[i1]._out[i2])
end
end
end
# Entity
for i1 in 0 ... @_ent.length-1
k = -1
for i2 in i1+1 ... @_ent.length
if @_ent[i1]._name == @_ent[i2]._name
print("***error 同じ名前の窓口があります " + @_ent[i1]._name + "\n")
end
end
end
for i1 in 0 ... @_ent.length
k = -1
for i2 in 0 ... @_que.length
if @_ent[i1]._inn == @_que[i2]._name
k = i2
break
end
end
if k >= 0
@_ent[i1]._in_n = k
else
print("***error 窓口に入る待ち行列名が不適当です " + @_ent[i1]._inn + "\n")
end
if @_ent[i1]._to > 0
k = -1
for i2 in 0 ... @_que.length
if @_ent[i1]._out == @_que[i2]._name
k = i2
break
end
end
if k >= 0
@_ent[i1]._out_n = k
else
print("***error 窓口の出口にある待ち行列名が不適当です " + @_ent[i1]._out)
end
end
end
# 初期設定
@_p_time = 0.0 # 現在時刻
@_max_c = 0 # 最大系内客数
@_nc = 0 # システムへの到着客数カウンタ
@_now_c_t = 0.0 # 現在の系内客数になった時間
@_c_now_c = 0.0 # 系内客数にその数が継続した時間を乗じた値の累計
@_c_sys = 0.0 # 滞在時間の累計
@_max_sys = 0.0 # 最大滞在時間
@_end = e # シミュレーション終了時間
@_cus = Hash.new() # 系内にいる客のリスト
# 乱数の初期設定
srand()
end
#############
# 全体の制御
#############
def Control()
sw = [0, 0]
while sw[0] > -2
Next(sw) # 次の処理の選択
if sw[0] == -1
sw[0] = End_o_s() # シミュレーションの終了
else
if sw[0] == 0
Arrive(sw[1]) # 客の到着処理
else
Service(sw[1]) # サービスの終了
end
end
end
end
#############################################
# 次の処理の決定
# sw[0] : =-1 : シミュレーションの終了
# =0 : 客の到着処理
# =1 : 窓口のサービス終了
# [1] : 入り口番号 or 窓口番号
#############################################
def Next(sw)
tm = @_end # 次の処理時刻
sw[0] = -1
# 次の客の到着時刻
for i1 in 0 ... @_inl.length
x = @_inl[i1]
if x._arrive_time >= 0.0 and x._arrive_time < tm
sw[0] = 0
sw[1] = i1
tm = x._arrive_time
end
end
# サービス終了時刻
for i1 in 0 ... @_ent.length
x = @_ent[i1]
if x._service > 0 and x._end_time <= tm
sw[0] = 1
sw[1] = i1
tm = x._end_time
end
end
if sw[0] < 0
@_end = @_p_time
end
end
##################################
# 終了処理
# return : =-1 : 終了前処理
# =-2 : 実際の終了
##################################
def End_o_s()
sw = -2
@_p_time = @_end # 現在時刻
for i1 in 0 ... @_ent.length
x = @_ent[i1]
if x._service > 0 # サービス中の客はいるか？
if sw == -2
sw = -1
@_end = x._end_time # 窓口i1のサービス終了時刻
else
if x._end_time > @_end
@_end = x._end_time # 窓口i1のサービス終了時刻
end
end
end
end
return sw
end
########################
# 客の到着処理
# kk : 入り口番号
########################
def Arrive(kk)
# 客数の増加と次の客の到着時刻の設定
@_nc += 1 # 到着客数カウンタ
@_p_time = @_inl[kk]._arrive_time # 現在時刻
if @_inl[kk]._a_t == 0 # 次の客の到着時刻
@_inl[kk]._arrive_time = @_p_time - @_inl[kk]._mean * Math.log(rand(0))
elsif @_inl[kk]._a_t == 1
@_inl[kk]._arrive_time = @_p_time + @_inl[kk]._mean
else
if (@_inl[kk]._que).length < 1
@_inl[kk]._arrive_time = -1.0
else
@_inl[kk]._arrive_time = @_inl[kk]._que.delete_at(0)
end
end
if @_inl[kk]._arrive_time >= @_end
@_inl[kk]._arrive_time = -1.0
end
# 系内客数の処理
@_c_now_c += @_cus.length * (@_p_time - @_now_c_t) # 系内客数にその数が継続した時間を乗じた値の累計
@_now_c_t = @_p_time # 現在の系内客数になった時刻
if @_cus.length+1 > @_max_c
@_max_c = @_cus.length + 1 # 最大系内客数
end
# 空いている窓口を探す
k1 = @_inl[kk]._out_n
@_que[k1]._nc += 1
k = -1
for i1 in 0 ... @_que[k1]._m
k2 = @_que[k1]._out_n[i1] # 処理窓口
if @_ent[k2]._service == 0
k = k2
break
end
end
# 窓口に空きがない場合
if k < 0
ct_p = Customer.new(0, k1, @_p_time)
@_cus[@_nc] = ct_p # 客の登録（系内客数）
@_que[k1]._c_ql += (@_que[k1]._que).length * (@_p_time - @_que[k1]._ql_t) # 待ち行列長にその長さが継続した時間を乗じた値の累計
@_que[k1]._que.push(@_nc) # 客の登録（待ち行列）
@_que[k1]._ql_t = @_p_time # 現在の待ち行列長になった時刻
if (@_que[k1]._que).length > @_que[k1]._max_q_l
@_que[k1]._max_q_l = (@_que[k1]._que).length # 最大待ち行列長
end
# すぐサービスをうけられる場合
else
ct_p = Customer.new(1, k, @_p_time)
@_cus[@_nc] = ct_p # 客の登録（系内客数）
@_ent[k]._service = @_nc # サービスを受けている客番号
@_ent[k]._busy_t = @_p_time # 窓口がふさがった時刻
if @_ent[k]._s_t == 0 # 窓口のサービス終了時刻
@_ent[k]._end_time = @_p_time - @_ent[k]._mean * Math.log(rand(0))
else
@_ent[k]._end_time = @_p_time + @_ent[k]._mean
end
end
end
###################################
# サービス終了時の処理
# kk : サービス終了窓口番号
###################################
def Service(kk)
# 時間の設定
@_p_time = @_ent[kk]._end_time # 現在時刻
@_ent[kk]._end_time = -1.0 # サービス終了時間
# システムの外へ出る場合
if @_ent[kk]._to == 0
# 系内客数の処理
@_c_now_c += @_cus.length * (@_p_time - @_now_c_t) # 系内客数にその数が継続した時間を乗じた値の累計
@_now_c_t = @_p_time # 現在の系内客数になった時刻
# 滞在時間の処理
it = @_cus[@_ent[kk]._service] # サービス中の客
x1 = @_p_time - it._time
@_c_sys += x1 # 滞在時間の累計
if x1 > @_max_sys
@_max_sys = x1 # 最大滞在時間
end
@_cus.delete(@_ent[kk]._service) # 客の削除（系内客数）
# 他の窓口処理へ入る場合の処理
else
k1 = @_ent[kk]._out_n
@_que[k1]._nc += 1
sw = 1
k2 = 0
if (@_que[k1]._que).length == 0
for i1 in 0 ... @_que[k1]._m
k2 = @_que[k1]._out_n[i1] # 窓口
if @_ent[k2]._service == 0
sw = 0
break
end
end
end
# 待ち行列がある場合
if sw > 0
@_que[k1]._c_ql += (@_que[k1]._que).length * (@_p_time - @_que[k1]._ql_t) # 待ち行列長にその長さが継続した時間を乗じた値の累計
@_que[k1]._que.push(@_ent[kk]._service) # 客の登録（待ち行列）
@_que[k1]._ql_t = @_p_time # 現在の待ち行列長になった時刻
if (@_que[k1]._que).length > @_que[k1]._max_q_l
@_que[k1]._max_q_l = (@_que[k1]._que).length # 最大待ち行列長
end
it = @_cus[@_ent[kk]._service]
it._state1 = 0 # 客の状態変更(待ち行列)
it._state2 = @_ent[kk]._out_n # 客の状態変更(待ち行列番号)
# すぐサービスをうけられる場合
else
@_ent[k2]._service = @_ent[kk]._service # サービスを受けている客番号
@_ent[k2]._busy_t = @_p_time # 窓口がふさがった時刻
if @_ent[k2]._s_t == 0 # 窓口のサービス終了時刻
@_ent[k2]._end_time = @_p_time - @_ent[k2]._mean * Math.log(rand(0))
else
@_ent[k2]._end_time = @_p_time + @_ent[k2]._mean
end
end
end
# 窓口使用時間の処理
@_ent[kk]._service = 0 # 窓口を空き状態にする
@_ent[kk]._c_busy += (@_p_time - @_ent[kk]._busy_t) # 窓口がふさがっている時間の累計
# この窓口に対する待ち行列がある場合
k3 = @_ent[kk]._in_n
if (@_que[k3]._que).length > 0
@_que[k3]._c_ql += (@_que[k3]._que).length * (@_p_time - @_que[k3]._ql_t) # 待ち行列長にその長さが継続した時間を乗じた値の累計
n = @_que[k3]._que.delete_at(0) # 待ち行列の先頭にいる客
@_que[k3]._ql_t = @_p_time # 現在の待ち行列長になった時刻
x1 = @_p_time - @_cus[n]._time
@_que[k3]._c_wt += x1 # 待ち時間の累計
if x1 > @_que[k3]._max_wt
@_que[k3]._max_wt = x1 # 最大待ち時間
end
for i1 in 0 ... @_que[k3]._m
k4 = @_que[k3]._out_n[i1] # 窓口
if @_ent[k4]._service == 0
@_ent[k4]._service = n # 窓口の客番号
@_ent[k4]._busy_t = @_p_time # 窓口がふさがった時刻
if @_ent[k4]._s_t == 0 # 窓口のサービス終了時刻
@_ent[k4]._end_time = @_p_time - @_ent[k4]._mean * Math.log(rand(0))
else
@_ent[k4]._end_time = @_p_time + @_ent[k4]._mean
end
@_cus[n]._state1 = 1 # 客の状態変更(サービス中)
@_cus[n]._state2 = k4 # 客の状態変更(窓口番号)
break
end
end
end
end
##########################
# 統計量の計算と最終出力
##########################
def Output()
# System
printf("全客数 %d", @_nc)
printf(" 最大系内客数 %d 最大滞在時間 %.3f\n", @_max_c, @_max_sys)
printf("平均系内客数 %.3f", (@_c_now_c / @_p_time))
printf(" 平均滞在時間 %.3f", (@_c_sys / @_nc))
printf(" 終了時間 %.3f\n", @_p_time)
# Entity
for i1 in 0 ... @_ent.length
e = @_ent[i1]
printf("Entity " + e._name)
printf(" 稼働率 %.3f\n", (e._c_busy / @_p_time))
end
# Queue
for i1 in 0 ... @_que.length
q = @_que[i1]
printf("Queue " + q._name)
printf(" 客数 %d", q._nc)
printf(" 最大待ち行列長 %d", q._max_q_l)
printf(" 最大待ち時間 %.3f\n", q._max_wt)
printf(" 平均待ち行列長 %.3f", (q._c_ql / @_p_time))
printf(" 平均待ち時間 %.3f\n", (q._c_wt / q._nc))
end
end
end
# 入り口
print("入り口(Inlet)の数は？ ")
n_i = Integer(gets())
inl = Array.new()
for i1 in 0 ... n_i
print(String(i1+1) + " 番目の入り口(Inlet)\n")
print(" 名前は？ ")
name1 = gets().strip()
qq = Array.new()
print(" 到着分布（=0:指数分布，=1:一定時間間隔，<0：指定，客数の負値）？ ")
n = Integer(gets())
if n == 0
print(" 到着時間間隔の平均値は？ ")
m_a = Float(gets())
elsif n == 1
print(" 到着時間間隔は？ ")
m_a = Float(gets())
else
for i2 in range(0, -n)
print(" 到着時間は？ ")
x = Float(gets())
qq.push(x)
end
end
print(" 並ぶ待ち行列の名前は？ ")
name2 = gets().strip()
inl_e = Inlet.new(name1, n, m_a, qq, name2)
inl.push(inl_e)
end
# 待ち行列
print("待ち行列(Queue)の数は？ ")
n_q = Integer(gets())
que = Array.new()
for i1 in 0 ... n_q
print(String(i1+1) + " 番目の待ち行列(Queue)\n")
print(" 名前は？ ")
name1 = gets().strip()
print(" 入り口(0)，または，窓口(n>0，窓口の数)から？ ")
n = Integer(gets())
inn = Array.new()
if n == 0
print(" 入り口の名前は？ ")
name2 = gets().strip()
inn.push(name2)
else
for i2 in 0 ... n
print(" " + String(i2+1) + " 番目の窓口の名前は？ ")
name3 = gets().strip()
inn.push(name3)
end
end
print(" 処理する窓口の数は？ ")
m = Integer(gets())
out = Array.new()
for i2 in 0 ... m
print(" " +String(i2+1) + " 番目の窓口の名前は？ ")
name4 = gets().strip()
out.push(name4)
end
que_e = Queue.new(name1, n, inn, m, out)
que.push(que_e)
end
# 窓口
print("窓口(Entity)の数は？ ")
n_e = Integer(gets())
ent = Array.new()
for i1 in 0 ... n_e
print(String(i1+1) + " 番目の窓口(Entity)\n")
print(" 名前は？ ")
name1 = gets().strip()
print(" サービス分布（=0:指数分布，=1:一定時間）？ ")
s_t = Integer(gets())
if s_t == 0
print(" サービス時間の平均値は？ ")
m_s = Float(gets())
else
print(" サービス時間は？ ")
m_s = Float(gets())
end
print(" 待ち行列(入力)の名前は？ ")
name2 = gets().strip()
print(" 終了後，外部(0)，または，待ち行列(1)？ ")
sw = Integer(gets())
name3 = ""
if sw > 0
print(" 待ち行列(出力)の名前は？ ")
name3 = gets().strip()
end
ent_e = Entity.new(name1, s_t, m_s, name2, sw, name3)
ent.push(ent_e)
end
# 全体の制御を行うクラス
print("シミュレーション終了時間？ ")
stp = Float(gets())
base = Q_base.new(inl, que, ent, stp) # 全体の制御を行うクラス
# 実行
base.Control()
# 出力
base.Output()
=begin
------------入力例(簡単な場合)-----------
1
Inlet
0
5
Queue
1
Queue
0
Inlet
2
Entity1
Entity2
2
Entity1
0
4
Queue
0
Entity2
0
4
Queue
0
10000
------------入力例(複雑な場合)-----------
2
Inlet1
0
5
Queue1
Inlet2
0
5
Queue2
3
Queue1
0
Inlet1
1
Entity1
Queue2
0
Inlet2
1
Entity2
Queue3
2
Entity1
Entity2
2
Entity3
Entity4
4
Entity1
0
4
Queue1
1
Queue3
Entity2
0
4
Queue2
1
Queue3
Entity3
0
3
Queue3
0
Entity4
0
3
Queue3
0
10000
=end