[ 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


Generated from ic_probing_for_scheduling.eci on 2009-02-24 09:44