Selected Applications of Constraint Technology

 

 

Some of the applications which Mike Pegman designed and / or developed have publicly available reference material.

Extracts are provided here for your information.

More information is available on request - Email to: mp@vinesolutions.co.uk Please give your postal address details & contact number.


Utility Service Scheduling / Engineer Dispatching

This application is now a commercial product of Severn Trent Systems Ltd http://www.sts.co.uk/. Part of the STORMS Work Management system, CREW Scheduler manages the allocation of work to multi-skilled crews. It offers a variety of types of scheduling, including planning work loads several days out and repairing a daily schedule to adapt the work plan to changing circumstances.

Mike Pegman is a consultant to STS Ltd.

Top Home


Mine Planning and Scheduling at RTZ Technical Services

by Mike Pegman, Vine Solutions Ltd, Nigel Forward, Brett King, Dave Teal, RTZ Technical Services Ltd

This paper describes work undertaken by Vine Solutions Ltd with RTZ Technical Services in 1996. Two projects are described in outline and brief technical descriptions of the projects are given.

Both projects are in the application area of open-pit mine planning and scheduling. One deals with short term operations scheduling for a period of weeks, the other longer term planning. Common factors are the selection of material for mining from a range of alternatives and the subsequent sequencing of the chosen material. In addition, this sequencing must be converted into a viable operational schedule of timed activities. Various constraints are modelled, including physical limitations of mining, machinery and processing constraints, operating costs and related financial information is included to support the calculation of cash flows.

The paper concentrates on three areas: the material selection problem, discussing two implemented models; the waste removal problem, presenting non-monotonic planning search code; and the joint resource allocation and scheduling problem associated with operations mine scheduling.

ILOG Solver is used heavily in the block selection process, for the representation of mining constraints and for specialised planners. ILOG Schedule is used for the resource allocation and scheduling sub-problems. Both projects are in prototype form and are undergoing trials on behalf of their respective user groups.

The paper presents sufficient detail to act as a study of model design and also of the search space engineering issues which arise in practical Solver / Schedule projects.

Winner of 'Best Technical Paper' at Ilog's International User Group Conference 1996.

Top Home

 


Aircraft Tail Allocation

The paper gives a summary of an application to plan which aircraft will fly a particular set of scheduled flights. Maintenance planning is performed in periods during which the aircraft is back at its base location.

Tail Allocation,
Gomberg G (Logica UK),
Proc Fourth Int’l ILOG Solver and Schedule Users’ Conference, Oct 1998

Abstract

A fleet of a few dozen aircraft flying passenger routes has to be allocated to between one and two hundred flight legs given in each day's fleet plan. This is known as "tail allocation" because the individual aircraft are identified by the registrations marked on their tailfins.

Because delays, faults and other unpredictable events must be taken into account, the allocations of an individual aircraft to every flight leg are made only about a day in advance and may be modified until shortly before take-off. This allocation sounds a simple problem, but it is complicated by extensive rules and preferences governing the choice of aircraft for each flight leg, by the fact that an aircraft which is booked in for maintenance must be allocated a sequence of activities that delivers it at the right place and time for that booking and by the fact that an allocation for one day should be adjusted to allow for the requirements of the following day's plan.

It is also made more difficult because there is very little slack - aircraft are expensive resources and the fleet plan is designed to use up the whole of the fleet's capacity. This paper describes an application going live in Summer 1998 which will provide an initial solution to this allocation problem, which the user may then amend before publishing it as a detailed plan - thus helping the user without reducing their control.

See Logica's Press Release.

This work is on-going at British Airways. Mike Pegman works with Logica as a design and implementation consultant to the project.

 

Top Home

 


Liquid Metal Manufacturing

The paper describes an application which was developed for Broner plc by Vine Solutions Ltd.

Short Term Scheduling for Metal Manufacture
M Pegman Proc Third Int’l ILOG Solver and Schedule Users’ Conference, July 1997
and Proc Practical Applications of Constraint Technology ’98

This paper discusses a constraint based application for scheduling and reactive re-scheduling of a liquid metal manufacturing process. The scheduler was designed, and a demonstration system developed, during the later half of 1996, by Vine Solutions Ltd for Broner Group Ltd, a premier vendor of scheduling systems to the global metals manufacturing industry. The demonstrator system had successful early trials at a customer site. The application is to be developed further before installation in an on-line control role.

A batch of liquid metal is delivered to a series of processes, the last of which is casting, in which slabs of metal are created in a continuous process. A primary objective is to ensure that the casting machine keeps running. The scheduler ensures that liquid metal is available whenever the casting machine requires. To achieve this, the up-stream processes must be scheduled subject to constraints including the following.

