[ The ECLiPSe Libraries | Reference Manual | Alphabetic Index ]

# library(ic_probing_for_scheduling)

Probing for Scheduling

## Predicates

fun_to_cons_var(+CostFun, -ConsList, -CostVar)
Convert a cost expression to a variable and a list of constraints, suitable to pass into probe_cstr_sched/7
probe_cstr_sched(+Starts, +Durations, +Resources, ++MaxResource, +Constraints, -Cost, ++Options)
Find a resource-feasible schedule that minimises the cost, subject to the constraints
probe_sched(+Starts, +Durations, +Resources, ++MaxResource, ?CostFun)
Find a resource-feasible schedule that minimises the cost function

## Description

This is a complete search method for resource-constrained scheduling problems

The user interface is similar to the cumulative constraint, with a list of task start times, durations and resources; and a maximum resource limit. There is one extra argument, a cost function which is to be minimised.

Probing for scheduling differs radically from the cumulative constraint because it includes a search routine. In its behaviour it is an optimisation procedure and not simply a constraint which enforces consistency.

The search is focussed towards an optimal vlaue of the cost function.

## Examples

```% Example program: simple schedule optimisation

:- lib(ic_probing_for_scheduling).
:- lib(ic).

ex1([X,Y,Z],Cost) :-
[OldX,OldY,OldZ]=[1,5,5],
Durations=[10,5,5],
Resources=[1,2,1],
MaxResource=2,
NewStarts=[X,Y,Z],
ic:(NewStarts::1..10),
CostFun= abs(X-OldX) + abs(Y-OldY) + abs(Z-OldZ),
probe_sched(NewStarts,Durations,Resources,MaxResource,CostFun),
Cost is CostFun.

ex2([X,Y,Z],Cost) :-
[OldX,OldY,OldZ]=[1,5,5],
Durations=[10,5,5],
Resources=[1,2,1],
MaxResource=2,
NewStarts=[X,Y,Z],
ic:(NewStarts::1..10),
Constraints=[
XDiff >= X-OldX, XDiff >= OldX-X,
YDiff >= Y-OldY, YDiff >= OldY-Y,
ZDiff >= Z-OldZ, ZDiff >= OldZ-Z,
Cost =:= XDiff+YDiff+ZDiff
],
Options=[granularity(1),priority(5)],
probe_cstr_sched(NewStarts,Durations,Resources,MaxResource,
Constraints,Cost,Options).

ex3(Starts,MaxResource,Cost) :-
Starts=[S1,S2,S3,S4],
ic:(S1::1..10),
ic:(S2::3..10),
ic:(S3::1..5),
ic:(S4::3..10),
[D1,D2,D3,D4]=[5,5,3,3],
Durations=[D1,D2,D3,D4],
Resources=[1,1,1,1],
CostFun= max([S1+D1,S2+D2,S3+D3,S4+D4]),
probe_sched(Starts,Durations,Resources,MaxResource,CostFun),
ic:(Cost =:= eval(CostFun)).

```

## About

• Author: Mark Wallace, Hani El Sakkout
• Copyright © Imperial College London and Parc Technologies
• Date: \$Date: 2005/05/11 11:30:39 \$

Generated from ic_probing_for_scheduling.eci on Tue May 23 02:57:27 2006