著者

草部 博輝 中森 眞理雄

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)

巻号頁・発行日

vol.48, no.15, pp.34-46, 2007-10-15

---

資源制約付きプロジェクトスケジューリング問題(Resource Constrained Project Scheduling Problem: RCPSP)は,多くの古典的スケジューリング問題の一般化されたモデルである.本稿は,利用可能な再生型資源量の時刻による変化と,各アクティビティが要求する再生型資源量の時間による変化を取り入れた,RCPSP/t モデルに,タイムラグの概念を追加した拡張モデル,RCPSP/t+ モデルを取り扱う.本稿において,我々はRCPSP/t+ モデルの解法として,タブーサーチアルゴリズムを提案し,ILOG CPLEX から得られた最適解と比較することにより,解の精度を評価する.Resource-constrained project-scheduling problem (RCPSP) is a general model of several classical scheduling models. In this paper, we suggest the scheduling model RCPSP/t+, which is added the time windows to the model of RCPSP/t having the changing of limit of renewable resources in project term and of requirement of renewable resources in each activity's processing time. We present a tabu search algorithm for the RCPSP/t+ and evaluate the solution accuracy comparing the oplitmal solution of ILOG CPLEX.

著者

草部 博輝 中森 眞理雄

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告バイオ情報学(BIO) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.128, pp.41-43, 2007-12-20

---

資源制約付プロジェクトスケジューリング問題(Resource Constrained Project Scheduling Problem : RCPSP)は,job-shop のようなモデルの一般形としてよく知られるモデルである.本稿は,RCPSP の先行制約と資源制約を変化させた RCPSP/τ+ モデルを取り扱い,その下界値の計算法を提案する.評価は比較的小規模のインスタンスを用い,最適解との比較を行うことにより行う.Resource-constrained project-scheduling problem (RCPSP) is a general model of several classical scheduling models like a job-shop. In this paper, we suggest the scheduling model RCPSP/${\tau}+$, which is added the time windows to the model of RCPSP/${\tau}$ having the changing of limit of renewable resources in project term and of requirement of renewable resources in each activity's processing time. We present a lower bounding method for the RCPSP/${\tau}+$ and evaluate the lower bound accuracy comparing the oplitmal solution.