M. Jerkovic
Resource-constrained project scheduling. Notation, classification and some
of the recent developments.
Literature survey,
Report 99.3.LT.5154, Transport Technology, Logistic Engineering.
Scheduling is the allocation of resources over time to perfonn a
collection of tasks. It is a decision-making process that has as a goal
the optimization of one or more objectives subject to precedence
constraints and resource constraints. Also, it is a collection of
principles, models, techniques, and logical conclusions that provide
insight into the scheduling function.
The vital elements in scheduling models are resources and tasks. The
resources and tasks may take many forms. The tasks may be called
"jobs" or "projects" or "assignments" and
are composed of elementary parts called "activities" or
"operations" and "delays". Each activity requires
certain amounts of specified resources for a specified time called the
"process time". The resources are in limited supply and also
have elementary parts, called "machines", "cells",
"transport", and so on. The objectjes may also take many forms.
One possible objective is the minimization of the completion time of the
last task, and another is the minimization of the number of tasks
completed after the committed due dates. In general, scheduling is the
process of organizing, choosing, and timing resource usage to carry out
all the activities necessary to produce the desired outputs at the desired
times, while satisfying a large number of time and relationship
constraints among the activities and the resources.
Scheduling decisions are generally subject to both precedence constraints
and resource constraints. The resource-constrained project scheduling
(RCPS) model contains both types of constraints that characterize
scheduling decisions. The relation of this topic to other scheduling
problems can therefore be interpreted in two ways. First, the
resource-constrained project scheduling problem can be formulated by
adding explicit resource requirements and resource capacities to the basic
network model of CPM (Critical Path Method) and PERT (Program Evaluation
and Review Technique). CPM and PERT have been regarded as tools for
planning and scheduling large, nonrepetitive projects. Alternatively, the
problem can also be formulated by allowing general precedence structures
in the job shop problem and replacing machines by machine groups, for
parallelism. Thus, the resource-constrained project scheduling problem
contains the job shop scheduling problem as a special case. So far, no
classification scheme exists which is compatible with what is commonly
accepted in machine scheduling. Also, a variety of symbols are used by
project scheduling researchers in order to denote one and the same subject.
One purpose of this report is to provide a classification scheme, i.e. a
description of the resource envirornnent (the machine environment in the
job shop model), the activity characteristics (task characteristics in the
job shop model), and the objective function (optimality criterion or
performance measure in the job shop model), which is compatible with
machine scheduling and which allows to classify the most important models
dealt with so far. The second purpose of this report is to review some of
the recent developments.
Reports on Logistic Engineering (in Dutch)
Modified: 2000.02.27;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.