.: 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.
.: 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.