MPSP Information | Download Problems | Upload Your Solution | Ranking & Analysis | Experiments | Contact Us |

Welcome to mpsplib.com

.: Welcome to MPSPLib - Scope

In the context of collaborative project management often many distributed
projects have to be planned at the same time. The planning of a project is
done decentrally by autonomous and self-interested decision makers (project
manager or decision system), taking account asymmetric information. On the
following websites the Decentral Resource Constrained Multi-Project Scheduling
Problem (DRCMPSP) is considered. The problem, was introduced by Confessore et
al. (2002, 2007) and extended by Homberger (2007), is a generalization of the
familiar Resource Constrained Project Scheduling Problem (RCPSP) (Blazewicz et al., 1983; Kolisch, 1996) and can be stated as follows.

A set of n projects has to be planned simultaneously by a set of autonomous and self-interested decision makers (project manager or agents). For each project i, i = 1, ..., n, a set of jobs or activities, precedence relations between the jobs, an arrival date ADi (Pritsker et al., 1969; Bouleimen and Lecocq, 2003; Goncalves et al., 2004), and a set of local renewable resources are given. Moreover, a finite set G of global renewable resources is introduced, which is shared by all projects.

Each decision maker has the local objective to minimize the makespan MSi of his project. However, the single objectives of the agents are usually at odds with each other. This is the case if jobs of different projects require the same capacities of a shared resource at the same time. In this case the makespans of the projects cannot be minimized simultaneously. Therefore efficient solutions are sought. To compare alternative efficient solutions of the DRCMPSP, usually additional performance criteria, namely the Average Project Delay (APD) (Lova and Tormos, 2001; Confessore et al., 2007), and the Total Makespan (TMS) (Pritsker et al. 1969) are used.

Information asymmetry is assumed: the problem data of project i (e.g., project activities and the local resources), and information with regard to calculated schedules for project i (e.g., the makespan MSi) are private, i.e., only known by the agent, which plans project i.

A set of n projects has to be planned simultaneously by a set of autonomous and self-interested decision makers (project manager or agents). For each project i, i = 1, ..., n, a set of jobs or activities, precedence relations between the jobs, an arrival date ADi (Pritsker et al., 1969; Bouleimen and Lecocq, 2003; Goncalves et al., 2004), and a set of local renewable resources are given. Moreover, a finite set G of global renewable resources is introduced, which is shared by all projects.

Each decision maker has the local objective to minimize the makespan MSi of his project. However, the single objectives of the agents are usually at odds with each other. This is the case if jobs of different projects require the same capacities of a shared resource at the same time. In this case the makespans of the projects cannot be minimized simultaneously. Therefore efficient solutions are sought. To compare alternative efficient solutions of the DRCMPSP, usually additional performance criteria, namely the Average Project Delay (APD) (Lova and Tormos, 2001; Confessore et al., 2007), and the Total Makespan (TMS) (Pritsker et al. 1969) are used.

Information asymmetry is assumed: the problem data of project i (e.g., project activities and the local resources), and information with regard to calculated schedules for project i (e.g., the makespan MSi) are private, i.e., only known by the agent, which plans project i.

.: MPSPLib - a collection of multi-project instances

140 instances of the DRCMPSP can be downloaded (Homberger, 2007). They are
separated in different problem sets comprising multiple multi-project instances
with n = 2, 5, 10, or 20 single-project instances each. Each multi-project
instance is made up of RCPSP instances from
** Kolisch (2008) **
of the same size. The multi-project instances differ in the composition of the
chosen RCPSP instances as well as in the number of global resource types
(|G| = 1, 2, 3, 4) and the arrival dates of the single projects. Results for
the instances can be uploaded. They are checked for feasibility.

.: References

- Blazewicz, J., Lenstra, J.K., Rinnooy Kan, A.H.G., 1983. Scheduling subject to resource constraints: classification and complexity. Discrete Applied Mathematics 5, 11-24.
- Bouleimen, K., Lecocq, H., 2003. A new efficient simulated annealing algorithm for the resource constrained project scheduling problem and its multiple mode version. European Journal of Operational Research 149, 268-281.
- Confessore, G., Giordani, S., Rismondo, S., 2002. An auction based approach in decentralized project scheduling. In: Proc. of PMS 2002 – International Workshop on Project Management and Scheduling. Valencia, pp. 110-113.
- Confessore, G., Giordani, S., Rismondo, S., 2007. A market-based multi-agent system model for decentralized multi-project scheduling. Annals of Operations Research 150, 115-135.
- Fink, A., 2004. Supply chain coordination by means of automated negotiations. In: Proc. of the 37th Hawaii International Conference on System Sciences. CD-ROM (10 pages)
- Goncalves, J.F., Mendes, J.J.M., Resende, M.G.C., 2004. A genetic algorithm for the resource constrained multi-project scheduling problem. AT&T Labs Technical Report TD-668LM4, Portugal.
- Homberger, J, 2007. A multi-agent system for the decentralized resource-constrained multi-project scheduling problem. International Transactions in Operational Research 14(6), 565-589.
- Klein, M., Faratin, P., Sayama, H., Bar-Yam, Y., 2003. Negotiating complex contracts. Group Decision and Negotiation 12, 111-125.
- Kolisch, R., 1996. Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. European Journal of Operational Research 90, 320-333.
- Kolisch, R., 2008. Library for project scheduling problems. http://129.187.106.231/psplib/ accessed January 15, 2008.
- Lova, A., Tormos, P., 2001. Analysis of scheduling schemes and heuristic rules performance in resource-constrained multiproject scheduling. Annals of Operations Research 102, 263-286.
- Pritsker, A.A.B., Watters, L.J., Wolfe, P.M., 1969. Multiproject scheduling with limited resources: a zero-one programming approach. Management Science 16, 93-108.

© 2008 Joerg Homberger, HfT Stuttgart