Resource Scheduling DSS

In a near future Service Providers will be facing a multi-service and multi-network market, requiring more and more efficiency. In particular, work crews installing telecommunication network and service configurations must be efficiently scheduled. The objective is to fully satisfy the customer by providing the required service at the expected time at competive cost. Consequently, the needs are

to propose a date for Service Activation which is achievable, requiring a long term view on resource usage in order to prevent bottlenecks and late delivery of services,
to optimise the day schedule by well organising the activities and the travelling of work crews,
to be able to react to any disturbances such as delay in work, temporary unavailability of work crews and cancellation of an installation.

Such needs can become quickly intractable manually and as such a decision support system is an essential support to a planner. It should give him characteristics of the situation and views on the problem, in order to support him in decision making and perform the required complex computation. RS DSS tackles this need and is described below.

Functions

RS DSS takes as inputs Service & Network configurations to be installed. It produces projects, which are logical dependencies graph of basic operations, known as PERT graphs. Each operation has a certain duration and requires a certain amount of a certain type of resource. Such a project is evaluated in order to characterise its shape and forecast and prevent very tensed situation. The project is then scheduled at two levels of granularity in time. The results are (i) the long term schedule, forecasting bottlenecks (and the need to hire external manpower) and proposing a date for a Service Activation and (ii) the detailed schedule of the day, an operational document distributed to work crews in order to optimise the way the work is organised.

Architecture and underlying techniques

The Resource DSS is based on a layered blackboard architecture, providing flexibility and reactivity.

The User Interface tool gathers all interactions with the user and provides the possibility of simulating real world events, such as delays on operations.

The Event Monitor processes external real-world events, such as resource unavailability as well as internally generated events, such as re-scheduling request. The Event Monitor provides the system with a high level of reactivity.

The Project Generator translates a service and network configuration into an installation project.

The Evaluator provides the user with metrics on the generated project. These metrics give some indications on complexity and density of the project, including a view of how well resources are being used from a project point of view.

The Long Term Scheduler (LTS) produces a rough planning, allocating operations in large time windows, using various different strategies, such as As Soon As Possible, Just In Time with more or less Balanced Use of resource and postponements of other projects. It reserves amount of resources in fixed period of time and produces the acknowledgement for contract due date. The following figure shows a GANTT chart of several installation projects processed by the LTS.

The Short Term Scheduler (STS) records and manages the temporal constraints issued by the LTS and the Sequencer. The STS relies on YACHT. YACHT manages a temporal database, consisting of events and constraints between those events.

The Sequencer performs accurate operation scheduling and resource allocation, thus determining the actual schedule for each team. The Sequencer uses Operations Research (OR) and Knowledge Based Systems (KBS) techniques. New OR tools are used, based on modern heuristic optimisation techniques. OR tools minimise idle time as well as travelling time. They generate tours of operation and assigns them to work crews. Modular access to OR algorithms allows incremental optimised resource allocation. KBS manages disturbances and minimises their impact, by focusing on a set of operations, rather than all of them, thus avoiding computational overhead. The following figure shows the geographical interface showing OR computed tours in London City.

Finally, RS DSS saves computed schedules in AIM(^*) an object oriented database management system and allows the user to fetch any past schedule.

Important features

The Resource Scheduling DSS offers the following interesting features :

flexibility with its architecture relying on a blackboard mechanism,
reactivity to real-world external and internally generated events,
realism, as it is capable of processing disturbances, such as delays on operations,
high level user support with several scheduling strategies, with metrics characterising the scheduling process, ...
optimisation of work crews work, by minimising idle time and travelling time.

(note * AIM is a federated, object-oriented database management system designed and implemented by University Van Amsterdam in P2256 ESPRIT ARCHON project.)