`

Case Study 7 : Collaborative Evolutionary Multi-Project Resource Scheduling

Introduction
Many real world scheduling problems, particularly those which arise in the large-scale construction, corporation wide logistics, or large-scale software development, are multi-project resource constrained problems, with a particular emphasis on the word multi. Such problems typically involve many thousands or tens of thousands of tasks, grouped into several hundred or more sub-projects. The individual sub-projects are tightly linked by project-wide resources and other logistic interdependencies. 

Despite the large-scale complexity, a feature of such problems is usually their high level management by a single individual, who maintains a project-wide view and attempts to organise sub-projects relative to each other in time in such a way that multiple criteria are satisfied, many of which cannot be easily formalised.

This project explored a way to deal with multi-project resource-constrained scheduling problems, which is designed to combine standard automated scheduling with scheduler guidance. A collaborative evolutionary multi-project scheduler was developed, which uses an evolutionary algorithm to evolve schedules according partly to standard criteria of due date slippage and makespan, but also includes the scheduler's input as part of a schedule's selective fitness. The scheduler regularly views example GANTT charts from the current population, and assigns coarse relative fitnesses to them (via an easy-to-use interface) by considering the overall ‘shape’ of the developing schedules. Results so far, as well as potential user comments, are very promising for the method.

The resultant software package is available for integration with a wide range of existing Project Management packages.

Implementation
Various existing systems (some GA, some AI, some Artistic) have demonstrated successful interaction between the computer program and the human operator’s subjective selections. They take advantage of modern PC systems with Windows-style interfaces which provide a suitable environment within which the human and PC can interact.

The success of this approach depends on the ability of the system to represent the generated populations in a distinguishable manner (usually graphical) for the human user to determine his selections. 

The following diagram shows the program during a typical session:

The 25 boxes each represent one of the GA solutions derived from the evolutionary process. The colours are used to group the GA calculated fitness prior to the user’s choice, the system uses 5 groups of fitness derived from the overall fitness factor. This display is then used by the Project Manager to choose and specify his preferred fitness values. 

The following diagram shows the final results of a scheduling session. The black dashed line shows the MS Project serial schedule result, whilst the lower Red line shows the Fittest (lowest slip) GA result. 

The main aim of the project was to include an element of Human interaction within the GA Fitness function, so that a Project Manager’s ’gut feel’ and implicit knowledge could be used to direct the solution process without requiring any complex definition language or expert system data gathering operation. Results have shown that the system can be directed by the human operator, so that the solutions ‘bred’ by the GA tend towards a shape or profile preferred by the user. The resultant system can be integrated with a wide range of existing project management packages.

Applications
Although the specific system developed for this project focussed on Programme Management, the techniques can be easily adapted for a wide range of other processes, which involve some graphical aspect, including:

• Industrial and Packaging Design (vehicles, furniture, white goods)

• Scheduling systems (Factory, Job shop, Project Management)

• Pattern design (Wallpaper, Flooring, Carpets)

• Police Investigations (Photofit Faces, determining the make of ‘Get-away’ Cars etc)

• Environmental Design (landscaping, shopping malls, room layouts)

• Advertising (Logos, Slogans, Brochure Layouts)

Conclusion
Taking into account the potential issues, it is entirely feasible to use existing PC technology to deliver Interactive Graphical Interfaces to standard GA processes. In this particular project, a Multi-Project Resource Scheduler benefited highly from interaction with a human user to enable the important but subjective fitness parameters to be specified. 

The ability of an Interactive GA to allow subjective human interaction with the fitness functions will also allow the GA as a methodology to become more of a user-friendly tool, rather than a ‘black-box’ application using arcane processes to deliver results that may be difficult to interpret or believe. Computer systems in general are more acceptable when seen as an extension of the human rather than as a replacement for them.