The context of operation is that of on-line reactive scheduling of the manufacturing process over a period several hours from the current time. The system produces schedules based on a desired sequence of caster operations. Each caster operation identifies a works order and hence possible routings and time windows for the up-stream processes. The system performs resource allocation, choosing a route for each works order and schedules the operations on each machine.

Due to variability in process times, or unforeseen problems in the plant, the duration of each operation, or even the machine on which an operation is undertaken, may be different from the plan. In addition, the user may over-ride the automatically generated route or timings, or limit the variability of timings of operations, and of the machines allowed for a particular batch of material. The re-scheduler takes such information into account, imposing these as constraints on the output schedule. As time advances, it also automatically considers those works orders which are committed to machines allocated in a previous run of the scheduler.

The current version of the system is running in an off-line mode, being tested at the customer site, prior to installation into an on-line environment in the liquid metal processing plant. The system employs ILOG Solver and Scheduler to model all aspects of the plant, routings and works order operations. A visualisation model and interactive user interface is constructed primarily around the ILOG Views Gantt Chart.

The current paper expands on the summary given above. It discusses the application domain in more depth, gives information on each of the listed constraints, and discusses some aspects of the implementation of the scheduling model and the search strategy. A generally applicable three layer top level object model and application control loop are also presented.

This paper discusses a constraint based application for scheduling and reactive re-scheduling of a liquid metal manufacturing process. The scheduler was designed, and a prototype developed, during the later half of 1996, by Vine Solutions Ltd for Broner Group Ltd, a premier vendor of scheduling systems to the global metals manufacturing industry.

Text of paper.

Top Home

 


Constraint Based Scheduling for the Process Industries

The paper gives a summary of the requirements of schedulers for the modern manufacturing environment. Following a brief overview of constraint solving as a technique, we outline its use as a method of representing and solving scheduling problems, and move on to a description of the capabilities of a leading-edge scheduler for the process industries employing these technologies. It focuses on solution features, emphasising the innovative characteristics and the functionality which differentiate constraint based schedulers from conventional applications.

M Pegman, Dec 1995, Constraint Based Scheduling for the Process Industries,
I Chem E publication Symposium on ‘Process Scheduling’ ISBN 0 906636 29 9

Top Home


 

A Practical Resource Allocation Application - British Airways Stand Planning

This is an extract from a paper presented at PACT 96 (Practical Applications of Constraint Technology 96). It gives an overview of an application design which dates from Mike Pegman's time at Headway Systems Ltd. This extract reviews BA’s stand planner and is based on material in the public domain.

It is important for airlines, in planning facilities and operations to provide the highest quality of service to passengers, to have tools that will support evaluations of the stand layouts and facilities of the terminals. These evaluations should enable the airline to determine the impact of changes to the schedule and operating assumptions. British Airways required a stand planning tool capable of evaluating the effect of different stand layouts on customer service.

High Level Description

The stand planning application can be described as reading a list of required aircraft movements (i.e. times of arrivals and departures and the aircraft which are associated with each), and allocating airport stand resources (i.e. stands and parking locations) to meet the required movements, thus producing a stand allocation plan. The system must achieve a service provision for the scheduled arrivals and departures without violating rules such as occupancy of stands, and without exceeding the available resources. In so doing it seeks to achieve a minimum quality level of the resulting stand allocation and then to improve this quality level. The quality level is a measure of the stand allocation plan in terms of customer service and operational metrics.

The aircraft movement list contains such information as the flight number, arrival and departure times and airport names, aircraft type, passenger numbers, etc. Note that, as the arrival and departure times are given as inputs, then the problem is one of pure resource allocation.

Airport resources are represented as:

The starting point for the construction of any given plan can be either a set of unused stands, or any combination of stands previously committed to servicing flights. In other words the system supports incremental stand allocation.

Summary

The above application is characterised by being complex, combinatorial, time based and of a high value. It is a resource allocation problem.

The use of constraint solving tools, in conjunction with intelligent search strategies, lowers the barriers to the practical solution of complex combinatorial problems. It is now feasible to build applications within acceptable development time and costs, in which the complex trade-offs between resource availability, service quality, time, and financial considerations can be modelled and managed during the generation of operational plans and schedules.

M Pegman, Vine Solutions Ltd, and J Heslop, Headway Systems Limited, Dec 1995,
Practical Scheduling and Resource Allocation Applications at Courtaulds Coatings and British Airways, Proc PACT96

Also see the Ilog web site for a Financial Times story: Ilog


Top of page Home


© Copyright Vine Solutions Ltd 1997-99 Email to: mp@vinesolutions.co.uk