以下,複数のファイル構成になっていますので,ファイル間の 区切りを「---・・・」で示します. ------------------------makefile------------------ # # リンク # CFLAGS = -c -Wall -O2 OBJECT = machi.o Entity.o Inlet.o List_e.o List_i.o List_q.o Q_base.o Que.o Queue.o pgm: $(OBJECT) g++ $(OBJECT) -o machi -lm # # コンパイル # machi.o: machi.h machi.cpp g++ $(CFLAGS) machi.cpp Entity.o: machi.h Entity.cpp g++ $(CFLAGS) Entity.cpp Inlet.o: machi.h Inlet.cpp g++ $(CFLAGS) Inlet.cpp List_e.o: machi.h List_e.cpp g++ $(CFLAGS) List_e.cpp List_i.o: machi.h List_i.cpp g++ $(CFLAGS) List_i.cpp List_q.o: machi.h List_q.cpp g++ $(CFLAGS) List_q.cpp Q_base.o: machi.h Q_base.cpp g++ $(CFLAGS) Q_base.cpp Que.o: machi.h Que.cpp g++ $(CFLAGS) Que.cpp Queue.o: machi.h Queue.cpp g++ $(CFLAGS) Queue.cpp ------------------------machi.h------------------- class Q_base; class Queue; class Entity; /***********************/ /* クラスQueの定義 */ /***********************/ class Que { double time; // 到着時刻,または,待ち開始時刻 int num; // 客番号 Que *next; public : Que (int, double); // コンストラクタ Que (); // コンストラクタ void Add(Que *); // 客の追加 void Del(int); // 客の削除 int Search(); // 待ち行列の先頭にいる客を捜す double Search(int); // 指定した客の到着時刻,または,待ち開始時刻 }; /*************************/ /* クラスInletの定義 */ /*************************/ class Inlet { char name[21]; // Inlet名 Queue *out; // 到着後入る待ち行列 double arrive_time; // 客の到着時間(負:客がない) double mean; // 平均値 public: Inlet (char *, Q_base &, double); // コンストラクタ Inlet (char *, Q_base &, Queue &, double); // コンストラクタ friend class Q_base; }; /*************************/ /* クラスQueueの定義 */ /*************************/ class Queue { char name[21]; // Queue名 int now; // 現在の待ち行列長 Entity *e_in; // 待ちへの入力Entity Inlet *i_in; // 待ちへの入力Inlet int max_q_l; // 最大待ち行列長 double c_ql; // 待ち行列長にその長さが継続した時間を乗じた値の累計 double ql_t; // 現在の待ち行列長になった時間 double max_wt; // 最大待ち時間 int nc; // 到着客数カウンタ double c_wt; // 待ち時間の累計 Que q_l; // 待ち行列 public: Queue(char *, Q_base &, Entity &); // コンストラクタ Queue(char *, Q_base &, Inlet &); // コンストラクタ Queue(char *, Q_base &); // コンストラクタ void Put(double, int); // 待ち行列へ追加 int Get(double); friend class Q_base; }; /**************************/ /* クラスEntityの定義 */ /**************************/ class Entity { char name[21]; // Entity名 double end_time; // サービス終了時間(負:何も処理していない) Queue *in; // サービス対象とする待ち行列 Queue *out; // サービス終了後に入る待ち行列 int bunpu; // サービス時間の分布(0:指数分布,1:正規分布) double mean; // 平均値 double std; // 標準偏差 int service; // サービス中の客番号(0のときはなし) double busy_t; // 窓口がふさがった時間 double c_busy; // 窓口がふさがっている時間の累計 public: Entity (char *, Q_base &, Queue &, double); // コンストラクタ Entity (char *, Q_base &, Queue &, Queue &, double); // コンストラクタ friend class Q_base; }; /**************************/ /* クラスList_eの定義 */ /**************************/ class List_e { List_e *next; Entity *e; // Entityオブジェクト public: List_e(); // コンストラクタ void Add(Entity *); // Entityの追加 friend class Q_base; }; /**************************/ /* クラスList_iの定義 */ /**************************/ class List_i { List_i *next; Inlet *i; // Inletオブジェクト public: List_i(); // コンストラクタ void Add(Inlet *); // Inletの追加 friend class Q_base; }; /**************************/ /* クラスList_qの定義 */ /**************************/ class List_q { List_q *next; Queue *q; // Queueオブジェクトのリスト public: List_q(); // コンストラクタ void Add(Queue *); // Queueの追加 friend class Q_base; }; /**************************/ /* クラスQ_baseの定義 */ /**************************/ class Q_base { char name[21]; // システム名 double time; // 現在時刻 int max_c; // 最大系内客数 int now_c; // 現在の系内客数 int nc; // 到着客数カウンタ double now_c_t; // 現在の系内客数になった時間 double c_now_c; // 系内客数にその数が継続した時間を乗じた値の累計 double c_sys; // 滞在時間の累計 double max_sys; // 最大滞在時間 double end; // シミュレーション終了時間 Que arv_l; // 到着した客のリスト public: List_e le; // Entityのリスト List_i li; // Inletのリスト List_q lq; // Queueのリスト Q_base (char *, double, int); // コンストラクタ double Exp_b(double); // 指数分布乱数の発生 void Control(); // 全体の制御 void Arrive(Queue *, Inlet *); // 客の到着 void Next_q(Queue *, Entity *); // 次のQueue void S_start(Entity *); // サービスの開始 void Bye(Entity *); // システムから出る void Result(); // 結果の出力 }; ------------------------Entity.cpp---------------- /*********************************/ /* クラスQueueのメンバー関数 */ /*********************************/ #include #include "machi.h" /***********************************************************************/ /* コンストラクタ */ /* na : Queueオブジェクトの名前 */ /* base:Q_baseオブジェクト */ /* qi : 入力Queue(このEntityで処理する待ち行列オブジェクト) */ /***********************************************************************/ Entity::Entity(char *na, Q_base &base, Queue &qi, double m) { strcpy(name, na); end_time = -1.0; in = &qi; out = NULL; mean = m; service = 0; busy_t = -1.0; c_busy = 0.0; base.le.Add(this); } /***********************************************************************/ /* 複数のEntityから同じ待ち行列に入れる場合のコンストラクタ */ /* (Queueのコンストラクタに可変個の引数を持たせればこのよ */ /* うなコンストラクタは不要である) */ /* na : Queueオブジェクトの名前 */ /* base:Q_baseオブジェクト */ /* qi : 入力Queue(このEntityで処理する待ち行列オブジェクト) */ /* qo : 処理後入るQueueオブジェクト */ /***********************************************************************/ Entity::Entity(char *na, Q_base &base, Queue &qi, Queue &qo, double m) { strcpy(name, na); end_time = -1.0; in = &qi; out = &qo; mean = m; service = 0; busy_t = -1.0; c_busy = 0.0; base.le.Add(this); } ------------------------Inlet.cpp----------------- /*********************************/ /* クラスInletのメンバー関数 */ /*********************************/ #include #include "machi.h" /*****************************************/ /* コンストラクタ */ /* na : Inletオブジェクトの名前 */ /* base:Q_baseオブジェクト */ /* m : 指数分布の平均値 */ /*****************************************/ Inlet::Inlet (char *na, Q_base &base, double m) { strcpy(name, na); out = NULL; mean = m; arrive_time = base.Exp_b(mean); base.li.Add(this); } /***************************************************************/ /* 複数のInletから同じ待ち行列に入れる場合のコンストラクタ */ /* (Queueのコンストラクタに可変個の引数を持たせればこのよ */ /* うなコンストラクタは不要である) */ /* na : Inletオブジェクトの名前 */ /* base:Q_baseオブジェクト */ /* m : 指数分布の平均値 */ /* q : 処理後入るQueueオブジェクト */ /***************************************************************/ Inlet::Inlet (char *na, Q_base &base, Queue &q, double m) { strcpy(name, na); out = &q; mean = m; arrive_time = base.Exp_b(mean); base.li.Add(this); } ------------------------Queue.cpp----------------- /*********************************/ /* クラスQueueのメンバー関数 */ /*********************************/ #include #include #include "machi.h" /************************************************************/ /* コンストラクタ */ /* na : Queueオブジェクトの名前 */ /* base:Q_baseオブジェクト */ /* e : 入力Entity(処理後,このQueueに入るEntity) */ /************************************************************/ Queue::Queue(char *na, Q_base &base, Entity &e) { strcpy(name, na); now = 0; e_in = &e; i_in = NULL; max_q_l = 0; c_ql = 0.0; ql_t = 0.0; max_wt = 0.0; nc = 0; c_wt = 0.0; base.lq.Add(this); } /**********************************************************/ /* コンストラクタ */ /* na : Queueオブジェクトの名前 */ /* base:Q_baseオブジェクト */ /* e : 入力Inlet(処理後,このQueueに入るInlet) */ /**********************************************************/ Queue::Queue(char *na, Q_base &base, Inlet &i) { strcpy(name, na); now = 0; e_in = NULL; i_in = &i; max_q_l = 0; c_ql = 0.0; ql_t = 0.0; max_wt = 0.0; nc = 0; c_wt = 0.0; base.lq.Add(this); } /************************************************************/ /* コンストラクタ */ /* (複数のInletまたはEntityからこのQueueに入る時使用) */ /* na * Queueオブジェクトの名前 */ /* base:Q_baseオブジェクト */ /************************************************************/ Queue::Queue(char *na, Q_base &base) { strcpy(name, na); now = 0; e_in = NULL; i_in = NULL; max_q_l = 0; c_ql = 0.0; ql_t = 0.0; max_wt = 0.0; nc = 0; c_wt = 0.0; base.lq.Add(this); } /*************************/ /* 待ち行列に追加 */ /* time : 時刻 */ /* num : 客番号 */ /*************************/ void Queue::Put(double time, int num) { nc++; // 到着客数 now++; // 待ち行列長 if (now > max_q_l) // 最大待ち行列長 max_q_l = now; c_ql += (double)(now - 1) * (time - ql_t); // Σ(待ち行列長*継続時間) ql_t = time; // 待ち行列変化時間 Que *dt = new Que (num, time); // 客の待ち行列への追加 q_l.Add(dt); } /****************************/ /* 待ち行列から取り除く */ /* time : 時刻 */ /* return : 客番号 */ /****************************/ int Queue::Get(double time) { double t,x; int num; num = q_l.Search(); // 待ち行列の先頭 t = q_l.Search(num); // 待ちの開始時刻 q_l.Del(num); // 待ちから削除 c_ql += (double)now * (time - ql_t); // Σ(待ち行列長*継続時間) ql_t = time; // 待ち行列変化時間 x = time - t; // 待ち時間 if (x > max_wt) // 最大待ち時間 max_wt = x; c_wt += x; // 待ち時間の累計 now--; return num; } ------------------------List_e.cpp---------------- /**********************************/ /* クラスList_eのメンバー関数 */ /**********************************/ #include #include "machi.h" /**********************/ /* コンストラクタ */ /**********************/ List_e::List_e() { next = NULL; } /********************************************/ /* Entityをリストの最後に追加 */ /* dt : Entityクラスのオブジェクト */ /********************************************/ void List_e::Add(Entity *dt) { List_e *lt = this; while (lt->next != NULL) lt = lt->next; List_e *lt_n = new List_e; lt_n->e = dt; lt->next = lt_n; } ------------------------List_i.cpp---------------- /**********************************/ /* クラスList_iのメンバー関数 */ /**********************************/ #include #include "machi.h" /**********************/ /* コンストラクタ */ /**********************/ List_i::List_i() { next = NULL; } /*******************************************/ /* Inletをリストの最後に追加 */ /* dt : Inletクラスのオブジェクト */ /*******************************************/ void List_i::Add(Inlet *dt) { List_i *lt = this; while (lt->next != NULL) lt = lt->next; List_i *lt_n = new List_i; lt_n->i = dt; lt->next = lt_n; } ------------------------List_q.cpp---------------- /**********************************/ /* クラスList_qのメンバー関数 */ /**********************************/ #include #include "machi.h" /**********************/ /* コンストラクタ */ /**********************/ List_q::List_q() { next = NULL; } /*******************************************/ /* Queueをリストの最後に追加 */ /* dt : Queueクラスのオブジェクト */ /*******************************************/ void List_q::Add(Queue *dt) { List_q *lt = this; while (lt->next != NULL) lt = lt->next; List_q *lt_n = new List_q; lt_n->q = dt; lt->next = lt_n; } ------------------------Que.cpp------------------- /*******************************/ /* クラスQueのメンバー関数 */ /*******************************/ #include #include #include "machi.h" /***********************/ /* コンストラクタ */ /* n : 客番号 */ /***********************/ Que::Que (int n, double t) { time = t; num = n; next = NULL; } /********************************/ /* 引数無しのコンストラクタ */ /********************************/ Que::Que () { next = NULL; } /*****************************************/ /* 客をリストの最後に追加 */ /* dt : Queクラスのオブジェクト */ /*****************************************/ void Que::Add(Que *dt) { Que *lt = this; while (lt->next != NULL) lt = lt->next; lt->next = dt; } /***********************/ /* 客の削除 */ /* n : 客番号 */ /***********************/ void Que::Del(int n) { Que *lt1, *lt2 = this; int sw = 1; while (sw > 0) { // データが存在しない場合 if (lt2->next == NULL) { printf(" 指定されたデータがありません(Del)!\n"); exit(1); } // 比較し,削除 else { lt1 = lt2; lt2 = lt2 -> next; if (n == lt2->num) { lt1->next = lt2->next; sw = 0; } } } } /**************************************/ /* 待ち行列の先頭の客を捜す */ /* return : 先頭の客番号 */ /* (負の時は無し) */ /**************************************/ int Que::Search() { Que *lt = this; int n = -1; if (lt->next != NULL) { lt = lt->next; n = lt->num; } return n; } /******************************/ /* 指定した客の到着時間 */ /* nm : 客番号 */ /* return : 到着時間 */ /******************************/ double Que::Search(int nm) { Que *lt = this; double t = 0.0; int sw = -1; while (sw < 0) { // データが存在しない場合 if (lt->next == NULL) { printf(" 指定されたデータがありません(Search)!\n"); exit(1); } // 探索 else { lt = lt->next; if (lt->num == nm) { sw = 0; t = lt->time; } } } return t; } ------------------------Q_base.cpp---------------- /**********************************/ /* クラスQ_baseのメンバー関数 */ /**********************************/ #include #include #include #include #include "machi.h" double drand48(); /*****************************************/ /* コンストラクタ */ /* na : Baseオブジェクトの名前 */ /* e : シミュレーション終了時間 */ /* seed : 乱数の初期値 */ /*****************************************/ Q_base::Q_base (char *na, double e, int seed) { strcpy(name, na); time = 0.0; max_c = 0; now_c = 0; nc = 0; now_c_t = 0.0; c_now_c = 0.0; c_sys = 0.0; max_sys = 0.0; end = e; srand(seed); } /**********************/ /* 指数分布乱数の発生 */ /* m : 平均値 */ /**********************/ double Q_base::Exp_b(double m) { return -m * log(drand48()); } /******************/ /* 全体の制御 */ /******************/ void Q_base::Control() { double tm = 0.0; int type = 0, len = 0; Entity *e1 = NULL, *e_next = NULL, *e_p; Inlet *i1 = NULL, *i_p; Queue *q_next = NULL, *q_p; List_e *le_p; List_i *li_p; List_q *lq_p; /* 次に処理すべき処理と時間を決める */ while (type >= 0) { type = -1; // Inletオブジェクト(到着し,サービスを待つ) // (複数のInletが同じQueueに入る場合) li_p = li.next; while (li_p != 0) { i_p = li_p->i; if (i_p->out != 0 && i_p->arrive_time >= 0.0) { q_p = i_p->out; if (type < 0 || type >= 0 && i_p->arrive_time < tm) { type = 1; tm = i_p->arrive_time; q_next = q_p; i1 = i_p; } } li_p = li_p->next; } // Queueオブジェクト lq_p = lq.next; while (lq_p != 0) { q_p = lq_p->q; // 窓口のサービスを終了し,このQueueに入る if(q_p->e_in != NULL) { e_p = q_p->e_in; if (e_p->service > 0) { // サービスを行っているか? // サービスを終了しQueueに入る if (type < 0 || type >= 0 && e_p->end_time < tm) { type = 0; tm = e_p->end_time; e1 = e_p; len = q_p->now; q_next = q_p; } // 複数のQueueがある場合は,最も短いQueueに入る else { if (type == 0 && e_p == e1 && q_p->now < len) { len = q_p->now; q_next = q_p; } } } } // 到着し,サービスを待つ else { if (q_p->i_in != NULL) { i_p = q_p->i_in; if (i_p->arrive_time >= 0.0) { // 到着したか? // 到着しQueueに入る if (type < 0 || type >= 0 && i_p->arrive_time < tm) { type = 1; tm = i_p->arrive_time; i1 = i_p; len = q_p->now; q_next = q_p; } // 複数のQueueがある場合は,最も短いQueueに入る else { if (type == 1 && i_p == i1 && q_p->now < len) { len = q_p->now; q_next = q_p; } } } } } lq_p = lq_p->next; } // Entityオブジェクト le_p = le.next; while (le_p != 0) { e_p = le_p->e; // 窓口は空いているか? // サービスの開始 if (e_p->service == 0) { q_p = e_p->in; if (q_p->now > 0 && type != 2) { // 待っている客はあるか? type = 2; tm = time; e_next = e_p; } } // サービスの終了 else { if (type < 0 || type >= 0 && e_p->end_time < tm) { tm = e_p->end_time; q_p = e_p->out; // システムから出る if (q_p == NULL) { type = 3; e_next = e_p; } // サービスを終了し,次のサービスを待つ else { type = 0; e1 = e_p; q_next = q_p; } } } le_p = le_p->next; } // 各処理 switch (type) { case 0: // サービスを終了し,次の処理のためのQueueに入る Next_q(q_next, e1); break; case 1: // 客の到着 Arrive(q_next, i1); break; case 2: // 窓口のサービス開始 S_start(e_next); break; case 3: // システムから出る Bye(e_next); break; default: // 結果の出力 Result(); break; } } } /************************************/ /* 到着した客を待ち行列へ入れる */ /* q : 対象とするQueue */ /* i : 到着したInlet */ /************************************/ void Q_base::Arrive(Queue *q, Inlet *i) { time = i->arrive_time; // 現在時間の修正 i->arrive_time = time + Exp_b(i->mean); // 次の客の到着時刻 if (i->arrive_time > end) i->arrive_time = -1.0; nc++; // 到着客数カウンタ now_c++; // 系内客数 if (now_c > max_c) // 最大系内客数 max_c = now_c; c_now_c += (double)(now_c - 1) * (time - now_c_t); // Σ(系内客数*継続時間) now_c_t = time; // 系内客数変化時間の記憶 Que *dt = new Que (nc, time); // 客をリストへ追加 arv_l.Add(dt); q->Put(time, nc); // 待ち行列へ追加 } /********************************************************/ /* サービスを終了し,次のサービスの待ち行列へ入れる */ /* q : 対象とするQueue */ /* e : 処理を終了したEntity */ /********************************************************/ void Q_base::Next_q(Queue *q, Entity *e) { time = e->end_time; // 現在時間の修正 e->c_busy += (time - e->busy_t); // Σ(窓口がふさがっている時間) q->Put(time, e->service); // 待ち行列へ追加 e->busy_t = -1.0; // 処理対象無し e->end_time = -1.0; // 処理対象無し e->service = 0; // 窓口を空き状態にする } /************************************/ /* Entityにおけるサービスの開始 */ /* e : 対象とするEntity */ /************************************/ void Q_base::S_start(Entity *e) { Queue *q = e->in; // 客が待っている待ち行列 int num = q->Get(time); // サービスに入る客を待ちから除く e->end_time = time + Exp_b(e->mean); // サービス終了時間 e->busy_t = time; // 処理開始時刻の記憶 e->service = num; // サービス中の客 } /*********************************/ /* システムから出る */ /* e : 対象とするEntity */ /*********************************/ void Q_base::Bye(Entity *e) { double t, x; time = e->end_time; // 現在時間の修正 c_now_c += (double)now_c * (time - now_c_t); // Σ(系内客数*継続時間) now_c_t = time; // 系内客数変化時間の記憶 t = arv_l.Search(e->service); // システム内滞在時間 x = time - t; c_sys += x; // Σ(滞在時間) if (x > max_sys) // 最大滞在時間 max_sys = x; now_c--; // 系内客数 e->c_busy += (time - e->busy_t); // Σ(窓口がふさがっている時間) e->busy_t = -1.0; // 処理対象無し e->end_time = -1.0; // 処理対象無し e->service = 0; // 窓口を空き状態にする } /******************************/ /* 統計量の計算と最終出力 */ /******************************/ void Q_base::Result() { // System std::cout << "System " << name << " 客数 " << nc; std::cout << " 最大系内客数 " << max_c << " 最大滞在時間 " << max_sys << std::endl; std::cout << " 平均系内客数 " << c_now_c / time; std::cout << " 平均滞在時間 " << c_sys / nc; std::cout << " 終了時間 " << time << std::endl; // Entity List_e *le_p = le.next; Entity *e; while (le_p != NULL) { e = le_p->e; std::cout << "Entity " << e->name << " 稼働率 " << e->c_busy / time << std::endl; le_p = le_p->next; } // Queue List_q *lq_p = lq.next; Queue *q; while (lq_p != NULL) { q = lq_p->q; std::cout << "Queue " << q->name << " 客数 " << q->nc; std::cout << " 最大待ち行列長 " << q->max_q_l; std::cout << " 最大待ち時間 " << q->max_wt << std::endl; std::cout << " 平均待ち行列長 " << q->c_ql / time; std::cout << " 平均待ち時間 " << q->c_wt / q->nc << std::endl; lq_p = lq_p->next; } } ------------------------main---------------------- /**********************************/ /* 複雑な待ち行列問題 */ /* coded by Y.Suganuma */ /**********************************/ #include #include "machi.h" /**********************************/ /* [0, 1]区間の一様乱数の発生 */ /* rerutn : 乱数 */ /**********************************/ double drand48(void) { double x; while ((x = (double)rand() / RAND_MAX) == 0.0) ; return x; } /********************/ /* main program */ /********************/ int main() { Q_base base("base", 5000.0, 123); // 全体の制御を行うクラス /* 簡単な待ち行列問題 -> Entity1 Inlet -> Queue1 -> -> Entity2 Inlet i1("Inlet1", base, 5.0); // 客の到着 Queue q1("Queue1", base, i1); // 待ち行列 Entity e1("Entity1", base, q1, 4.0); // 窓口 Entity e2("Entity2", base, q1, 4.0); // 窓口 */ /* 複雑な待ち行列問題 Inlet1 -> Queue1 -> Entity1 -> Entity3 -> Queue3 -> Inlet2 -> Queue2 -> Entity2 -> Entity4 */ Queue q3("Queue3", base); // 待ち行列,複数のEntityから入るため入力Entityを記述できない // Entity1とEntity2で参照するため前もって定義する必要がある Inlet i1("Inlet1", base, 5.0); // 客の到着 Queue q1("Queue1", base, i1); // 待ち行列 Entity e1("Entity1", base, q1, q3, 4.0); // 窓口,Entity2と同じQueue3に入れるため Inlet i2("Inlet2", base, 5.0); // 客の到着 Queue q2("Queue2", base, i2); // 待ち行列 Entity e2("Entity2", base, q2, q3, 4.0); // 窓口,Entity1と同じQueue3に入れるため Entity e3("Entity3", base, q3, 3.0); // 窓口 Entity e4("Entity4", base, q3, 3.0); // 窓口 base.Control(); return 0; }